An asymptotic simplex method for parametric linear programming

Author

Filar, J.A. ; Avrachenkov, K.E. ; Altman, E.

Author_Institution

Sch. of Math., Univ. of South Australia, The Levels, SA, Australia

fYear

1999

fDate

1999

Firstpage

427

Lastpage

432

Abstract

We study singularly perturbed linear programs. These are parametric linear programs whose constraints become linearly dependent when the perturbation parameter goes to zero. Problems like that were studied by Jeroslow (1973). He proposed simplex-like method, which works over the field of rational functions. Here we develop an alternative asymptotic simplex method based on Laurent series expansions. This approach appears to be more computationally efficient. In addition, we point out several possible generalizations of our method and provide new simple updating formulae for the perturbed solution

Keywords

computational complexity; linear programming; rational functions; singularly perturbed systems; LP; Laurent series expansions; asymptotic simplex method; computational efficiency; linearly dependent constraints; parametric linear programming; rational functions; singularly perturbed linear programs; Australia Council; Electronic mail; Functional programming; Linear programming; Mathematics; Polynomials; Sensitivity analysis; Vectors;

fLanguage

English

Publisher

ieee

Conference_Titel

Information, Decision and Control, 1999. IDC 99. Proceedings. 1999

Conference_Location

Adelaide, SA

Print_ISBN

0-7803-5256-4

Type

conf

DOI

10.1109/IDC.1999.754195

Filename

754195