Cutting Plane Approaches

Benders Cut Classification via Support Vector Machines for Solving Two-stage Stochastic Programs

  • Huiwen Jia
  • Siqian Shen
    • Categories Cutting Plane Approaches, Stochastic Programming Tags , , ,

    We consider Benders decomposition for solving two-stage stochastic programs with complete recourse based on finite samples of the uncertain parameters. We define the Benders cuts binding at the final optimal solution or the ones significantly improving bounds over iterations as valuable cuts. We propose a learning-enhanced Benders decomposition (LearnBD) algorithm, which adds a cut classification … Read more

    Generalized Chvatal-Gomory closures for integer programs with bounds on variables

  • Sanjeeb Dash
  • Oktay Gunluk
  • Dabeen Lee
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    Integer programming problems that arise in practice often involve decision variables with one or two sided bounds. In this paper, we consider a generalization of Chvatal-Gomory inequalities obtained by strengthening Chvatal-Gomory inequalities using the bounds on the variables. We prove that the closure of a rational polyhedron obtained after applying the generalized Chvatal-Gomory inequalities is … Read more

    Decorous Combinatorial Lower Bounds for Row Layout Problems

  • Mirko Dahlbeck
  • Anja Fischer
  • Frank Fischer
    • Categories Cutting Plane Approaches, Facility Planning and Design

    In this paper we consider the Double-Row Facility Layout Problem (DRFLP). Given a set of departments and pairwise transport weights between them the DRFLP asks for a non-overlapping arrangement of the departments along both sides of a common path such that the weighted sum of the center-to-center distances between the departments is minimized. Despite its … Read more

    On the depth of cutting planes

  • Laurent Poirrier
  • James Yu
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , ,

    We introduce a natural notion of depth that applies to individual cutting planes as well as entire families. This depth has nice properties that make it easy to work with theoretically, and we argue that it is a good proxy for the practical strength of cutting planes. In particular, we show that its value lies … Read more

    Submodularity in conic quadratic mixed 0-1 optimization

  • Alper Atamturk
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , , , , , ,

    We describe strong convex valid inequalities for conic quadratic mixed 0-1 optimization. These inequalities can be utilized for solving numerous practical nonlinear discrete optimization problems from value-at-risk minimization to queueing system design, from robust interdiction to assortment optimization through appropriate conic quadratic mixed 0-1 relaxations. The inequalities exploit the submodularity of the binary restrictions and … Read more

    Consistency for 0-1 programming

  • Danial Davarnia
  • John Hooker
    • Categories Cutting Plane Approaches, Integer Programming

    Concepts of consistency have long played a key role in constraint programming but never developed in integer programming (IP). Consistency nonetheless plays a role in IP as well. For example, cutting planes can reduce backtracking by achieving various forms of consistency as well as by tightening the linear programming (LP) relaxation. We introduce a type … Read more

    Generating feasible points for mixed-integer convex optimization problems by inner parallel cuts

  • Christoph Neumann
  • Oliver Stein
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    In this article we introduce an inner parallel cutting plane method (IPCP) to compute good feasible points along with valid cutting planes for mixed-integer convex optimization problems. The method iteratively generates polyhedral outer approximations of an enlarged inner parallel set (EIPS) of the continuously relaxed feasible set. This EIPS possesses the crucial property that any … Read more

    Chvatal rank in binary polynomial optimization

  • Alberto Del Pia
  • Silvia Di Gregorio
    • Categories 0-1 Programming, Cutting Plane Approaches, Global Optimization Theory Tags , , , , ,

    Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvatal rank. We show that almost all known cutting planes have Chvatal rank 1. All these inequalities have an associated hypergraph that is beta-acyclic, thus, … Read more

    Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse semigroup theory, closures, decomposition of perturbations

  • Robert Hildebrand
  • Matthias Köppe
  • Yuan Zhou
    • Categories Cutting Plane Approaches Tags , ,

    In this self-contained paper, we present a theory of the piecewise linear minimal valid functions for the 1-row Gomory-Johnson infinite group problem. The non-extreme minimal valid functions are those that admit effective perturbations. We give a precise description of the space of these perturbations as a direct sum of certain finite- and infinite-dimensional subspaces. The … Read more

    Submodularity and valid inequalities in nonlinear optimization with indicator variables

  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    We propose a new class of valid inequalities for mixed-integer nonlinear optimization problems with indicator variables. The inequalities are obtained by lifting polymatroid inequalities in the space of the 0–1 variables into conic inequalities in the original space of variables. The proposed inequalities are shown to describe the convex hull of the set under study … Read more