Cutting Plane Approaches

Stabilized Benders methods for large-scale combinatorial optimization, with application to data privacy

  • Daniel Baena
  • Jordi Castro
  • Antonio Frangioni
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Cutting Plane Approaches

    The Cell Suppression Problem (CSP) is a challenging Mixed-Integer Linear Problem arising in statistical tabular data protection. Medium sized instances of CSP involve thousands of binary variables and million of continuous variables and constraints. However, CSP has the typical structure that allows application of the renowned Benders’ decomposition method: once the “complicating” binary variables are … Read more

    Lower bounds on the lattice-free rank for packing and covering integer programs

  • Merve Bodur
  • Alberto Del Pia
  • Santanu S. Dey
  • Marco Molinaro
    • Categories Cutting Plane Approaches, Integer Programming Tags , , , , ,

    In this paper, we present lower bounds on the rank of the split closure, the multi-branch closure and the lattice-free closure for packing sets as a function of the integrality gap. We also provide a similar lower bound on the split rank of covering polyhedra. These results indicate that whenever the integrality gap is high, … Read more

    A Benders squared (B2) framework for infinite-horizon stochastic linear programs

  • Giacomo Nannicini
  • Roberto Wolfler Calvo
  • Emiliano Traversi
    • Categories Cutting Plane Approaches, Linear Programming, Stochastic Programming

    We propose a nested decomposition scheme for infinite-horizon stochastic linear programs. Our approach can be seen as a provably convergent extension of stochastic dual dynamic programming to the infinite-horizon setting: we explore a sequence of finite-horizon problems of increasing length until we can prove convergence with a given confidence level. The methodology alternates between a … Read more

    Facets for Single Module and Multi-Module Capacitated Lot-Sizing Problems without Backlogging

  • Manish Bansal
    • Categories Cutting Plane Approaches, Production and Logistics Tags , , , , ,

    In this paper, we consider the well-known constant-batch lot-sizing problem, which we refer to as the single module capacitated lot-sizing (SMLS) problem, and multi-module capacitated lot-sizing (MMLS) problem. We provide sufficient conditions under which the (k,l,S,I) inequalities of Pochet and Wolsey (Math of OR 18: 767-785, 1993), the mixed (k,l,S,I) inequalities, derived using mixing procedure … Read more

    Structure and Interpretation of Dual-Feasible Functions

  • Matthias Köppe
  • Jiawei Wang
    • Categories Combinatorial Optimization, Cutting Plane Approaches

    We study two techniques to obtain new families of classical and general Dual-Feasible Functions: A conversion from minimal Gomory–Johnson functions; and computer-based search using polyhedral computation and an automatic maximality and extremality test. Citation 6 pages extended abstract to appear in Proc. LAGOS 2017, with 21 pages of appendix. Article Download View Structure and Interpretation … Read more

    Branch-and-cut methods for the Network Design Problem with Vulnerability Constraints

  • Luís Gouveia
  • Martim Joyce-Moniz
  • Markus Leitner
    • Categories Cutting Plane Approaches, Network Optimization, Telecommunications

    The aim of Network Design Problem with Vulnerability Constraints (NDPVC), introduced by Gouveia and Leitner [EJOR, 2017], is to design survivable telecommunications networks that impose length bounds on the communication paths of each commodity pair, before and after the failure of any k links. This problem was proposed as an alternative to the Hop-Constrained Survivable … Read more

    Outer-Product-Free Sets for Polynomial Optimization and Oracle-Based Cuts

  • Daniel Bienstock
  • Chen Chen
  • Gonzalo Muñoz
    • Categories Constrained Nonlinear Optimization, Cutting Plane Approaches, Global Optimization Theory Tags , ,

    Cutting planes are derived from specific problem structures, such as a single linear constraint from an integer program. This paper introduces cuts that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set $S\cap P$, where $S$ is a closed set, … Read more

    A hybrid approach for Bi-Objective Optimization

  • Kim Allan Andersen
  • Thomas R. Stidsen
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Multi-Criteria Optimization

    A large number of the real world planning problems which are today solved using Operations Research methods are actually multi-objective planning problems, but most of them are solved using single-objective methods. The reason for converting, i.e. simplifying, multi- objective problems to single-objective problems is that no standard multi-objective solvers exist and specialized algorithms need to … Read more

    Packing circles in a square: a theoretical comparison of various convexification techniques

  • Aida Khajavirad
    • Categories Cutting Plane Approaches, Global Optimization Theory Tags , , , ,

    We consider the problem of packing congruent circles with the maximum radius in a unit square. As a mathematical program, this problem is a notoriously difficult nonconvex quadratically constrained optimization problem which possesses a large number of local optima. We study several convexification techniques for the circle packing problem, including polyhedral and semi-definite relaxations and … Read more

    Partial hyperplane activation for generalized intersection cuts

  • Egon Balas
  • Aleksandr M. Kazachkov
  • François Margot
  • Selvaprabu Nadarajah
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    The generalized intersection cut (GIC) paradigm is a recent framework for generating cutting planes in mixed integer programming with attractive theoretical properties. We investigate this computationally unexplored paradigm and observe that a key hyperplane activation procedure embedded in it is not computationally viable. To overcome this issue, we develop a novel replacement to this procedure … Read more