18

For context: most (if not all) major LP solvers are built on 2 algorithms: the simplex method, and the interior-point method. The simplex method is intrinsically sequential: you're doing a lot of (cheap) operations called pivots, and the matrices involved are usually sparse. At each pivot, you essentially perform a rank-one update of a sparse LU ...


14

The first algorithm coming to mind that can benefit from GPUs is the Interior-Point Method (IPM), at its heart is the resolution of a linear system. See references: GPU Acceleration of the Matrix-Free Interior Point Method Cholesky Decomposition and Linear Programming on a GPU


14

If you problem is continuous I would say that it might be beneficial. For problems that involve discrete variables I've not seen anything that does benefit from the usage of a GPU. GPUs aid problem solving if the underlying problem has a structure that can exploit the massive parallel computation structure of the graphical processing unit. Calculations ...


14

I've not seen any efficient use from GPU's for metaheuristics - only experiments that proved their inefficiency for these algorithms. So not the right tool for the job, apparently. Maybe there's a undiscovered technique to make them work efficiently. (I have seen/build efficient use of multiple CPU cores for metaheuristics, even on Local Search with ...


13

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


10

A lot depends on what kinds of computations you are doing. The subject of this group is "Operations Research", but that surely includes a range of computational work including discrete event simulation, machine learning, linear and nonlinear programming, discrete optimization, etc. There's no one answer applicable to all of those kinds of problems. For ...


8

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


8

Which GPU, if any, should I get for mathematical optimization? In the case of commercially available software, where no source code is available, you are stuck using the GPU that is better supported by the applications you intend to run. AmgX, cuSOLVER and nvGRAPH all require Nvidia GPUs, and offer supporting articles on their blog. Cusp is a library ...


7

Modern CPUs are very complex and have at least two features that limit their scaling capability. The first one is a turbo feature that increases the clock speed when not all cores are utilized. The second one is that all cores share the same memory bus and the same L2 and L3 cache. If you solve the same problem in parallel (so start Python twice and let each ...


7

You need to distinguish between threads and (physical) cores. Is it possible that the cores you see in your machine are actually just hyperthreads, i.e. 2 cores resemble one physical core? Furthermore, using many cores is not always very helpful to solve a MIP. You may want to try something like Concurrent Optimization in Gurobi to exploit performance ...


7

As a developer of parallel non-linear software, I want to share my experience working in this space and the challenges we face. If I were to break down why we don't have more parallel non-linear software I would pick the following reasons: Expectations vs reality Inherent difficulties in designing and implementing the algorithms. Lack of good tools to ...


5

Another paradigm to parallelize search heuristics is the Backbone strategy. See for example this paper. The main idea is to run multiple instances of an arbitrary heuristic in parallel, and then compare the resulting solutions of each instance. "structures" (e.g. subtours in TSP) common in all/most solutions (called Backbones) are used to reduce the ...


5

I think that there exist multiple solvers based on ADMM. If the variables can be partitioned in two sets in a way that the problem decomposes for one set fixed, then every other iteration can be executed in parallel. I had a specific solver implementation in mind, but could not find it now. Instead I found POGS which seems to be more recent and targeting ...


5

It depends on the solver and on the license type, but generally it is possible and you should reach out to the software provider directly to get more information. Most solvers (I have seen this with Gurobi, Cplex, FICO Xpress) can be bought with different licensing options: licenses for dedicated machines single user license (which includes student licenses)...


5

(Full disclosure: I founded Octeract) So, a few things here: In practice Technologically speaking, of course you can (that's the point of a VM), unless a solver is using anti-virtualisation technology, and assuming your hardware supports virtualisation. However, some solver licences tend to be tied to a specific machine/user, so you will need to read the ...


4

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


3

SAS solvers are part of the SAS Viya cloud platform and thus can be run in containers and virtual machines. The same is probably true for most commercial solvers. But the benefits might be not as great as you think. While a lot of memory certainly does not hurt and might be needed for some problem instances, the gain from hundreds of CPUs is probably minimal....


3

The easiest way is to use the Python multiprocessing module (or similar). You can create a pool of parallel workers, each of which would run a different heuristic. The multiprocessing toolbox also allows you to pass messages between processes, which you can use to communicate information among them (e.g., solution vectors). In order to do that you would need ...


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


3

For the automatic solver configuration, I know of this reference (there may be a journal version): A learning-based mathematical programming formulation for the automatic configuration of optimization solvers. They also cite further references on the topic.


2

Your screenshot here indicates to me that you have 32 physical cores, 64 threads, and 64 vCPUs. You observed that Gurobi and CPLEX are not making use of more than 32 cores, but you have not shown us anything indicating that your machine has ever successfully used more than 32 cores for any calculation that doesn't use hyperthreading. If you try other ...


2

I've noticed that parallel (CPU or GPU) nonlinear programming solvers are few and far between. The General Nonlinear Problem The $n \times n$ nonlinear problem is: $$\begin{array} \mathcal{f}_1(x_1, x_2, \cdots , x_n)=0 \\ \mathcal{f}_2(x_1, x_2, \cdots , x_n)=0 \\ \vdots \tag 1 \\ \mathcal{f}_n(x_1, x_2, \cdots , x_n)=0 \end{array}$$ which can be ...


2

I've implemented reproducible parallelization on a number of Local Search variants with incremental score calculation (= delta constraint and fitness evaluation). Some of our requirements you might be able to forgo (most notably OO/FP support), but others (such as not sacrificing incremental calculation) are crucial to get better results. For more ...


2

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


1

I'm not sure if this is exactly on point, but there is a paper by Carvajal et al. on the use of parallel trees (with communication between them) for solving integer programs. You might also be interested in reference [10] in their paper (Koch et al.), which discusses "racing ramp-up", a technique adopted by CPLEX a while back, in which you ...


Only top voted, non community-wiki answers of a minimum length are eligible