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
Anstreicher, Kurt M.
[J]. 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
GAY, DM
[J]. 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
Todd, Michael J.
Burrell, Bruce P.
[J]. ALGORITHMICA, 1986, 1 (1-4) : 409 - 424
[9] TODD MJ, 1986, UNPUB IMPROVED BOUND
[10] YE Y, 1987, UNPUB DUAL APPROACH

← 1 →