Intermediate integer programming representations using value disjunctions
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1187159 (Why is no real title available?)
- scientific article; zbMATH DE number 3545380 (Why is no real title available?)
- scientific article; zbMATH DE number 3568353 (Why is no real title available?)
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Combining Problem Structure with Basis Reduction to Solve a Class of Hard Integer Programs
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition
- Hilbert Bases and the Facets of Special Knapsack Polytopes
- Improving Discrete Model Representations via Symmetry Considerations
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances
- Solving a system of linear Diophantine equations with lower and upper bounds on the variables.
- Subset Algebra Lift Operators for 0-1 Integer Programming
- The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
- The Steiner tree problem. II: Properties and classes of facets
- Using separation algorithms to generate mixed integer model reformulations
Cited in
(7)- A note on splitting of variables in integer programming models
- An integer programming framework for critical elements detection in graphs
- Irregular polyomino tiling via integer programming with application in phased array antenna design
- Valid inequalities for mixed integer linear programs
- Binary extended formulations of polyhedral mixed-integer sets
- 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
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)
