3

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?

Xavier Nodet
  • 5,033
  • 2
  • 37
  • 48
Nabilah M. Syukur
  • 31
  • 2

1 Answers1

6

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.

GB supports the mod strike
  • 1,543
  • 1
  • 11
  • 12
  • Thanks a lot sir! It really helps :) – Nabilah M. Syukur May 17 '18 at 08:39
  • When trying to run the command `iisfind 1`, I get the error `Failed to compute conflict`. How to avoid this issue? – Jonas Schnidrig Aug 30 '22 at 09:30
  • @JonasSchnidrig I'm not familiar with that one. You could try testing it on a very small and simple infeasible problem, as a way of testing whether the issue is with your syntax/configuration in general or if your particular problem is too hard. Beyond that I don't have advice, sorry. You could ask this as a separate question and see if somebody else knows. – GB supports the mod strike Aug 30 '22 at 12:16
  • 1
    In fact, I tried and changed things. After some research, I found the issue. As you mentioned in the response, there might be the issue of presolve. When putting the option `option presolve 0`, the size of the problem (12'533) constraint issues is not anymore a problem. Thanks for coming back on it nevertheless... – Jonas Schnidrig Aug 30 '22 at 17:34