An Extension of Karmarkar's Algorithm for Linear Programming Using Dual Variables

被引：90

作者：

Todd, Michael J. ^{[1
]}

Burrell, Bruce P. ^{[1
]}

机构：

[1] Cornell Univ, Coll Engn, Sch Operat Res & Ind Engn, Ithaca, NY 14850 USA

来源：

ALGORITHMICA | 1986年 / 1卷 / 1-4期

关键词：

Linear programming; Karmarkar's algorithm; Duality;

D O I：

10.1007/BF01840455

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We describe an extension of Karmarkar's algorithm for linear programming that handles problems with unknown optimal value and generates primal and dual solutions with objective values converging to the common optimal primal and dual value. We also describe an implementation for the dense case and show how extreme point solutions can be obtained naturally, with little extra computation.

引用

页码：409 / 424

页数：16

共 18 条

[1]

ANSTREICHER KM, 1985, ANAL KARMARKAR UNPUB

[2]

Charnes A., 2010, NAV RES LOG, V9, P181, DOI DOI 10.1002/NAV.3800090303

[3]

CHARNES A, 1984, EXPLICIT SOLUT UNPUB

[4]

Chvatal V., 1983, LINEAR PROGRAMMING

[5]

Frisch K.R., 1955, LOGARITHMIC PO UNPUB

[6]

GAY D, 1985, VARIANT KARMAR UNPUB

[7] SOLUTION OF SPARSE LINEAR LEAST-SQUARES PROBLEMS USING GIVENS ROTATIONS [J].

GEORGE, A ;

HEATH, MT .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1980, 34 (DEC) :69-83

[8]

GILL PE, 1985, PROJECTED NEWT UNPUB

[9]

Golub G. H., 2013, MATRIX COMPUTATIONS, V3

[10]

GONZAGA C, 1985, CONICAL PROJEC UNPUB

← 1 2 →