Variation of cost functions in integer programming
Sturmfels, Bernd
Thomas, Rekha R.

Data: 1997
Resum: We study the problem of minimizing c · x subject to A · x = b, x >= 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 Gröbner bases associated with A. The union of the reduced Gröbner bases as c varies (called the universal Gröbner basis) consists precisely of the edge directions of St(A). We present geometric algorithms for computing St(A), the Graver basis, and the universal Gröbner basis. .
Drets: Tots els drets reservats.
Llengua: Anglès
Document: Article ; recerca ; Versió publicada
Publicat a: Mathematical Programming, vol. 77 n. 3 (1997) p. 357-387, ISSN 0025-5610



31 p, 1.6 MB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2023-06-03



   Favorit i Compartir