0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Ketcheson Apr 22 '14 at 8:18
2
$\begingroup$

No, any penalty will not do the trick. However, this is a well researched area, and goes under the name exact penalty. Basically, if the penalty is larger than a value which depends on the dual of the original problem, the solution from the model with the penalty on the slacks will coincide with the solution from the original model, when possible. I think this can be found in, e.g., "Fletcher - Practical Methods of Optimization". Otherwise, just do a search for exact penalty for slacks etc.

$\endgroup$

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.