Determining Basic Variables of Optimal Solutions in Karmarkar's New LP Algorithm

被引：12

作者：

Kojima, Masakazu ^{[1
]}

机构：

[1] Tokyo Inst Technol, Dept Informat Sci, Meguro Ku, Tokyo 152, Japan

来源：

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

关键词：

Linear program; Karmarkar's algorithm; Optimal basis;

D O I：

10.1007/BF01840459

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper establishes a sufficient condition for a variable of a linear program to be positive at all optimal solutions. A numerical test using the condition is incorporated into Karmarkar's new LP algorithm to determine columns of optimal basis. Experimental results on the test are also reported.

引用

页码：499 / 515

页数：17