2
$\begingroup$

CPLEX settings

LPMethod: Barrier

Threads: 4

Issue: When I run my model, the barrier method will solve using the 4 threads (as expected). I noticed in the log file that the solver then follows up with its "deterministic" parallel mode in which it will start dual simplex and primal simplex but only use 1 thread for each. It is in this stage that my model run times start to grow exponentially w/ longer time periods.

I have done a little bit of reading and understand that "deterministic" is the default setting for parallel mode (i.e. this is expected behavior).

Question(s):

  • Is there a way to specify more threads than 1 when parallel mode kicks in? If so how?
  • Can I remove deterministic parallel execution model all together if I accept the final results varying slightly from 1 run to another?
$\endgroup$
6
  • $\begingroup$ Can you clarify the setting a bit? It's somewhat hard to follow what exactly is happening. If i had to guess, i would say: you use barrier for a large continuous LP, which works reasonably well, but after having solved it with the barrier method, the solver does it's crossover-step which is simplex-based and therefore limited to serial processing. This crossover can be a bottleneck (it has been for some huge layered-graph models for me in the past). If that's the case and you don't need a basic feas sol, you can turn it off.If you actually solve a MIP, things are more problematic howewer $\endgroup$
    – sascha
    Aug 7, 2022 at 10:54
  • $\begingroup$ What version of CPLEX are you using? In 22.1, the default parallel mode is "let CPLEX choose", not deterministic. (It switches to deterministic when you use the barrier method, but then I think it switches back to the original choice when branching in MIP problems. I'm not sure what it uses during crossover.) $\endgroup$
    – prubin
    Aug 7, 2022 at 15:00
  • $\begingroup$ CPLEX version: 20.1.0.0 @sascha your assessment is generally correct. i am solving a large LP problem in the form of a capacity expansion model for the electric power grid. there will be instances in which i would need to run the form as a MILP but not in this instance. sounds like i can just switch the [parallel] parameter to (-1), i.e. opportunistic, and this might provide me the response i am looking for? $\endgroup$
    – JBH_84
    Aug 7, 2022 at 15:58
  • $\begingroup$ I think we are still in diagnostics. It would be better to increase verbosity (split into multiple params in cplex) such that it's easier to recognize, if the bottleneck is crossover or something else. I'm interpreting things a bit different than you: I don't see why deterministic -> oppurtunistic should help. Both simplex (primal and dual) are not parallel and your are bound by 2 threads in crossover i guess. This has, imho, nothing to do with para-mode. Deterministic parallelism doesn't imply serial processing in general (it sounds you indicate this?). It's just more careful syncing-work $\endgroup$
    – sascha
    Aug 7, 2022 at 16:55
  • $\begingroup$ Can you show the log file? $\endgroup$ Aug 7, 2022 at 20:41

1 Answer 1

2
$\begingroup$

I think there are several things to distinguish here: concurrent LP algorithms (e.g. running barrier and simplex in parallel), deterministic vs opportunistic, and crossover (which happens after barrier). Note they are controlled by different parameters.

First the concurrent part, which mean "run multiple algorithms in parallel". If you give CPLEX an LP to solve and multiple threads, there are several strategies CPLEX can use, see https://www.ibm.com/docs/en/icos/22.1.0?topic=parameters-algorithm-continuous-linear-problems. The original post indicates "LPMethod: Barrier", so I assume there is no simplex vs barrier running concurrently, i.e., only the barrier algorithm is executed and it uses all available threads (in your case, 4).

Second, the deterministic vs opportunistic mode. This distinction exists because, as parallelism is involved, things may not be deterministic anymore, i.e., you may run the same problem on the same machine with identical settings, and get a different answer. In particular, it only makes sense when multiple algorithms are executed concurrently. From the CPLEX docs:

deterministic means that multiple runs with the same model at the same parameter settings on the same platform will reproduce the same solution path and results. In contrast, opportunistic implies that even slight differences in timing among threads or in the order in which tasks are executed in different threads may produce a different solution path and consequently different timings or different solution vectors during optimization executed in parallel threads. In multithreaded applications, the opportunistic setting entails less synchronization between threads and consequently may provide better performance.

Finally, crossover. This is the step of taking an interior-point solution and polishing it into a basic solution. AFAIK, CPLEX applies crossover by default. While I cannot say for sure without seeing your exact CPLEX log, I believe what you describe is the crossover: after the barrier algorithm, CPLEX will execute a primal and/or dual simplex to perform crossover. This step is single-threaded, because simplex algorithms are single-threaded If you're only solving an LP, and do not need a basic solution, you can switch it off; see CPLEX docs on how to do that.

$\endgroup$
3
  • $\begingroup$ your paragraph addressing the crossover behavior is in fact what i am trying to hone in on. i can upload my log file but to be honest i'm not sure how to do that on this forum. do you know what CPLEX parameter is the one that controls whether the crossover stage is executed or not? and just to confirm my understanding: the simplex method during crossover is limited to a single thread, correct? what is a basic solution? $\endgroup$
    – JBH_84
    Aug 7, 2022 at 23:26
  • $\begingroup$ The three links to the CPLEX docs will take you to the parameters that control (i) the algorithm used to solve LP problems, (ii) the deterministic vs opportunistic mode, and (iii) crossover. That last one will explain how to switch it off. Primal and dual simplex are limited to one thread each, yes. Basis solutions are the solutions that are returned by simplex. They correspond to extreme points of the feasible set, and they are generally sparser / better numerically conditioned. $\endgroup$
    – mtanneau
    Aug 8, 2022 at 2:16
  • $\begingroup$ thank you very much. learned a lot from just this one question $\endgroup$
    – JBH_84
    Aug 8, 2022 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.