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 costmin: 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: 1011Actual values of the variables:x                               5y                               6e1                              1e2                              0e3                              0With 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).
Elastic LP Programming
optimization;convex optimization;linear programming