Intermediate integer programming representations using value disjunctions
From MaRDI portal
Publication:951104
DOI10.1016/J.DISOPT.2006.12.003zbMATH Open1151.90502arXivmath/0603311OpenAlexW3100383456MaRDI QIDQ951104FDOQ951104
Quentin Louveaux, Robert Weismantel, Matthias Köppe
Publication date: 29 October 2008
Published in: Discrete Optimization (Search for Journal in Brave)
Abstract: We introduce a general technique to create an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The extended formulation is constructed by creating a new binary variable for each generated value. Initial experiments show that the extended formulation can have a more compact complete description than the original formulation. We prove that, using this reformulation technique, the facet description decomposes into one ``linking polyhedron per block and the ``aggregated polyhedron. Each of these polyhedra can be analyzed separately. For the case of identical coefficients in a block, we provide a complete description of the linking polyhedron and a polynomial-time separation algorithm. Applied to the knapsack with a fixed number of distinct coefficients, this theorem provides a complete description in an extended space with a polynomial number of variables.
Full work available at URL: https://arxiv.org/abs/math/0603311
Recommendations
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Mixed integer programming (90C11)
Cites Work
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
- Solving a system of linear Diophantine equations with lower and upper bounds on the variables.
- Title not available (Why is that?)
- The Steiner tree problem. II: Properties and classes of facets
- Title not available (Why is that?)
- Using separation algorithms to generate mixed integer model reformulations
- Title not available (Why is that?)
- Improving Discrete Model Representations via Symmetry Considerations
- Subset Algebra Lift Operators for 0-1 Integer Programming
- Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances
- Hilbert Bases and the Facets of Special Knapsack Polytopes
- Combining Problem Structure with Basis Reduction to Solve a Class of Hard Integer Programs
- Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition
Cited In (6)
- An integer programming framework for critical elements detection in graphs
- Valid inequalities for mixed integer linear programs
- Irregular polyomino tiling via integer programming with application in phased array antenna design
- Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results
- Ideal, non-extended formulations for disjunctive constraints admitting a network representation
- A note on splitting of variables in integer programming models
Uses Software
This page was built for publication: Intermediate integer programming representations using value disjunctions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q951104)
