Solving multiple easy ILP instances

Question

I have an application where I am solving millions of ILP instances that differ from each other only on one constraint. The instances, of course, are relatively easy to solve or otherwise this would be hopeless. Their size is less than 1000 variables.

What ILP solvers would be good for this application? What CPLEX settings would be good for this application?

So far I have used the CPLEX C++ API. I use IloModel::add() and IloModel::remove() to add and remove the differing constraint every time. With this approach, I am able to solve 100,000 instances in about 40 seconds. However, I'm not sure if this is the best I can do. I have also observed that the model is very unstable: adding a constraint saying objective <= upper_bound, where upper_bound is an external upper bound, made the solving more than 10 times slower.

Answer 1

in order to increase the throughput you could

1. Not only rely on add and remove in "modifying problems" options but on smaller changes.
2. Try to run the instances in parallel
3. Instead of adding a constraint on the objective use the setting IloCplex::Param::MIP::Tolerances::UpperCutoff or IloCplex::Param::MIP::Tolerances::LowerCutoff

Answer 2

If I recall correctly, adding a constraint on the primal objective function causes degeneracy in the dual LPs, which could account for at least part of the speed decrease you noted. In addition to Alex's suggestion about using the upper and lower cutoff parameters, you could add a new variable (call it $z$), constraint it to equal the original objective function, then minimize or maximize $z$. When you want to bound the objective value, you can change the lower or upper bound of the $z$ variable. I think this avoids at least some of the degeneracy-related problems.