Variation of cost functions in integer programming |
| |
Authors: | Bernd Sturmfels Rekha R. Thomas |
| |
Affiliation: | (1) Department of Mathematics, University of California ai Berkeley, 94720 Berkeley, CA, USA;(2) Department of Mathematics, Texas A&M University, 77843 College Station, TX, USA |
| |
Abstract: | We study the problem of minimizingc · x subject toA · x =b. x ≥ 0 andx integral, for a fixed matrixA. Two cost functionsc andc′ are considered equivalent if they give the same optimal solutions for eachb. We construct a polytopeSt(A) whose normal cones are the equivalence classes. Explicit inequality presentations of these cones are given by the reduced Gröbner bases associated withA. The union of the reduced Gröbner bases asc varies (called the universal Gröbner basis) consists precisely of the edge directions ofSt(A). We present geometric algorithms for computingSt(A), the Graver basis, and the universal Gröbner basis. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|