Affine-scaling for linear programs with free variables

R. J. Vanderbei

doi:10.1007/BF01582276

Affine-scaling for linear programs with free variables

R. J. Vanderbei

Research output: Contribution to journal › Article › peer-review

31 Scopus citations

Abstract

The affine-scaling modification of Karmarkar's algorithm is extended to solve problems with free variables. This extended primal algorithm is used to prove two important results. First the geometrically elegant feasibility algorithm proposed by Chandru and Kochar is the same algorithm as the one obtained by appending a single column of residuals to the constraint matrix. Second the dual algorithm as first described by Adler et al., is the same as the extended primal algorithm applied to the dual.

Original language	English (US)
Pages (from-to)	31-44
Number of pages	14
Journal	Mathematical Programming
Volume	43
Issue number	1-3
DOIs	https://doi.org/10.1007/BF01582276
State	Published - Jan 1989
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Keywords

Affine-scaling
Karmarkar's algorithm
dual algorithm
feasibility algorithm

Access to Document

10.1007/BF01582276

Cite this

@article{d6e72371dcbc4e3189efc41beca9a614,

title = "Affine-scaling for linear programs with free variables",

abstract = "The affine-scaling modification of Karmarkar's algorithm is extended to solve problems with free variables. This extended primal algorithm is used to prove two important results. First the geometrically elegant feasibility algorithm proposed by Chandru and Kochar is the same algorithm as the one obtained by appending a single column of residuals to the constraint matrix. Second the dual algorithm as first described by Adler et al., is the same as the extended primal algorithm applied to the dual.",

keywords = "Affine-scaling, Karmarkar's algorithm, dual algorithm, feasibility algorithm",

author = "Vanderbei, {R. J.}",

year = "1989",

month = jan,

doi = "10.1007/BF01582276",

language = "English (US)",

volume = "43",

pages = "31--44",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1-3",

}

TY - JOUR

T1 - Affine-scaling for linear programs with free variables

AU - Vanderbei, R. J.

PY - 1989/1

Y1 - 1989/1

N2 - The affine-scaling modification of Karmarkar's algorithm is extended to solve problems with free variables. This extended primal algorithm is used to prove two important results. First the geometrically elegant feasibility algorithm proposed by Chandru and Kochar is the same algorithm as the one obtained by appending a single column of residuals to the constraint matrix. Second the dual algorithm as first described by Adler et al., is the same as the extended primal algorithm applied to the dual.

AB - The affine-scaling modification of Karmarkar's algorithm is extended to solve problems with free variables. This extended primal algorithm is used to prove two important results. First the geometrically elegant feasibility algorithm proposed by Chandru and Kochar is the same algorithm as the one obtained by appending a single column of residuals to the constraint matrix. Second the dual algorithm as first described by Adler et al., is the same as the extended primal algorithm applied to the dual.

KW - Affine-scaling

KW - Karmarkar's algorithm

KW - dual algorithm

KW - feasibility algorithm

UR - http://www.scopus.com/inward/record.url?scp=0024303447&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024303447&partnerID=8YFLogxK

U2 - 10.1007/BF01582276

DO - 10.1007/BF01582276

M3 - Article

AN - SCOPUS:0024303447

SN - 0025-5610

VL - 43

SP - 31

EP - 44

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-3

ER -

Affine-scaling for linear programs with free variables

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this