4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ There may be sequencing things to consider. Such as, can we reuse an earlier found solution in a subsequent solve. In that case, the calculation becomes very different. $\endgroup$ Aug 5 at 8:36
2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Have you set up SLURM yourself for this or did you have a cluster that came with it? If the former would you say the ongoing and one time administrative effort is worth it? $\endgroup$ Aug 5 at 5:26
  • $\begingroup$ @worldsmithhelper I have never needed to set up slurm myself because all the servers I have used already had it installed. Slurm is quite well-known for cluster management and if you are using a server that has not it installed, you can ask your admin to do so (this is what they are supposed to do). Note that they might be using something other than Slurm, in which case you can use that option instead. $\endgroup$
    – rasul
    Aug 5 at 10:11
  • 1
    $\begingroup$ @worldsmithhelper There are many more schedulers out there, but I haven't tried installing any of them. Not sure if setting them up would be easier than Slurm, but personally I would try Slurm first any way. Slurm is widely used for cluster management, it is open source, it has good documentation and a wide range of users, and you could essentially end up being one of them. So the time you spend learning it is not wasted! $\endgroup$
    – rasul
    Aug 5 at 10:18

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.