cutting planes

On the Relation between the Extended Supporting Hyperplane Algorithm and Kelley’s Cutting Plane Algorithm

  • Ambros Gleixner
  • Felipe Serrano
  • Robert Schwarz
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization Tags , ,

    Recently, Kronqvist et al.rediscovered the supporting hyperplane algorithm of Veinott and demonstrated its computational benefits for solving convex mixed-integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley’s cutting plane algorithm applied to a particular … 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

    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

    Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks

  • Radu Baltean-Lugojan
  • Pierre Bonami
  • Ruth Misener
  • Andrea Tramontani
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming Tags , , , , ,

    Semidefinite programming relaxations complement polyhedral relaxations for quadratic optimization, but global optimization solvers built on polyhedral relaxations cannot fully exploit this advantage. This paper develops linear outer-approximations of semidefinite constraints that can be effectively integrated into global solvers. The difference from previous work is that our proposed cuts are (i) sparser with respect to the … 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

    Inexact cutting planes for two-stage mixed-integer stochastic programs

  • Ward Romeijnders
  • Niels van der Laan
    • Categories Cutting Plane Approaches, Stochastic Programming Tags , , ,

    We propose a novel way of applying cutting plane techniques to two-stage mixed-integer stochastic programs. Instead of using cutting planes that are always valid, our idea is to apply inexact cutting planes to the second-stage feasible regions that may cut away feasible integer second-stage solutions for some scenarios and may be overly conservative for others. … Read more

    A Branch-and-Cut Algorithm for Solving Mixed-integer Semidefinite Optimization Problems

  • Ken Kobayashi
  • Yuichi Takano
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Semi-definite Programming Tags , , ,

    This paper is concerned with a cutting-plane algorithm for solving mixed-integer semidefinite optimization (MISDO) problems. In this algorithm, the positive semidefinite constraint is relaxed, and the resultant mixed-integer linear optimization problem is repeatedly solved with valid inequalities for the relaxed constraint. We prove convergence properties of the algorithm. Moreover, to speed up the computation, we … Read more

    Cutting Planes by Projecting Interior Points onto Polytope Facets

  • Daniel Porumbel
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Linear Programming Tags , ,

    Given a point x inside a polytope P and a direction d, the projection of x along d asks to find the maximum step length t such that x+td is feasible; we say x+td is a pierce point because it belongs to the boundary of P. We address this projection sub-problem with arbitrary interior points … Read more

    Scanning integer points with lex-inequalities: A finite cutting plane algorithm for integer programming with linear objective

  • Michele Conforti
  • Marianna De Santis
  • Marco Di Summa
  • Francesco Rinaldi
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags ,

    We consider the integer points in a unimodular cone K ordered by a lexicographic rule defined by a lattice basis. To each integer point x in K we associate a family of inequalities (lex-inequalities) that defines the convex hull of the integer points in K that are not lexicographically smaller than x. The family of … Read more

    The Supporting Hyperplane Optimization Toolkit

  • Jan Kronqvist
  • Andreas Lundell
  • Tapio Westerlund
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , , , , ,

    In this paper, an open source solver for mixed-integer nonlinear programming (MINLP) problems is presented. The Supporting Hyperplane Optimization Toolkit (SHOT) combines a dual strategy based on polyhedral outer approximations (POA) with primal heuristics. The outer approximation is achieved by expressing the nonlinear feasible set of the MINLP problem with linearizations obtained with the extended … Read more