integer programming

Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • Categories 0-1 Programming, Convex Optimization, Semi-definite Programming Tags , , , , , ,

    We consider operators acting on convex subsets of the unit hypercube. These operators are used in constructing convex relaxations of combinatorial optimization problems presented as a 0,1 integer programming problem or a 0,1 polynomial optimization problem. Our focus is mostly on operators that, when expressed as a lift-and-project operator, involve the use of semidefiniteness constraints … Read more

    Decomposition of loosely coupled integer programs: A multiobjective perspective

  • Shabbir Ahmed
  • Merve Bodur
  • Natashia Boland
  • George L. Nemhauser
    • Categories Integer Programming, Multi-Criteria Optimization Tags , , ,

    We consider integer programming (IP) problems consisting of (possibly a large number of) subsystems and a small number of coupling constraints that link variables from different subsystems. Such problems are called loosely coupled or nearly decomposable. Motivated by recent developments in multiobjective programming (MOP), we develop a MOP-based decomposition algorithm to solve loosely coupled IPs. … Read more

    On the polyhedrality of closures of multi-branch split sets and other polyhedra with bounded max-facet-width

  • Sanjeeb Dash
  • Oktay Gunluk
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    For a fixed integer $t > 0$, we say that a $t$-branch split set (the union of $t$ split sets) is dominated by another one on a polyhedron $P$ if all cuts for $P$ obtained from the first $t$-branch split set are implied by cuts obtained from the second one. We prove that given a … Read more

    Aggregation-based cutting-planes for packing and covering integer programs

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

    In this paper, we study the strength of Chvatal-Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs). Aggregation cuts are obtained as follows: Given an IP formulation, we first generate a single implied inequality using aggregation of the original constraints, then obtain the integer hull of the set defined … Read more

    Mixed-integer Programming Based Approaches for the Movement Planner Problem: Model, Heuristics and Decomposition

  • Chiwei Yan
  • Luyi Yang
    • Categories Scheduling, Transportation Tags , , , ,

    This is the first prize winning report for the 2012 INFORMS Railway Application Section Problem Solving Competition (https://www.informs.org/Community/RAS/Problem-Solving-Competition/2012-RAS-Problem-Solving-Competition). ArticleDownload View PDF

    A combinatorial approach for small and strong formulations of disjunctive constraints

  • Joey Huchette
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We present a framework for constructing small, strong mixed-integer formulations for disjunctive constraints. Our approach is a generalization of the logarithmically-sized formulations of Vielma and Nemhauser for SOS2 constraints, and we offer a complete characterization of its expressive power. We apply the framework to a variety of disjunctive constraints, producing novel, small, and strong formulations … Read more

    Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VI. The Curious Case of Two-Sided Discontinuous Functions

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

    We construct a two-sided discontinuous piecewise linear minimal valid function for the 1-row Gomory–Johnson model which is not extreme, but which is not a convex combination of other piecewise linear minimal valid functions. This anomalous behavior results from combining features of Hildebrand’s two-sided discontinuous extreme functions and Basu–Hildebrand–Koeppe’s piecewise linear extreme function with irrational breakpoints. … Read more

    Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. V. Software for the continuous and discontinuous 1-row case

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

    We present software for investigations with cut generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath. CitationAn extended abstract of 8 pages appeared under the title “Software for cut-generating functions in the Gomory–Johnson model and beyond” in Proc. International Congress on Mathematical Software 2016ArticleDownload View PDF

    A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs

  • Vicky Mak-Hau
    • Categories Polyhedra Tags , , , ,

    In this paper, we study the Cardinality Constrained Multi-cycle Problem (CCMcP) and the Car- dinality Constrained Cycle and Chain Problem (CCCCP). A feasible solution allows one or more cardinality-constrained cycles to exist on the digraph. A vertex can only be involved in at most one cycle, and there may be vertices not involved in any … Read more

    Beating the SDP bound for the floor layout problem: A simple combinatorial idea

  • Santanu S. Dey
  • Joey Huchette
  • Juan Pablo Vielma
    • Categories Facility Planning and Design, Integer Programming Tags ,

    For many Mixed-Integer Programming (MIP) problems, high-quality dual bounds can obtained either through advanced formulation techniques coupled with a state-of-the-art MIP solver, or through Semidefinite Programming (SDP) relaxation hierarchies. In this paper, we introduce an alternative bounding approach that exploits the “combinatorial implosion” effect by solving portions of the original problem and aggregating this information … Read more