Constraint augmentation in pseudo-singularly perturbed linear programs

K. Avrachenkov, R. S. Burachik, J. A. Filar, V. Gaitsgory*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

In this paper we study a linear programming problem with a linear perturbation introduced through a parameter ε > 0. We identify and analyze an unusual asymptotic phenomenon in such a linear program. Namely, discontinuous limiting behavior of the optimal objective function value of such a linear program may occur even when the rank of the coefficient matrix of the constraints is unchanged by the perturbation. We show that, under mild conditions, this phenomenon is a result of the classical Slater constraint qualification being violated at the limit and propose an iterative, constraint augmentation approach for resolving this problem.

Original languageEnglish
Pages (from-to)179-208
Number of pages30
JournalMathematical Programming
Volume132
Issue number1-2
DOIs
Publication statusPublished - Apr 2012
Externally publishedYes

Fingerprint Dive into the research topics of 'Constraint augmentation in pseudo-singularly perturbed linear programs'. Together they form a unique fingerprint.

Cite this