A New Algebraic Geometry Algorithm for Integer Programming

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.

• 저널Management Science · 46(7) · 999–1008
• 토픽Advanced Graph Theory Research · Computational Theory and Mathematics
• DOI10.1287/mnsc.46.7.999.12033
• 저자Dimitris Bertsimas, Georgia Perakis, Sridhar Tayur