Truncated Gröbner Bases for Integer Programming
Please always quote using this URN: urn:nbn:de:0297-zib-1750
- {\def\N{{\mbox{{\rm I\kern-0.22emN}}}}In this paper we introduce a multivariate grading of the toric ideal associated with the integer program $min \{ cx : Ax = b, x \in \N^n \}$, and a truncated Buchberger algorithm to solve the program. In the case of $max \{ cx : Ax \leq b, x \leq u, x \in \N^n \}$ in which all data are non-negative, this algebraic method gives rise to a combinatorial algorithm presented in UWZ94}.
Author: | Rekha R. Thomas, Robert Weismantel |
---|---|
Document Type: | ZIB-Report |
Date of first Publication: | 1995/03/23 |
Series (Serial Number): | ZIB-Report (SC-95-09) |
ZIB-Reportnumber: | SC-95-09 |
Published in: | Appeared in: Applicable Algebra in Engineering, Communication and Computing 8 (1997) 241-257 |