Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
Let's say I have an 16 core machine and many roughly equally hard MILP problems and enough RAM. The latency of solving doesn't matter. With how many cores should I start solvers on to maximize throughput (instances solved per second)?
I am looking for general advice for MILP solvers using Branch and Bound based or Local Solvers. If you have experience with a specific problem class you are welcome to answer too.
As far as I know, solution speed for solvers is typically a sublinear function of the number of threads/cores. This makes sense since parallel processing requires additional effort (CPU cycles) to coordinate threads, and may sometimes be subject to blocking. Based on that, and assuming a reasonably large pool of problems and adequate RAM, I would probably allocate one core per problem (or, assuming the cores each accommodate multiple threads and you are drowning in RAM) maybe one thread per problem.
So we know that MILP instances are independent and that the total throughput is to be maximized. In practice, increasing the number of threads used by a solver to solve a MILP instance could marginally improve the runtime only up to some point. Such optimal number of threads should be checked on a case by case basis. In CPLEX, for instance, the parallelism efficiency decreases for more than 4-8 threads. Increasing the thread count past this number will not significantly reduce the execution time.. This may be considered as a general rule of thumb.
Once you fix the number of threads used by the solver, you can use a job scheduler to allocate your jobs (solving MILP instances) to the resources (e.g., cores) that you specify. A job scheduler would start a new job automatically once the previous job is completed. I have mainly used Slurm. Note that in general a computer node/core may have multiple threads (see here for more details). In a linux machine running lscpu in a bash terminal would show this information. Here is an example with 1 thread per core:
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Thread(s) per core: 1
Core(s) per socket: 8
Socket(s): 2
NUMA node(s): 2
Vendor ID: GenuineIntel
CPU family: 6
Model: 62
Model name: Intel(R) Xeon(R) CPU E5-2667 v2 @ 3.30GHz
Stepping: 4
CPU MHz: 3299.910
BogoMIPS: 6599.11
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 25600K
NUMA node0 CPU(s): 0,2,4,6,8,10,12,14
NUMA node1 CPU(s): 1,3,5,7,9,11,13,15
You should also test the scenario that restricts each job to one core (e.g., in the example above, the number of threads used by the solver is set to 1 and each job is allocated to one core). The operating system (OS) typically switches intensive threads between different cores to balance the thermal load of a multicore processor. This can cause latencies due to the OS bringing jobs from one core to another. So the last scenario may also prove efficient.
One last comment!
There is still room for improving the efficiency if you are really into it! This requires you to have/generate a profile or sample data as to how long an instance with features such as number of nonzero elements, number of variables and number of constraints would take (if your MILP instances represent different instances of the same problem, then you can also use that problem's features). Based on this sample, you can solve an optimisation problem that allocates jobs to a given number of cores/nodes such that the maximum completion time (makespan) of nodes is minimized. You can even go ahead and solve a two-stage stochastic program that minimizes the expected makespan (first-stage decisions are allocation of the jobs to nodes and second-stage decisions are the sequencing of them on each node).
