Constraint augmentation in pseudo-singularly perturbed linear programs

Konstantin Avrachenkov 1 Regina Burachik 2 Jerzy Filar 2 Vladimir Gaitsgory 2
1 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
2 University of South Australia [Adelaide]
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.
Type de document :
Article dans une revue
Mathematical Programming, Series A, Springer, 2012, 132 (1-2), pp.179-208. 〈10.1007/s10107-010-0388-0〉
Liste complète des métadonnées
https://hal.inria.fr/hal-00764284
Contributeur : Konstantin Avrachenkov <>
Soumis le : mercredi 12 décembre 2012 - 16:33:38
Dernière modification le : samedi 27 janvier 2018 - 01:31:43

Lien texte intégral

istex

Identifiants

Collections

INRIA

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

184

Contact


archive-ouverte@inria.fr