Gröbner bases of lattices, corner polyhedra, and integer programming
Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Integer programming (90C10)
There are very close connections between the arithmetic of integer lattices, algebraic properties of the associated ideals, and the geometry and the combinatorics of corresponding polyhedra. In this paper, we investigate the generating sets (``Gröbner bases) of integer lattices that correspond to the Gröbner bases of the associated binomial ideals. Extending results by Sturmfels\&Thomas, we obtain a geometric characterization of the universal Gröbner basis in terms of the vertices and edges of the associated corner polyhedra. In the special case where the lattice has finite index, the corner polyhedra were studied by Gomory, and there is a close connection to the ``group problem in integer programming. We present exponential lower and upper bounds for the maximal size of a reduced Gröbner basis. The initial complex of (the ideal of) a lattice is shown to be dual to the boundary of a certain simple polyhedron.
- Triple-loop networks with arbitrarily many minimum distance diagrams
- On the complexity of smooth projective toric varieties
- Standard pairs and group relaxations in integer programming
- Test sets of integer programs
- Test sets for integer programs
- The Hilbert zonotope and a polynomial time algorithm for universal Gröbner bases.
- The vertex ideal of a lattice.
- Universal Gröbner basis associated with the maximum flow problem
- Lattice polytopes from Schur and symmetric Grothendieck polynomials
- Fibers of multi-way contingency tables given conditionals: relation to marginals, cell bounds and Markov bases
- Minimal generating sets of lattice ideals
- Alternatives for testing total dual integrality
- Computing the integer programming gap
- Computing the algebraic relations of \(C\)-finite sequences and multisequences
- On Lawrence semigroups
- Test sets for vertex cover problems
- Border bases for lattice ideals
- Cellular resolutions of monomial modules
- scientific article; zbMATH DE number 1276818 (Why is no real title available?)
- Computing Gröbner bases of pure binomial ideals via submodules of Z^n
- scientific article; zbMATH DE number 1163420 (Why is no real title available?)
- scientific article; zbMATH DE number 2019945 (Why is no real title available?)
- Standard pairs for lawrence-type matrices and their applications to several lawrence-type integer programs
- Regular decomposition in integer programming
- scientific article; zbMATH DE number 835749 (Why is no real title available?)
- Toric varieties from cyclic matrix semigroups
- GRIN: an implementation of Gröbner bases for integer programming
- Convex Polytopes and Gröbner Bases
- The combinatorics of modeling and analyzing biological systems
- Linear label code of a root lattice using Gröbner bases
- Equivariant lattice bases
- Non-standard approaches to integer programming
- PALP: a package for analysing lattice polytopes with applications to toric geometry
- Computing generating sets of lattice ideals and Markov bases of lattices
This page was built for publication: Gröbner bases of lattices, corner polyhedra, and integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1903365)
