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 条

[41]

Papadimitriou C. H., 1998, COMBINATORIAL OPTIMI

[42]

STEGER AE, 1985, THESIS STATE U NEW Y

[43] An Extension of Karmarkar's Algorithm for Linear Programming Using Dual Variables [J].

Todd, Michael J. ;

Burrell, Bruce P. .

ALGORITHMICA, 1986, 1 (1-4) :409-424

[44] A Modification of Karmarkar's Linear Programming Algorithm [J].

Vanderbei, Robert J. ;

Meketon, Marc S. ;

Freedman, Barry A. .

ALGORITHMICA, 1986, 1 (1-4) :395-407

[45] A POTENTIAL REDUCTION ALGORITHM ALLOWING COLUMN GENERATION [J].

Ye, Yinyu .

SIAM JOURNAL ON OPTIMIZATION, 1992, 2 (01) :7-20

[46]

YE YY, 1987, MATH PROGRAM, V39, P305, DOI 10.1007/BF02592079

[47]

1985, SAS USERS GUIDE VERS

[48]

1990, CS2305191 PUBL

← 1 2 3 4 5 →