Constructing lattice-free gradient polyhedra in dimension two
From MaRDI portal
Publication:2118128
Abstract: Lattice-free gradient polyhedra can be used to certify optimality for mixed-integer convex minimization models. We consider how to construct these polyhedra for unconstrained models with two integer variables under the assumption that all level sets are bounded. A classic result of Bell, Doignon, and Scarf states that a lattice-free gradient polyhedron with at most four facets exists in this setting. We present an algorithm for creating a sequence of gradient polyhedra, each of which has at most four facets, that finitely converges to a lattice-free gradient polyhedron. Each update requires constantly many gradient evaluations. Our updates imitate the gradient descent algorithm, and consequently, it yields a gradient descent type of algorithm for problems with two integer variables.
Recommendations
- Constructing lattice-free gradient polyhedra in dimension two
- Relaxations of mixed integer sets from lattice-free polyhedra
- Relaxations of mixed integer sets from lattice-free polyhedra
- Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three
- The triangle closure is a polyhedron
Cites work
- A geometric approach to cut-generating functions
- A Theorem Concerning the Integer Lattice
- An algorithmic framework for convex mixed integer nonlinear programs
- An observation on the structure of production sets with indivisibilities
- An outer-approximation algorithm for a class of mixed-integer nonlinear programs
- Branch and Bound Experiments in Convex Nonlinear Integer Programming
- Convexity in cristallographical lattices
- Duality for mixed-integer convex minimization
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- Geometric algorithms and combinatorial optimization
- scientific article; zbMATH DE number 4119933 (Why is no real title available?)
- scientific article; zbMATH DE number 1860211 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- Inequalities from Two Rows of a Simplex Tableau
- Integrating SQP and branch-and-bound for mixed integer nonlinear programming
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Lifting Integer Variables in Minimal Inequalities Corresponding to Lattice-Free Triangles
- Maximal lattice-free convex sets in linear subspaces
- Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three
- Mirror-Descent Methods in Mixed-Integer Convex Optimization
- Notions of Maximality for Integral Lattice-Free Polyhedra: The Case of Dimension Three
- Optimality certificates for convex minimization and Helly numbers
- Relaxations of mixed integer sets from lattice-free polyhedra
- Unique minimal liftings for simplicial polytopes
Cited in
(5)- Constructing lattice-free gradient polyhedra in dimension two
- Towards a characterization of maximal quadratic-free sets
- Enumeration and unimodular equivalence of empty delta-modular simplices
- Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube
- A characterization of maximal homogeneous-quadratic-free sets
This page was built for publication: Constructing lattice-free gradient polyhedra in dimension two
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118128)
