SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS USING KARMARKAR ALGORITHM

被引：52

作者：

MITCHELL, JE ^{[1
]}

TODD, MJ ^{[1
]}

机构：

[1] CORNELL UNIV,SCH OPERAT RES & IND ENGN,ITHACA,NY 14853

来源：

MATHEMATICAL PROGRAMMING | 1992年 / 56卷 / 03期

关键词：

COMBINATORIAL OPTIMIZATION; INTEGER PROGRAMMING; KARMARKAR METHOD;

D O I：

10.1007/BF01580902

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We describe a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.

引用

页码：245 / 284

页数：40

共 48 条

[1] AN IMPLEMENTATION OF KARMARKAR ALGORITHM FOR LINEAR-PROGRAMMING [J].

ADLER, I ;

RESENDE, MGC ;

VEIGA, G ;

KARMARKAR, N .

MATHEMATICAL PROGRAMMING, 1989, 44 (03) :297-335

[2] A Monotonic Projective Algorithm for Fractional Linear Programming [J].

Anstreicher, Kurt M. .

ALGORITHMICA, 1986, 1 (1-4) :483-498

[3] THE NONLINEAR GEOMETRY OF LINEAR-PROGRAMMING .2. LEGENDRE TRANSFORM COORDINATES AND CENTRAL TRAJECTORIES [J].

BAYER, DA ;

LAGARIAS, JC .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1989, 314 (02) :527-581

[4] THE NONLINEAR GEOMETRY OF LINEAR-PROGRAMMING .1. AFFINE AND PROJECTIVE SCALING TRAJECTORIES [J].

BAYER, DA ;

LAGARIAS, JC .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1989, 314 (02) :499-526

[5]

BORCHERS B, 1991, 195 MATH SCI RENSS P

[6]

CHOI IC, 1990, LORSA J COMPUTING, V2, P304

[7]

Christofides N, 1976, WORST CASE ANAL NEW

[8]

DANTZIG G.B., 1951, ACTIVITY ANAL PRODUC, P339

[9]

DDERIGS U, 1986, COMPUTING, V3, P263

[10] A SURVEY OF SEARCH DIRECTIONS IN INTERIOR POINT METHODS FOR LINEAR-PROGRAMMING [J].

DENHERTOG, D ;

ROOS, C .

MATHEMATICAL PROGRAMMING, 1991, 52 (03) :481-509

← 1 2 3 4 5 →