Constraint augmentation in pseudo-singularly perturbed linear programs
成果类型：
Article
署名作者：
Avrachenkov, K.; Burachik, R. S.; Filar, J. A.; Gaitsgory, V.
署名单位：
University of South Australia; Inria
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-010-0388-0
发表日期：
2012
页码：
179-208
关键词：
摘要：
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.