Solving a LP problem

[Faizan Suhail (Student)]

Hi to all,

I am trying to solve a LP problem, which is sometimes infeasible due to the constraints. I am looking for a solver in cvxpy that converges to a feasible point that minimizes the objective function even if the problem is infeasible. This scenario is similar to the implementation of linprog function from scipy package.

Please let me know if someone has information on this.

[Sergio]

Hi Faizan,

You cannot find a solution if the problem is infeasible by definition. You will have to relax some of the constraints so that the problem is feasible. This can be done by transforming the constraint into a penalty function that goes in the objective, or by adding some slack variable to the constraint and minimise its value in the objective.

Hope that helps.

Best,

Sergio

[Faizan Suhail (Student)]

Hi Sergio,

Thank you for the input. I have a similar implementation using linprog function from scipy package. What it does is that whenever the problem is infeasible, it tries to satisfy as many constraints as possible and always returns a solution. However, most of the solvers that I have used on cvxpy don't return any solution in this case. Is it possible to somehow imitate the working of linprog using cvxpy when the problem is infeasible?   

Best regards,

Faizan

[Sergio]

Hi Faizan,

I don't understand. Do you mean that the problem is actually feasible but ill conditioned so that linprog finds the solution but other solvers interfaced with cvxpy don't? If that's the case I'd suggest to try to use CPLEX from cvxpy; it is very robust.

Otherwise, if what you mean is to try to find a solution that is "as close" to the feasible set as possible, then you have to relax the constraints. 

Suppose the feasible set is expressed as: A @ x <= b and x >= 0. Let the objective be: c.T @ x. Then, the standard LP would be:

x = cvx.Variable((len_x, 1), nonneg=True)

constraints = [A@ x <= b]

problem = cvx.Problem(cvx.Minimize(c.T @ x), constraints)

If this problem is mathematically infeasible (meaning the constraints A@ x <= b and x>= 0 are mutually exclusive, and not a matter of robustness of the solver), then you could do the following. Suppose you are willing to relax the constraints A@ x <= b, but you really want to enforce that x remains nonnegative. Then, you can add epsilon as a slack variable:

x = cvx.Variable((len_x, 1), nonneg=True)

epsilon = cvx.Variable((len_b, 1), nonneg=True)

constraints = [A@ x + <= b + epsilon]

problem = cvx.Problem(cvx.Minimize(c.T @ x + cvx.sum(epsilon)), constraints)

Hope that helps.

Best,

Sergio

[Sergio]

Oops, there is a typo in the second constraints, you have to remove the + sign:

constraints = [A@ x <= b + epsilon]

Note that by adding epsilon, we are giving flexibility to the constraint, such that the right side will be arbitrarily big. Since epsilon is unbounded, this will be always feasible. In addition, since we are adding cvx.sum(epsilon) in the objective and epsilon >= 0, then we are ensuring that epsilon will grow as little as possible.

BTW, there are other ways of doing this. For example, you could solve the problem with the only constraint being A@ x <= b, and then projecting the solution on the set x>= 0. Another alternative is to remove the constraint and use it as penalty in the objective A@ x <= b, etc.

Best regards,

Sergio

[Faizan Suhail (Student)]

Hi Sergio,

Thanks a lot for the detailed response. Actually, I am trying to solve a transportation problem. Typically, when the supply is equal to the demand, the flow conservation constraints are met, the problem is feasible and both cvxpy/linprog return a solution. However, under some exceptional cases when supply != demand, the problem becomes infeasible. Linprog handles this case by satisfying as many supply/demands as possible (usually I just have one equality constraint which is not met). But cvxpy just doesn't return any solution. 

According to your suggestion, I can test the CPLEX solver first and then try to relax the constraints. I will get back after testing.

Best Regards,

Faizan    

[Sergio]

Hi Faizan,

I believe that if the problem is infeasible, scipy.optimize.linprog won't be able to behave as you describe in general. Perhaps it did as you expect in some specific problems by chance, but I wouldn't rely on that. I would suggest to double check the result you obtain with multiple problem instances, since the output you get might be just any feasible point, not the minimum required relaxation. 

Best regards,

Sergio