AN ANALOG OF KARMARKAR ALGORITHM FOR INEQUALITY CONSTRAINED LINEAR-PROGRAMS, WITH A NEW CLASS OF PROJECTIVE TRANSFORMATIONS FOR CENTERING A POLYTOPE

被引：6
作者：
FREUND, RM
机构：
[1] MIT, Cambridge, MA, USA, MIT, Cambridge, MA, USA
来源：
OPERATIONS RESEARCH LETTERS | 1988年 / 7卷 / 01期
关键词：
KARMARKAR'S ALGORITHM - POLYTOPE - PROJECTIVE TRANSFORMATION;
D O I：
10.1016/0167-6377(88)90045-4
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
The methodology presented herein can be used to translate other results regarding Karmarkar's algorithm to the space of linear inequality constraints. Although it is assumed that the objective function failure is known in advance, this assumption can be relaxed. The results on objective function value bounding, dual variables, fractional programming, and acceleration techniques all should carry over to the space of linear inequality constraints.
引用
收藏
页码：9 / 13
页数：5
相关论文
共 10 条
[1]   A Monotonic Projective Algorithm for Fractional Linear Programming [J].
Anstreicher, Kurt M. .
ALGORITHMICA, 1986, 1 (1-4) :483-498
[2]  
BAYER DA, 1987, KARMARKARS LINEAR PR
[3]  
GAY DA, 1987, 136 AT T BELL LAB CO
[4]   A VARIANT OF KARMARKAR LINEAR-PROGRAMMING ALGORITHM FOR PROBLEMS IN STANDARD FORM [J].
GAY, DM .
MATHEMATICAL PROGRAMMING, 1987, 37 (01) :81-90
[5]  
Grunbaum B, 1967, CONVEX POLYTOPES
[6]  
LAGARIAS JC, 1987, NONLINEAR GEOMETRY L, V3
[7]  
SONNEVEND G, 1985, 12TH P IFIP C SYST M
[8]   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
[9]  
TODD MJ, 1986, UNPUB IMPROVED BOUND
[10]  
YE Y, 1987, UNPUB DUAL APPROACH
1