A new algebraic geometry algorithm for integer programming

被引：15

作者：

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 [J].

TAYUR, SR ;

THOMAS, RR ;

NATRAJ, NR .

MATHEMATICAL PROGRAMMING, 1995, 69 (03) :369-401

[10] A geometric Buchberger algorithm for integer programming [J].

Thomas, RR .

MATHEMATICS OF OPERATIONS RESEARCH, 1995, 20 (04) :864-884

← 1 2 →