ON ADAPTIVE-STEP PRIMAL-DUAL INTERIOR-POINT ALGORITHMS FOR LINEAR-PROGRAMMING

被引：219

作者：

MIZUNO, S

TODD, MJ

YE, YY

机构：

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

[2] UNIV IOWA,DEPT MANAGEMENT SCI,IOWA CITY,IA 52242

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 1993年 / 18卷 / 04期

关键词：

LINEAR PROGRAMMING; INTERIOR POINT ALGORITHMS; PATH-FOLLOWING ALGORITHMS; POTENTIAL REDUCTION ALGORITHMS;

D O I：

10.1287/moor.18.4.964

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We describe several adaptive-step primal-dual interior point algorithms for linear programming. All have polynomial time complexity while some allow very long steps in favorable circumstances. We provide heuristic reasoning for expecting that the algorithms will perform much better in practice than guaranteed by the worst-case estimates, based on an analysis using a nonrigorous probabilistic assumption.

引用

页码：964 / 981

页数：18

共 31 条

[1] LONG STEPS IN AN O(N3L) ALGORITHM FOR LINEAR-PROGRAMMING [J].