A New Algebraic Geometry Algorithm for Integer Programming
Authors:
- 1 July 2000
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 46 (7) , 999-1008
Abstract
We propose a new algorithm for solving integer programming (IP) problems that is based on ideas from algebraic geometry. The method provides a natural generalization of the Farkas lemma for IP, leads to a way of performing sensitivity analysis, offers a systematic enumeration of all feasible solutions, and gives structural information of the feasible set of a given IP. We provide several examples that offer insights on the algorithm and its properties.Keywords
This publication has 9 references indexed in Scilit:
- Using Algebraic Geometry1998
- Truncated Gröbner Bases for Integer ProgrammingApplicable Algebra in Engineering, Communication and Computing, 1997
- Algebraic propositional proof systems1997
- A Variant of the Buchberger Algorithm for Integer ProgrammingSIAM Journal on Discrete Mathematics, 1997
- Ideals, Varieties, and Algorithms1997
- A Geometric Buchberger Algorithm for Integer ProgrammingMathematics of Operations Research, 1995
- An algebraic geometry algorithm for scheduling in presence of setups and correlated demandsMathematical Programming, 1995
- Buchberger algorithm and integer programming1991
- Integer and Combinatorial Optimization1988