CPLEX, number of threads and solving time

Question

Using CPLEX via its Python API, I encountered a "weird" behavior. For some instances, with a limited number of threads (10 in my tests), the instances cannot be solved after 10 days (afterwards, the memory is full).

However, when relaunching the solver on the same instance but without thread limitation (14 on my machine), the same instance is solved within a few seconds!

There is no objective function in my MIP (I just want the satisfaction of the constraints). I know that it could be "luck" in the enumeration, but I found it quite strange that allowing a few more threads totally changes the solving time.

Is it something "normal"? Is there a reason of such behavior? Thanks

Answer 1

What you encounter is called performance variability, it was first (?) observed by Emilie Danna. Yes, B&B is an exact method, but during the run, a lot of heuristic decisions are taken, which variable to branch on, which node to select, which primal heuristic to run... Many of these decisions are based on some sort of score. When several entities (like fractional variables) have the same score, it is "implementation dependent" what happens; it may depend e.g., on the order in which items are stored in a data structure, which in turn may depend on the order in which the model is read etc. etc. etc. It was depressing in the beginning because it means that some speedups or slowdowns may actually be only noise. Then, people started to make use of this phaenomenon, like here by Andrea Lodi and Andrea Tramontani.

Answer 2

I wouldn't call this "normal", but then I rarely use the term "normal" for anything involving MIPs. If the optimal solution from the quick run is close to the best bound from the long run, then yes, this could just be luck (the 14 thread run happened to stumble on the optimal solution quickly). If the 10 day best bound is significantly inferior, then it's a bit less clear that we are looking at luck ... but it is still possible.

Among other things, I think CPLEX will turn several different algorithms loose on the root node in parallel, with whichever one solves the root node first the "winner" (meaning branch-and-cut will use the root solution it got). I'm not sure how changing from 10 to 14 threads would influence that, but you could conceivably wind up with a different initial basis (particularly since your objective function is constant, so all basic feasible solutions are "optimal"). That in turn could result in different cuts and bound tightening results, altering the search tree quite a bit.

Also, the default setting for the parallel mode switch is "auto", meaning CPLEX will choose between deterministic and opportunistic use of parallel threads (with the latter, as you would expect, not being particularly deterministic). You could try running both 10 and 14 threads in deterministic mode (not running the 10 thread version too long, of course) and see if things change.

Answer 3

I had a similar observation while running my developed optimization framework (based on column generation) on different machines. Being new to this phenomenon, I was confused for days to see these performance variations even after fixing random number seeds from different packages. Later, I found that the LP solver is giving a slightly different answer in each iteration of a Column Generation approach which is because of the fact that the order of input variables to LP are changing due to usage of multiprocessing techniques while generation of these variables. Hence, the order of variables/constraints or any other change in model may bring such performance variations.