# Elastic LP Programming

Say I have an LP that is unfeasible and that I want to find the solution that makes it feasible without strongly violating the current constraints.

What is a principled way of solving this problem, and how can I know a posteriori what constraints would have to be violated?

I found the following example, but it is unclear to me how would one proceed to choose a good value for the penalty to the elastic variables. More concretely:

1. Is any penalty to the slack variables enough? How can I choose a "significant cost" for my slack variables?
2. What is a principled way of setting up the cost coefficients of the slack variables?
3. Is it always the case that, anytime a slack variable in the solution is positive, the corresponding original constraint was infeasible?
min: x + y;
c1: x >= 6;
c2: y >= 6;
c3: x + y <= 11;


This model is clearly infeasible. We can now introduce slack variables at a significant cost

min: x + y + 1000 e1 + 1000 e2 + 1000 e3;
c1: x1 + e1 >= 6;
c2: y + e2 >= 6;
c3: x + y - e3 <= 11;


The result of this model is:

Value of objective function: 1011


Actual values of the variables:

x                               5
y                               6
e1                              1
e2                              0
e3                              0


With this simple example model, multiple solutions were possible. Here, the first constraint was relaxed since e1 is non-zero. Only this one constraint had to be relaxed to make the model feasible. The objective value of 1011 isn't saying very much. However if we subtract 1000 e1 + 1000 e2 + 1000 e3 from it, then it becomes 11 which is the value of the original objective function (x + y).

• Maybe I've misunderstood, but it seems like you're asking us to define a new optimization problem for you. There is no one "right" redefinition of the problem, and someone who knows the specifics of the problem's application is more likely to come up with a "good" redefinition. – David Ketcheson Apr 22 '14 at 8:18