CODEWITHSUNDEEP
pythonmathematical-optimizationpulpmixed-integer-programming
K N Reddy
K N Reddy

Reputation: 13

Identifying infeasibility constraint and relaxing/removing it in Python using Pulp?

I am tried to solve a MILP problem using python pulp and The solution is infeasible. So, I want to find where infeasibility is coming and want to relax it or remove it to find feasible solution. it is difficult to check manually in the LP file bcz large number of constraints are present. So How I can handle this issue?

I went through some articles they mentioned that check manually in the LP file but it is very difficult to do manually for a huge number of variables/constraints.

It is giving just infeasibility

Upvotes: 1

Views: 4169

Answers (2)

seimetz
seimetz

Reputation: 171

I use some rule of thumbs to check infeasibility.

  • Always start with a small data set that you can inspect more manually.

  • After relax all integer variables. If this relaxation is infeasible, your problem is linear infeasible. You might have constraints saying stuff like x > 3 and x < 2;

  • If the linear relaxation is feasible, then deactivate each constraint once. Frequently you find some obvious constraints being infeasible, such as sum(i,x_i) = 1. But if you deactivate one by one, you may find that another more complex constraint set is causing infeasibility, and there you might investigate better.

Upvotes: 0

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

In general, this is not so easy. Some pointers:

  • If you can construct a feasible but not necessarily optimal solution for your problem, plug this in and you will find the culprits very easily.
  • Some advanced solvers have tools that can help (IIS, Conflict refiner). They may or may not point to the real problem.
  • Note that the model can be LP infeasible or just integer infeasible.
  • In some cases it is possible just to relax a suspect block of constraints and see what happens.
  • A more structural approach I often use is to formulate an elastic model: allow constraints to be violated but at a cost. This often makes some economic sense: hire temp workers, rent extra capacity, buy from 3rd parties etc.

Upvotes: 2

Related Questions