Valid inequalities for mips and group polyhedra from approximate liftings
The paper presents a new simple and constructive approximate lifting scheme for the generation of cuts for mixed-integer linear programs. The approach allows the generation of strong inequalities for the group problem. First a scheme for obtaining valid inequalities for a mixed integer problem with just one constraint is described. Here a approximate superadditive lifting of the integer variables is followed by an approximate superlinear lifting of the real variables. The relations between this lifting approach and Johnson's superadditive theory of valid inequalities for MIPs is discussed as well as the relation to Gomory's subadditive characterization of the facets for the group problem. Moreover, a family of piecewise linear approximate lifting functions is introduced and it is discussed under which conditions they are superadditive. Several classes of known cutting planes and a new class of cuts are obtained by analyzing the underlying parameterized polyhedron. Moreover, the computational potential of the new approach is outlined.
- New inequalities for finite and infinite group problems from approximate lifting
- On lifting integer variables in minimal inequalities
- Generalized mixed integer rounding inequalities: Facets for infinite group polyhedra
- Lifting for conic mixed-integer programming
- Linear-programming-based lifting and its application to primal cutting-plane algorithms
- k-cuts: a variation of Gomory mixed integer cuts from the LP tableau
- Corner polyhedra and their connection with cutting planes
- Cyclic group and knapsack facets
- Edmonds polytopes and a hierarchy of combinatorial problems
- scientific article; zbMATH DE number 2196290 (Why is no real title available?)
- Integer Programming and Pricing
- Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms
- Lifted inequalities for 0-1 mixed integer programming: superlinear lifting
- MIP: Theory and practice -- closing the gap
- On the facial structure of set packing polyhedra
- Sequence Independent Lifting for Mixed-Integer Programming
- Sequence independent lifting in mixed integer programming
- Some continuous functions related to corner polyhedra
- Some continuous functions related to corner polyhedra, II
- Some polyhedra related to combinatorial problems
- T-space and cutting planes
- Technical Note—Facets and Strong Valid Inequalities for Integer Programs
- Valid Inequalities and Superadditivity for 0–1 Integer Programs
- Valid inequalities based on the interpolation procedure
- Theoretical challenges towards cutting-plane selection
- New computer-based search strategies for extreme functions of the Gomory-Johnson infinite group problem
- Some cut-generating functions for second-order conic sets
- Equivariant perturbation in Gomory and Johnson's infinite group problem. VI: The curious case of two-sided discontinuous minimal valid functions
- An electronic compendium of extreme functions for the Gomory-Johnson infinite group problem
- The master equality polyhedron with multiple rows
- Two row mixed-integer cuts via lifting
- Software for Cut-Generating Functions in the Gomory–Johnson Model and Beyond
- Toward Computer-Assisted Discovery and Automated Proofs of Cutting Plane Theorems
- Linear-programming-based lifting and its application to primal cutting-plane algorithms
- New inequalities for finite and infinite group problems from approximate lifting
- Composite lifting of group inequalities and an application to two-row mixing inequalities
- Equivariant perturbation in Gomory and Johnson's infinite group problem (V). Software for the continuous and discontinuous 1-row case
- Equivariant perturbation in Gomory and Johnson's infinite group problem. I: The one-dimensional case
- Equivariant perturbation in Gomory and Johnson's infinite group problem. III: Foundations for the \(k\)-dimensional case with applications to \(k=2\)
- A Framework to Derive Multidimensional Superadditive Lifting Functions and Its Applications
- Lifting convex inequalities for bipartite bilinear programs
- Lifting convex inequalities for bipartite bilinear programs
- On the extreme inequalities of infinite group problems
- Relations between facets of low- and high-dimensional group problems
- Generating facets for finite master cyclic group polyhedra using \(n\)-step mixed integer rounding functions
This page was built for publication: Valid inequalities for mips and group polyhedra from approximate liftings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1016121)
