A PROJECTIVE ALGORITHM FOR LINEAR-PROGRAMMING WITH NO REGULARITY CONDITION

被引：2
作者：
VIAL, JP
机构：
[1] Département d'Economie Commerciale et Industrielle, Université de Genève, Geneva
来源：
OPERATIONS RESEARCH LETTERS | 1992年 / 12卷 / 01期
关键词：
LINEAR PROGRAMMING; INTERIOR POINT ALGORITHM; COMBINED PHASE-I PHASE-II; REGULARITY CONDITION;
D O I：
10.1016/0167-6377(92)90014-T
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
The combined phase I-phase II projective algorithm of de Ghellinck and Vial solves any linear programming problem in its primal-dual formulation, without assuming any regularity condition. The method does not require artificial variables and/or constraints. It consists simply in minimizing the sum of all primal and dual variables. The present note is an alternative to a recent proposal of Anstreicher.
引用
收藏
页码：1 / 2
页数：2
相关论文
共 6 条
[1]  
ANSTREICHER K, 1991, UNPUB INTERIOR ALGOR
[2]   A Polynomial Newton Method for Linear Programming [J].
de Ghellinck, Guy ;
Vial, Jean-Philippe .
ALGORITHMICA, 1986, 1 (1-4) :425-453
[3]   AN EXTENSION OF KARMARKAR ALGORITHM FOR SOLVING A SYSTEM OF LINEAR HOMOGENEOUS EQUATIONS ON THE SIMPLEX [J].
DEGHELLINCK, G ;
VIAL, JP .
MATHEMATICAL PROGRAMMING, 1987, 39 (01) :79-92
[4]   A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING [J].
KARMARKAR, N .
COMBINATORICA, 1984, 4 (04) :373-395
[5]   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
[6]  
VIAL JP, 1989, LECT NOTES MATH, V1405, P191
1