A New Algebraic Geometry Algorithm for Integer Programming

Dimitris Bertsimas, Georgia Perakis and Sridhar Tayur
Additional contact information
Dimitris Bertsimas: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Georgia Perakis: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Sridhar Tayur: Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

Management Science, 2000, vol. 46, issue 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: integer programming; algebraic geometry; Groebner basis (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.46.7.999.12033 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:46:y:2000:i:7:p:999-1008

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().