12
$\begingroup$

Reading gurobi reference manual I found this:

We have also found that certain classes of MIP models benefit from reducing the thread count, often all the way down to one thread. Starting multiple threads introduces contention for machine resources. For classes of models where the first solution found by the MIP solver is almost always optimal, and that solution isn't found at the root, it is often better to allow a single thread to explore the search tree uncontended.

Another situation where reducing the thread count can be helpful is when memory is tight. Each thread can consume a significant amount of memory.

In the past, when I used a shared server, users were requested by IT to manually limit our thread limit to 1. Now I am working on a dedicated server with 8 threads available.

As we can see from gurobi's manual, one could choose which thread limit benefits your goals (for worse or better), so that the maximum number might not be the case for better/faster results.

The Question

For an academic research and publishing, what is the fair practice when comparing comercial solver results with non parallelized heuristics?

$\endgroup$
7
$\begingroup$

Personal opinion: I think it is fair to use as many threads as makes sense in context. For instance, when I use CPLEX I believe it defaults to four threads (one per core on my PC). If I'm solving a problem that is a particular memory hog, I may throttle back to three or even two threads to avoid memory problems. I have no compunction about comparing any of those runs (2, 3 or 4 threads) to a single-threaded heuristic, provided that I document that the heuristic was single threaded and CPLEX was not (or at least document that CPLEX was using default parameter settings, which would imply multiple threads).

That said, I have no objection to someone comparing a single-threaded heuristic to a commercial solver limited to a single thread, provided that they state the limitation on the commercial solver.

Also, I do not think it is typical to pit a heuristic against a commercial solver in a speed test. In addition to the comparability problems alluded to in dhasson's answer (CPLEX: highly optimized C/C++ code written by experts; heuristic: crappy Java code written by an amateur, i.e., me), it's a bit of an apples-oranges comparison because solvers produce proof of optimality (or at least gap measurements) and heuristics generally do not. You can use CPLEX, Gurobi or some other solver in "heuristic mode" (use parameter settings to maximize the chance of improving the primal bound, ignore the dual bound), in which case it's more of an apples-to-apples comparison.

$\endgroup$
5
$\begingroup$

The problem is, even if you use the same number of threads, a 'rigorous' comparison of different implementations in different programming languages - for example, in terms of running time or of the quality of the solution found in the same time limit - can be quite challenging or tricky. Citing Chapter 18 of Ahuja, Magnanti & Orlin1:

"The existing literature on computational testing has a tendency to overrely on CPU time as the primary measure of performance. CPU time depends greatly on subtle details of the computational environment and the test problems such as (1) the chosen programming language, compiler, and computer; (2) the implementation style and skill of the programmer; (3) network generators used to generate the random test problems; (4) combinations of input size parameters; and (5) the particular programming environment (e.g., the use of the computer system by other users). Be-cause of the multiple sources of variabilities, CPU times are often difficult to replicate, which is contrary to the spirit of scientific investigation. Another drawback of the use of CPU time is that it is an aggregate measure of empirical performance and does not provide much insight about an algorithm's behavior. For example, an algorithm generally performs some fundamental operations repeatedly, and a typical CPU time analysis does not help us to identify these "bottleneck" operations. Identifying the bottleneck operations of an algorithm can provide useful guidelines for where to direct future efforts to understand and subsequently improve an algorithm."

From the last citation, most likely points (1) and (2) - and probably (3) - will affect comparison of optimization algorithm performance and should be taken into account.

To the best of my knowledge - what I remember after being to talks of academics reading publications -, they tend to mention reducing the number of cores to 1 (in case of comparing to non-parallelized heuristics) and more importantly turning off all kind of additional intelligence the commercial solver may include (e.g. presolve, automatic cutting plane generation), in order to the performance comparison to be as fair and unbiased as possible.

1 Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1988). Network flows.

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