Cutting Plane Approaches

Decomposition and Dynamic Cut Generation in Integer Linear Programming

  • M.V. Galati
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , , , ,

    Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen the linear programming relaxation. Recently, a number of … Read more

    Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation

  • Alper Atamturk
  • Simge Küçükyavuz
    • Categories Cutting Plane Approaches, Production and Logistics Tags , , ,

    We investigate the polyhedral structure of the lot-sizing problem with inventory bounds. We consider two models, one with linear costs on inventory, the other with linear and fixed costs on inventory. For both models, we identify facet-defining inequalities that make use of the inventory capacities explicitly and give exact separation algorithms. We also give a … Read more

    Cover and pack inequalities for (mixed) integer programming

  • Alper Atamturk
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    We review strong inequalities for fundamental knapsack relaxations of (mixed) integer programs. These relaxations are the 0-1 knapsack set, the mixed 0-1 knapsack set, the integer knapsack set, and the mixed integer knapsack set. Our aim is to give a unified presentation of the inequalities based on covers and packs and highlight the connections among … Read more

    Using selective orthonormalization to update the analytic center after the addition of multiple cuts

  • John E. Mitchell
  • Srinivasan Ramaswamy
    • Categories Convex Optimization, Cutting Plane Approaches, Nonsmooth Optimization Tags , , , ,

    We study the issue of updating the analytic center after multiple cutting planes have been added through the analytic center of the current polytope in Euclidean n-space. This is an important issue that arises at every `stage’ in a cutting plane algorithm. If q cuts are to be added, with q no larger than n, … Read more

    Lagrangean Duality Applied on Vehicle Routing with Time Windows

  • Brian Kallehauge
  • Jesper Larsen
  • Oli B.G. Madsen
    • Categories Cutting Plane Approaches, Nonsmooth Optimization, Transportation Tags , , , , ,

    This paper presents the results of the application of a non-differentiable optimization method in connection with the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is an extension of the Vehicle Routing Problem. In the VRPTW the service at each customer must start within an associated time window. The Shortest Path decomposition of the … Read more

    A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations

  • Christoph Helmberg
    • Categories Cutting Plane Approaches, Nonsmooth Optimization, Semi-definite Programming Tags , , , , , ,

    The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges … Read more

    The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

  • Shabbir Ahmed
  • Anton J. Kleywegt
  • George L. Nemhauser
  • Alexander Shapiro
  • Bram Verweij
    • Categories Cutting Plane Approaches, Stochastic Programming, Transportation Tags , , ,

    The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. … Read more

    Polynomial interior point cutting plane methods

  • John E. Mitchell
    • Categories Cutting Plane Approaches, Linear Programming, Nonsmooth Optimization Tags , , ,

    Polynomial cutting plane methods based on the logarithmic barrier function and on the volumetric center are surveyed. These algorithms construct a linear programming relaxation of the feasible region, find an appropriate approximate center of the region, and call a separation oracle at this approximate center to determine whether additional constraints should be added to the … Read more

    Branch-and-cut for the k-way equipartition problem

  • John E. Mitchell
    • Categories Cutting Plane Approaches, Polyhedra Tags , , , ,

    We investigate the polyhedral structure of a formulation of the k-way equipartition problem and a branch-and-cut algorithm for the problem. The k-way equipartition problem requires dividing the vertices of a weighted graph into k equally sized sets, so as to minimize the total weight of edges that have both endpoints in the same set. Applications … Read more