cutting planes

Optimality-Based Discretization Methods for the Global Optimization of Nonconvex Semi-Infinite Programs

  • Evren Turan
  • Johannes Jäschke
  • Rohit Kannan
    • Categories Global Optimization, Semi-infinite Programming Tags , , , , ,

    We use sensitivity analysis to design optimality-based discretization (cutting-plane) methods for the global optimization of nonconvex semi-infinite programs (SIPs). We begin by formulating the optimal discretization of SIPs as a max-min problem and propose variants that are more computationally tractable. We then use parametric sensitivity theory to design an efficient method for solving these max-min … Read more

    Monoidal Strengthening of Simple V-Polyhedral Disjunctive Cuts

  • Aleksandr M. Kazachkov
  • Egon Balas
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming Tags , , ,

    Disjunctive cutting planes can tighten a relaxation of a mixed-integer linear program. Traditionally, such cuts are obtained by solving a higher-dimensional linear program, whose additional variables cause the procedure to be computationally prohibitive. Adopting a V-polyhedral perspective is a practical alternative that enables the separation of disjunctive cuts via a linear program with only as … Read more

    Integer Programming Models for Round Robin Tournaments

  • Jasper van Doornmalen
  • Christopher Hojny
    • Categories Scheduling Tags , , ,

    Round robin tournaments are omnipresent in sport competitions and beyond. We propose two new integer programming formulations for scheduling a round robin tournament, one of which we call the matching formulation. We analytically compare their linear relaxations with the linear relaxation of a well-known traditional formulation. We find that the matching formulation is stronger than … Read more

    On the strength of recursive McCormick relaxations for binary polynomial optimization

  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Integer Programming Tags , , , ,

    Recursive McCormick relaxations have been among the most popular convexification techniques for binary polynomial optimization problems. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal recursive sequence amounts to solving a difficult combinatorial optimization problem. In this paper, we prove that any … Read more

    Relaxations and Cutting Planes for Linear Programs with Complementarity Constraints

  • Alberto Del Pia
  • Jeff Linderoth
  • Haoran Zhu
    • Categories 0-1 Programming, Cutting Plane Approaches, Global Optimization Tags , , , ,

    We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based on identifying vertex covers of the conflict graph of the instance and generalizes the extended reformulation-linearization technique of Nguyen, Richard, and Tawarmalani to instances with general complementarity conditions between variables. We demonstrate … Read more

    V-polyhedral disjunctive cuts

  • Egon Balas
  • Aleksandr M. Kazachkov
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming Tags , , ,

    We introduce V-polyhedral disjunctive cuts (VPCs) for generating valid inequalities from general disjunctions. Cuts are critical to integer programming solvers, but the benefit from many families is only realized when the cuts are applied recursively, causing numerical instability and “tailing off” of cut strength after several rounds. To mitigate these difficulties, the VPC framework offers … Read more

    Learning to Use Local Cuts

  • Timo Berthold
  • Matteo Francobaldi
  • Gregor Hendel
    • Categories (Mixed) Integer Linear Programming, Optimization Software Design Principles Tags , ,

    An essential component in modern solvers for mixed-integer (linear) programs (MIPs) is the separation of additional inequalities (cutting planes) to tighten the linear programming relaxation. Various algorithmic decisions are necessary when integrating cutting plane methods into a branch-and-bound (B&B) solver as there is always the trade-off between the efficiency of the cuts and their costs, … Read more

    Partitioning through projections: strong SDP bounds for large graph partition problems

  • Frank de Meijer
  • Renata Sotirov
  • Angelika Wiegele
  • Shudian Zhao
    • Categories Semi-definite Programming Tags , , , ,

    The graph partition problem (GPP) aims at clustering the vertex set of a graph into a fixed number of disjoint subsets of given sizes such that the sum of weights of edges joining different sets is minimized. This paper investigates the quality of doubly nonnegative (DNN) relaxations, i.e., relaxations having matrix variables that are both … Read more

    A Finitely Convergent Cutting Plane, and a Bender’s Decomposition Algorithm for Mixed-Integer Convex and Two-Stage Convex Programs using Cutting Planes

  • Fengqiao Luo
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Stochastic Programming Tags , , ,

    We consider a general mixed-integer convex program. We first develop an algorithm for solving this problem, and show its nite convergence. We then develop a finitely convergent decomposition algorithm that separates binary variables from integer and continuous variables. The integer and continuous variables are treated as second stage variables. An oracle for generating a parametric … Read more

    Simple odd beta-cycle inequalities for binary polynomial optimization

  • Alberto Del Pia
  • Matthias Walter
    • Categories 0-1 Programming, Bound-constrained Optimization, Polyhedra Tags , ,

    We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd beta-cycle inequalities valid for this polytope, showed that these generally have Chvátal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle … Read more