A New Algebraic Geometry Algorithm for Integer Programming
Dimitris Bertsimas, Georgia Perakis, Sridhar Tayur
Management Science · 2000 · Volume 46 · Issue 7
DOI: 10.1287/mnsc.46.7.999.12033
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
integer programming, algebraic geometry, Groebner basis
Enable JavaScript for citation tools and additional paper interactions.