Gröbner bases of lattices, corner polyhedra, and integer programming
type: Item
instance of: scholarly article
title: Gröbner bases of lattices, corner polyhedra, and integer programming
zbMATH Open document ID: 0863.90115
author: Bernd Sturmfels
author: Robert Weismantel
author: Günter M. Ziegler
published in: Beiträge zur Algebra und Geometrie
publication date: 1996-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/223420
full work available at URL: no.2
review text: 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.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 52C07
Mathematics Subject Classification ID: 52B20
Mathematics Subject Classification ID: 13P10
zbMATH DE Number: 821696
zbMATH Keywords: integer lattices
zbMATH Keywords: associated ideals
zbMATH Keywords: polyhedra
zbMATH Keywords: Gröbner bases
zbMATH Keywords: corner polyhedra
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 821696