| 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: |
Aquest material està protegit per drets d'autor i/o drets afins. Podeu utilitzar aquest material en funció del que permet la legislació de drets d'autor i drets afins d'aplicació al vostre cas. Per a d'altres usos heu d'obtenir permís del(s) titular(s) de drets.  |
| Llengua: |
Anglès |
| Document: |
Article ; recerca ; Versió publicada |
| Matèria: |
Programació (Matemàtica) |
| Publicat a: |
Mathematical Programming, vol. 77 n. 3 (1997) p. 357-387, ISSN 0025-5610 |
visitant ::
identificació
Accés restringit a la UAB
