CPLEX C++ Interface: How to get the index of a violated constraint?

Question

I attempt to solve an integer linear program (ILP) using the solver IBM ILOG CPLEX in C++. The solver states that the problem is infeasible and points out the index of a violated constraint. My question concerns the identification and analysis of this constraint in C++.

A manual approach to analyzing the constraint would be to export the problem to a text file using the function extractModel and look up the violated constraint in this file.

Preferably, I would like to get the index of the violated constraint in C++ and get as much information about this conflict as possible.

Currently, I am using the conflict refiner but do not get any useful information out of it. Specifically, I keep an IloRangeArray of all constraints I ever add to the model, call refineConflict for this array and then use the function getConflict to query (possibly) violated constraints. The result is that all constraints I ever added are possibly violated and no constraint is proved to be violated.

How can I access the index of the one constraint reported in the error message that states that the problem is infeasible?

Also, am I using the conflict refiner incorrectly? E.g. am I doing something wrong when I make copies of constraints that I add to the model in a separate array? (The copy constructor and assignment operator of certain classes in Cplex seem to have non-standard behavior that I do not understand.)

Any help is appreciated.

Answer 1

I've not tried to use the conflict refiner API. Probably should look into it... but I use the conflict refiner a lot in the standalone interactive CPLEX. I am not aware of any issues of keeping copies of the constraints in your own code - I have done it before in CPLEX & Concert with C++. It may be a conceptual misunderstanding of what the conflict refiner does...

Remember that it is very rare to have a single identifiable infeasible constraint. It is much more common that there is a set of constraints that cannot be satisfied together, but if any of that set of constraints is removed then the rest are then feasible. This is usually called the "irreducible infeasible set".

Think for example of three constraints:

a >= b + 1
b >= c + 1
c >= a + 1

Clearly these three constraints cannot be satisfied simultaneously, but take any one away and the other two are then OK. It can be very hard to decide which constraint is wrong in some cases, and really depends on a deeper understanding of the problem and its model.

Anyway, try exporting the model as an LP, MPS or SAV format file and read it into the standalone CPLEX optimiser. Then optimise it - it should also fail with a reported infeasibility. Then run the conflict refiner and then display the computed (irreducible) infeasible set:

read fred.lp
optimize
conflict
display conflict all

I find that MPS files are better at preserving the full precision of the problem and are probably more portable to try with other solvers, but LP files are much more human-readable. The SAV file format is supposed to be the most accurate copy of what CPLEX has in memory, but is very opaque and rather CPLEX-specific. If your problem is clearly infeasible the LP format is probably nicer to work with, but if the problem is borderline infeasible you may get different behaviour from the LP file. It would probably help you a great deal if you name all your variables ad constraints too. Maybe just do the naming in debug builds or add a flag to control whether or not to do the additional naming.