A new algebraic geometry algorithm for integer programming

Authors
Bertsimas, D Perakis, G Tayur, S
Citation
D. Bertsimas et al., A new algebraic geometry algorithm for integer programming, MANAG SCI, 46(7), 2000, pp. 999-1008
Citations number
12
Categorie Soggetti
Management
Journal title
MANAGEMENT SCIENCE
ISSN journal
00251909 → ACNP
Volume
46
Issue
7
Year of publication
2000
Pages
999 - 1008
Database
ISI
SICI code
0025-1909(200007)46:7<999:ANAGAF>2.0.ZU;2-1
Abstract
We propose a new algorithm for solving integer programming (IP) problems th at 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 se nsitivity analysis, offers a systematic enumeration of all feasible solutio ns, and gives structural information of the feasible set of a given IP. We provide several examples that offer insights on the algorithm and its prope rties.