Can cut-generating functions be good and efficient?
From MaRDI portal
Abstract: Making cut generating functions (CGFs) computationally viable is a central question in modern integer programming research. One would like to find CGFs that are simultaneously good, i.e., there are good guarantees for the cutting planes they generate, and efficient, meaning that the values of the CGFs can be computed cheaply (with procedures that have some hope of being implemented in current solvers). We investigate in this paper to what extent this balance can be struck. We propose a family of CGFs which, in a sense, achieves this harmony between good and efficient. In particular, we provide a parameterized family of free sets to derive CGFs from and show that our proposed CGFs give a good approximation of the closure given by CGFs obtained from all maximal free sets and their so-called trivial liftings, and simultaneously, show that these CGFs can be computed with explicit, efficient procedures. We provide a constructive framework to identify these sets as well as computing their trivial lifting. We follow it up with computational experiments to demonstrate this and to evaluate their practical use. Our proposed family of cuts seem to give some tangible improvement on randomly generated instances compared to GMI cuts; however, in MIPLIB 3.0 instances, and vertex cover and stable problems on random graph instances, their performance is poor.
Recommendations
Cites work
- A geometric approach to cut-generating functions
- A geometric perspective on lifting
- A probabilistic analysis of the strength of the split and triangle closures
- A probabilistic comparison of split and type 1 triangle cuts for two-row mixed-integer programs
- A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts
- An algorithm for the separation of two-row cuts
- Approximation of corner polyhedra with families of intersection cuts
- Composite lifting of group inequalities and an application to two-row mixing inequalities
- Computing with multi-row gomory cuts
- Convex Analysis
- Cut-generating functions and S-free sets
- Experiments with two row tableau cuts
- Experiments with two-row cuts from degenerate tableaux
- How tight is the corner relaxation? Insights gained from the stable set problem
- scientific article; zbMATH DE number 3555734 (Why is no real title available?)
- scientific article; zbMATH DE number 1860211 (Why is no real title available?)
- Integer Programming
- Integer programming and algorithmic geometry of numbers
- Intersection cuts for single row corner relaxations
- Intersection cuts with infinite Split rank
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Lifting properties of maximal lattice-free polyhedra
- Nonunique lifting of integer variables in minimal inequalities
- On an analysis of the strength of mixed-integer cutting planes from multiple simplex tableau rows
- On the rank of disjunctive cuts
- On the relative strength of split, triangle and quadrilateral cuts
- Operations that preserve the covering property of the lifting region
- Relaxations of mixed integer sets from lattice-free polyhedra
- Some continuous functions related to corner polyhedra
- Some continuous functions related to corner polyhedra, II
- Some polyhedra related to combinatorial problems
- Stable sets, corner polyhedra and the Chvàtal closure
- Strengthening cuts for mixed integer programs
- The (not so) trivial lifting in two dimensions
- The strength of multi-row models
- Two row mixed-integer cuts via lifting
- Unique lifting of integer variables in minimal inequalities
- Unique minimal liftings for simplicial polytopes
Cited in
(3)
This page was built for publication: Can cut-generating functions be good and efficient?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4634102)
