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  357387  Year  1997  Translation 
No  Refereed 
No 
