# Minimally relaxing an infeasible linear program

I am trying to debug a piece of code to 'relax' an infeasible linear program formulated in the standard formulation

Program 1 (that we assume infeasible):

$max/min$ $c^{T}r \\ s.t. Ar \leq, =, \geq b\\ l \leq r \leq u$

The following problem would find the minimum set of relaxation on upper and lower bounds and constraints of problem 1 to make it feasible.

Program 2

$min$ $c^T r + \lambda ||v||_0 + \alpha (||p||_0 + ||q||_0) \\ s.t. A r + v \leq, =, \geq b \\ l - p \leq r \leq u + q \\ v \in R^m \\ p,q \in R_+^n$

Now my question is:

Does the solution to problem 2 ensure solely a minimal set of bounds and constraints to relax? e.g. variable 2 should be relaxed.

Or

Does problem 2 find a set of bounds and constraints to relax and the minimal set of adjustements on the those bounds and constraints to find a feasible LP? e.g. variable 2 should be relaxed by a minimum of 2 units.

• Why should program 1 not be feasible? Take $l\leq r$ and $-u\leq -r$. – Wuestenfux Jul 20 '17 at 13:58
• let's assume for a second that it isn't feasible given the bounds and constraints in Program 1 generally formulated. – Marouen Jul 20 '17 at 13:59
• First of all: please do not use $\|\cdot\|_0$. The cardinality function is not a norm. Use $\mathop{\textrm{card}}(\cdot)$ instead. And secondly---the cardinality function is not convex. So while yes, your does find a "minimal" relaxation in some sense of the term, it's also intractable, whereas the original problem was not. – Michael Grant Jul 21 '17 at 19:20
• You might also be interested in the notion of a "Minimum Irreducible Infeasible Subset". Your model above looks for the minimum number of constraints that must be deleted to make the problem feasible. An MIIS is different: it looks for the minimum number of constraints that by themselves are infeasible. That is not the same thing! – Michael Grant Jul 22 '17 at 15:00
• thanks, this is interesting, would you have references about MIIS for me? – Marouen Jul 22 '17 at 23:15