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.


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.

  • $\begingroup$ Why should program 1 not be feasible? Take $l\leq r$ and $-u\leq -r$. $\endgroup$ – Wuestenfux Jul 20 '17 at 13:58
  • $\begingroup$ let's assume for a second that it isn't feasible given the bounds and constraints in Program 1 generally formulated. $\endgroup$ – Marouen Jul 20 '17 at 13:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Grant Jul 21 '17 at 19:20
  • 1
    $\begingroup$ 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! $\endgroup$ – Michael Grant Jul 22 '17 at 15:00
  • $\begingroup$ thanks, this is interesting, would you have references about MIIS for me? $\endgroup$ – Marouen Jul 22 '17 at 23:15

So the answer would be that Program 2 finds the minimal cardinality solution without necessarily ensuring a minimal adjustement to the bounds andconstraints.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.