A New Variant of Buchberger's Algorithm for Integer Programming
Please always quote using this URN: urn:nbn:de:0297-zib-1570
- In this paper we modify Buchberger's $S$-pair reduction algorithm for computing a Gröbner basis of a toric ideal so as to apply to an integer program in inequality form with fixed right hand sides and fixed upper bounds on the variables. We formulate the algorithm in the original space and interpret the reduction steps geometrically. In fact, three variants of this algorithm are presented and we give elementary proofs for their correctness. A relationship between these (exact) algorithms, iterative improvement heuristics and the Kernighan-Lin procedure is established.
Download full text files
Additional Services
| Author: | Regina Urbaniak, Robert Weismantel, Günter M. Ziegler |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 1994/11/09 |
| Series (Serial Number): | ZIB-Report (SC-94-29) |
| ZIB-Reportnumber: | SC-94-29 |
| Published in: | Appeared in: SIAM J. Discrete Math. 10 (1997) pp. 96-108 |
