Relations between facets of low- and high-dimensional group problems

DOI10.1007/S10107-009-0303-8MaRDI QIDQ964183zbMATH OpenOpenAlexFDO

Authors Santanu S. Dey, Jean-Philippe Richard

Publication date 15 April 2010

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-009-0303-8

zbMATH Keywords

cutting planegroup problemmixed integer programmingpolyhedronvalid inequality

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Review text

The paper studies facets of low- and high-dimensional infinite group problems which are important for deriving strong cutting planes for mixed integer programs. The authors aim to improve results obtained from one-dimensional groups by considering higher dimensional groups. They first review the group approach and prove some results that are used later to prove that certain functions are facet defining. They then introduce a sequential merge procedure, which allows to derive facets of general high-dimensional infinite group problems from facets of lower-dimensional group problems. Finally, they analyze the types of inequalities that can be generated for low-dimensional group problems using high-dimensional sequential merge group cuts.

Recommendations

• Sequential-Merge Facets for Two-Dimensional Group Problems
• Facets of Two-Dimensional Infinite Group Problems
• Generalized mixed integer rounding inequalities: Facets for infinite group polyhedra
• Facets, weak facets, and extreme functions of the Gomory-Johnson infinite group problem

Cites work

• Corner polyhedra and their connection with cutting planes
• Cutting planes in integer and mixed integer programming
• Cyclic group and knapsack facets
• Facets of Two-Dimensional Infinite Group Problems
• scientific article; zbMATH DE number 3225653 (Why is no real title available?)
• MIP: Theory and practice -- closing the gap
• Mixed-integer cuts from cyclic groups
• New inequalities for finite and infinite group problems from approximate lifting
• Non-standard approaches to integer programming
• On the extreme inequalities of infinite group problems
• On the strength of Gomory mixed-integer cuts as group cuts
• Progress in computational mixed integer programming -- a look back from the other side of the tipping point
• Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition
• Sequential-Merge Facets for Two-Dimensional Group Problems
• 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
• Two-step MIR inequalities for mixed integer programs
• Valid inequalities based on simple mixed-integer sets
• Valid inequalities for mips and group polyhedra from approximate liftings

Cited in

(9)

• Theoretical challenges towards cutting-plane selection
• Some cut-generating functions for second-order conic sets
• Design and verify: a new scheme for generating cutting-planes
• The strength of multi-row aggregation cuts for sign-pattern integer programs
• A 3-slope theorem for the infinite relaxation in the plane
• New inequalities for finite and infinite group problems from approximate lifting
• 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\)

This page was built for publication: Relations between facets of low- and high-dimensional group problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q964183)