Cutting Plane Approaches

A Polyhedral Study of the Integrated Minimum-Up/-Down Time and Ramping Polytope

  • Yongpei Guan
  • Kai Pan
    • Categories Applications - Science and Engineering, Cutting Plane Approaches

    In this paper, we consider the polyhedral structure of the integrated minimum-up/-down time and ramping polytope for the unit commitment problem. Our studied generalized polytope includes minimum-up/-down time constraints, generation ramp-up/-down rate constraints, logical constraints, and generation upper/lower bound constraints. We derive strong valid inequalities by utilizing the structures of the unit commitment problem, and … Read more

    New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem

  • Matthias Köppe
  • Yuan Zhou
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We describe new computer-based search strategies for extreme functions for the Gomory–Johnson infinite group problem. They lead to the discovery of new extreme functions, whose existence settles several open questions. ArticleDownload View PDF

    Cutting planes from extended LP formulations

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

    Given a mixed-integer set defined by linear inequalities and integrality requirements on some of the variables, we consider extended formulations of its continuous (LP) relaxation and study the effect of adding cutting planes in the extended space. In terms of optimization, extended LP formulations do not lead to better bounds as their projection onto the … Read more

    A polyhedral study of binary polynomial programs

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization

    We study the polyhedral convex hull of a mixed-integer set S defined by a collection of multilinear equations over the 0-1-cube. Such sets appear frequently in the factorable reformulation of mixed-integer nonlinear optimization problems. In particular, the set S represents the feasible region of a linearized unconstrained binary polynomial optimization problem. We define an equivalent … Read more

    Maximizing a class of submodular utility functions with constraints

  • Shabbir Ahmed
  • Jiajin Yu
    • Categories 0-1 Programming, Cutting Plane Approaches, Stochastic Programming Tags , , , ,

    Motivated by stochastic 0-1 integer programming problems with an expected utility objective, we study the mixed-integer nonlinear set: $P = \cset{(w,x)\in \reals \times \set{0,1}^N}{w \leq f(a’x + d), b’x \leq B}$ where $N$ is a positive integer, $f:\reals \mapsto \reals$ is a concave function, $a, b \in \reals^N$ are nonnegative vectors, $d$ is a real … Read more

    An electronic compendium of extreme functions for the Gomory–Johnson infinite group problem

  • Matthias Köppe
  • Yuan Zhou
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches

    In this note we announce the availability of an electronic compendium of extreme functions for Gomory–Johnson’s infinite group problem. These functions serve as the strongest cut-generating functions for integer linear optimization problems. We also close several gaps in the literature. ArticleDownload View PDF

    Strong Inequalities for Chance-Constrained Program

  • Kai Huang
  • Bo Zeng
  • Ming Zhao
    • Categories Cutting Plane Approaches, Integer Programming Tags , ,

    As an essential substructure underlying a large class of chance-constrained programming problems with finite discrete distributions, the mixing set with $0-1$ knapsack has received considerable attentions in recent literature. In this study, we present a family of strong inequalities that subsume existing ones for this set. We also find many other inequalities that can be … Read more

    Light on the Infinite Group Relaxation

  • Amitabh Basu
  • Robert Hildebrand
  • Matthias Köppe
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches

    This is a survey on the infinite group problem, an infinite-dimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their groundbreaking papers titled “Some continuous functions related to corner polyhedra I, II” [Math. Programming 3 (1972), 23-85, 359-389]. The survey presents the infinite group problem in the modern context … Read more

    Facets for Continuous Multi-Mixing Set with General Coefficients and Bounded Integer Variables

  • Manish Bansal
  • Kiavash Kianfar
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming Tags , , , , ,

    Bansal and Kianfar introduced continuous multi-mixing set where the coefficients satisfy the so-called n-step MIR conditions and developed facet-defining inequalities for this set. In this paper, we first generalize their inequalities for the continuous multi-mixing set with general coefficients (where no conditions are imposed on the coefficients) and show that they are facet-defining in many … Read more

    Operations that preserve the covering property of the lifting region

  • Amitabh Basu
  • Joseph Paat
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches

    We contribute to the theory for minimal liftings of cut-generating functions. In particular, we give three operations that preserve the so-called covering property of certain structured cut-generating functions. This has the consequence of vastly expanding the set of undominated cut generating functions which can be used computationally, compared to known examples from the literature. The … Read more