CODEWITHSUNDEEP
cplexampl
Nabilah M. Syukur
Nabilah M. Syukur

Reputation: 31

What constraints make my problem infeasible?

I'm using CPLEX 12.8 for modelling my thesis project and I have a problem that I cannot solve. I get the following output: 

CPLEX 12.8.0.0: integer infeasible.
1828 MIP simplex iterations
316 branch-and-bound nodes
No basis.

Is there any way to know which constraints are contradicting each other?

Upvotes: 3

Views: 3064

Answers (1)

G_B
G_B

Reputation: 1573

Welcome to SO!

CPLEX and similar solvers have a capability to generate an "irreducible infeasible set" of constraints (IIS) for infeasible problems. This is a subset of the original constraints which has the following properties:

  • It is impossible to solve the problem with all the IIS constraints active.
  • Removing any one of these constraints will make it possible to solve the problem.

Examining an IIS is often helpful in finding contradictory constraints. Note that some problems will have more than one IIS; the solver will only find one IIS each time you run it, so if there are multiple conflicts you may need to repeat the process a few times until you've found and fixed all of them. Finding an IIS can be quite slow.

From your tags I'm assuming you're using CPLEX via AMPL. Here is some documentation which discusses how to access CPLEX IIS capability via AMPL. Basically, insert the following commands before and after the "solve":

option cplex_options 'iisfind 1';
solve;
display {i in 1.._ncons: _con[i].iis <> "non"} (_conname[i], _con[i].iis);

This will list the constraints involved in the infeasibility. You can also use 'iisfind 2' which is slower but tries to find a smaller IIS.

Sometimes AMPL's presolve capability gets in the way of using the IIS finder. AMPL runs a "presolve" step which attempts to reduce the size of the problem by identifying redundant constraints and so on.

Usually this is helpful because it reduces memory requirements and solver time, but it may get in the way of infeasibility debugging. Presolve may mean that not all the constraints get passed to the solver (in which case your IIS may not be a true IIS, because the solver didn't see the redundant constraints) and sometimes AMPL identifies the infeasibility in presolve, in which case it never sends it to the solver at all so you can't use the IIS capability.

In your case, it looks as if AMPL is sending it to the solver, so the code above ought to work. But if you do have cases where infeasibility is detected in presolve, and you want to identify the cause of the problem, you can switch off presolve:

 option presolve 0; #set to 10 to re-enable presolve

I hope that helps with your problem.

Upvotes: 6

Related Questions