Details:

Title	Variation of Cost Functions in Integer Programming
Author(s)	Bernd Sturmfels, Rekha R. Thomas
Type	Article in Journal
Abstract	We study the problem of minimizing c cdot x subject to A cdot x = b, x ge 0 and x integral, for a fixed matrix A. Two cost functions c and c' are considered equivalent if they give the same optimal solutions for each b. We construct a polytope St(A) whose normal cones are the equivalence classes. Explicit inequality presentations of these cones are given by the reduced Grobner bases associated with A. The union of the reduced Grobner bases as c varies (called the universal Grobner basis) consists precisely of the edge directions of St(A). We present geometric algorithms for computing St(A), the Graver basis [Gra], and the universal Grobner basis.
Length	31
File
Language	English
Journal	Mathematical Programming
Volume	77
Pages	357-387
Year	1997
Translation	No
Refereed	No