5
$\begingroup$

I am solving a mixed-integer (binary) linear problem using CPLEX as a solver (branch-and-bound method). But I encountered the following issue. Each run I get a different solution at a different node of MILP. However, these solutions are very close to each other.

According to my logic (please correct me if I'm wrong), the solver stops when the solution satisfies absolute\relative (or both?) gap tolerance, so basically, this gap could be satisfied at different nodes of the branch-and-bound algorithm.

My question is: Which parameters impact the final node where the algorithm ends? Are there any parameters that CPLEX chooses randomly at the beginning of the algorithm (like branching variables for example or others) that I can fix and end up on the same solution every run?

enter image description here

$\endgroup$

1 Answer 1

12
$\begingroup$

There are a number of decisions CPLEX makes that can be affected by "randomness". In some cases, CPLEX is actually using a random number generator to make decisions (such as breaking ties). In other cases, solutions can change when the order of entry of variables or constraints is changed, or when the model is read from a .lp file in one case and a .sav file in the other case, even though the model is theoretically the same. (This does not sound like your situation.) Finally, when CPLEX is running with parallel threads, the order that the computations get done is subject to the whim of the gods, since the operating system will interrupt threads to do operating systems sorts of things (background processes).

You may be able to eliminate some or all of the first source of randomness by setting the RandomSeed parameter explicitly at the start of each run, although I'm not confident about that. The other parameter you can try is the "parallel" parameter (aka parallel mode switch), which you can try setting to deterministic. If that does not work, the only other suggestion I would have would be to use a single thread. That would eliminate the randomness induced by threads finishing before/after sibling threads, but it would presumably also slow the solver.

$\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.