Constraint augmentation in pseudo-singularly perturbed linear programs (Q2429463)

The paper concerns linear programmes with perturbed constraints and objective function introduced by a scalar parameter \(\varepsilon > 0\) and discusses the situation that the limit of the feasible set as \(\varepsilon \rightarrow 0\) (and the limit of the optimal value) exist but are different from the feasible set and optimal value of the unperturbed problem. It is shown that under certain assumptions (including an extended Slater condition) the limiting feasible set and optimal objective value are given by an LP with an additional layer of constraints added to the unperturbed LP. The authors then investigate the case when the extended Slater condition does not hold. They prove that adding additional layers of constraints yields a more general result. Finally a lexicographic Slater condition is defined, which is shown to be equivalent to the Slater condition for the perturbed problem and also leads to the limiting LP.