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:
- Is any penalty to the slack variables enough? How can I choose a "significant cost" for my slack variables?
- What is a principled way of setting up the cost coefficients of the slack variables?
- 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).