# Constraint augmentation in pseudo-singularly perturbed linear programs

1 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In this paper we study a linear programming problem with a linear perturbation introduced through a parameter $\epsilon > 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.
Document type :
Journal articles

https://hal.inria.fr/hal-00764284
Contributor : Konstantin Avrachenkov <>
Submitted on : Wednesday, December 12, 2012 - 4:33:38 PM
Last modification on : Thursday, September 24, 2020 - 10:22:03 AM

### Citation

Konstantin Avrachenkov, Regina Burachik, Jerzy Filar, Vladimir Gaitsgory. Constraint augmentation in pseudo-singularly perturbed linear programs. Mathematical Programming, Series A, Springer, 2012, 132 (1-2), pp.179-208. ⟨10.1007/s10107-010-0388-0⟩. ⟨hal-00764284⟩

Record views