A new algebraic geometry algorithm for integer programming

被引：14

作者：

Bertsimas, D ^{[1
]}

Perakis, G

Tayur, S

机构：

[1] MIT, Alfred P Sloan Sch Management, Cambridge, MA 02139 USA

[2] Carnegie Mellon Univ, Grad Sch Ind Adm, Pittsburgh, PA 15213 USA

来源：

MANAGEMENT SCIENCE | 2000年 / 46卷 / 07期

关键词：

integer programming; algebraic geometry; Groebner basis;

D O I：

10.1287/mnsc.46.7.999.12033

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：999 / 1008

页数：10

共 12 条

[1] [Anonymous], 1998, USING ALGEBRAIC GEOM, DOI DOI 10.1007/978-1-4757-6911-1
[2] Bertsimas D., 1997, Introduction to linear optimization
[3] CONTI P, 1991, LECT NOTES COMPUT SC, V539, P130
[4] Cox D., 1997, UNDERGRADUATE TEXTS, V2nd edn
[5] LOVASZ L, 1982, ANN DISCRETE MATH, V16, P213
[6] Nemhauser GL, 1988, INTEGER COMBINATORIA
[7] Papadimitriou Christos H., 1981, Combinatorial Optimization: Algorithms and Complexity
[8] Pitassi Toniann, 1996, DESCRIPTIVE COMPLEXI, P215
[9] AN ALGEBRAIC-GEOMETRY ALGORITHM FOR SCHEDULING IN PRESENCE OF SETUPS AND CORRELATED DEMANDS
TAYUR, SR
THOMAS, RR
NATRAJ, NR
[J]. MATHEMATICAL PROGRAMMING, 1995, 69 (03) : 369 - 401
[10] A geometric Buchberger algorithm for integer programming
Thomas, RR
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1995, 20 (04) : 864 - 884

← 1 2 →