Skip to main content
20 votes
Accepted

Linear Optimization Library for C++ with GPU Support

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 (...
mtanneau's user avatar
  • 4,183
15 votes

Which GPUs to get for Mathematical Optimization (if any)?

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 ...
Geoffrey De Smet's user avatar
14 votes

Which GPUs to get for Mathematical Optimization (if any)?

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-...
Mathieu B's user avatar
  • 242
14 votes

Which GPUs to get for Mathematical Optimization (if any)?

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 ...
JakobS's user avatar
  • 2,767
14 votes

CPLEX, number of threads and solving time

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 ...
Marco Lübbecke's user avatar
10 votes

Which GPUs to get for Mathematical Optimization (if any)?

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 ...
Brian Borchers's user avatar
10 votes
Accepted

RAM requirement for optimization problems

Easy answer: 64 GB With 24 threads (is this already including hyperthreads? Maybe not, so we are actually talking about 48 threads...) you'll have about 2 and a half GB for every thread - that's not ...
mattmilten's user avatar
  • 1,653
8 votes

Fast way to repeatedly solve many similar LPs/QPs in parallel

The OPTMODEL modeling language in SAS (disclaimer: I work at SAS) supports two features for solving independent optimization (LP or otherwise) problems concurrently: The COFOR loop, which ...
RobPratt's user avatar
  • 32.7k
8 votes

CPLEX, number of threads and solving time

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, ...
prubin's user avatar
  • 39.5k
8 votes
Accepted

Parallel nonlinear solvers

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 ...
Nikos Kazazakis's user avatar
8 votes

Which GPUs to get for Mathematical Optimization (if any)?

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 ...
Rob's user avatar
  • 2,120
7 votes

Gurobi and CPLEX cannot exploit more than 32 cores of machine

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 ...
LinAlg's user avatar
  • 171
7 votes

Gurobi and CPLEX cannot exploit more than 32 cores of machine

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,...
mattmilten's user avatar
  • 1,653
6 votes

Fast way to repeatedly solve many similar LPs/QPs in parallel

A very easy way to do this is to use multiprocessing alongside cvxpy. It won't be fastest possible, but since you want to stick ...
Robert Bassett's user avatar
6 votes
Accepted

Fast way to repeatedly solve many similar LPs/QPs in parallel

After a good bit of experimentation based on the ideas posted, here was my solution: Do as many matrix multiplications up front using pytorch on the GPU to simplify the problem. This means two things....
Zach Lee's user avatar
  • 131
6 votes

Parallel nonlinear solvers

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 ...
Robert Schwarz's user avatar
5 votes

Parallelization of an existing Adaptive Large Neighbourhood Search Heuristic

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 ...
Michael Feldmeier's user avatar
5 votes

How to use solvers with virtual machines?

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 ...
Walter Sebastian Gisler's user avatar
5 votes
Accepted

How to use solvers with virtual machines?

(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,...
Nikos Kazazakis's user avatar
5 votes

Fast way to repeatedly solve many similar LPs/QPs in parallel

If I understand this correctly, you are solving 900 QPs (one for each combination of $i$ and $j$), tweaking the parameters, then solving all 900 again (and again). One possibility to try would be hot-...
prubin's user avatar
  • 39.5k
4 votes

When solving many MILPs how to assign CPU cores to solver instances?

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 ...
rasul's user avatar
  • 2,150
3 votes

How to use solvers with virtual machines?

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 ...
Philipp Christophel's user avatar
3 votes

How to parallelize metaheuristics algorithms (Island Model)?

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 ...
Nikos Kazazakis's user avatar
3 votes

CPLEX, number of threads and solving time

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 ...
Divyam Aggarwal's user avatar
3 votes

Literature for building solver portfolios

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 ...
mtanneau's user avatar
  • 4,183
2 votes

Gurobi and CPLEX cannot exploit more than 32 cores of machine

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 ...
Nike Dattani's user avatar
  • 1,278
2 votes

Parallel nonlinear solvers

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, ...
Rob's user avatar
  • 2,120
2 votes

Parallelization of an existing Adaptive Large Neighbourhood Search Heuristic

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 ...
Geoffrey De Smet's user avatar
2 votes
Accepted

When solving many MILPs how to assign CPU cores to solver instances?

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 ...
prubin's user avatar
  • 39.5k
2 votes

Linear Optimization Library for C++ with GPU Support

As mentioned, both simplex method and barrier method don't suit GPUs. However, recently Google successfully gives a first-order method PDLP[1]. By using tricks like restarting, the performance of PDLP ...
xd y's user avatar
  • 1,196

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