10
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Thanks! Using IloCplex::Param::MIP::Tolerances helped a lot. I also tried modifying the constraint instead of adding and removing it, but that didn't have any impact on the runtimes. $\endgroup$ – Laakeri Jan 24 at 11:25
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.