0
$\begingroup$

Currentlly, I am using ortools with SCIP/CBC solvers for a large scale optimization problem, which turned out to be quite slow. The integer part of my problem is due to a piece-wise linear function in the cost function for which to model I introduce around 1e5 binary variables.

  • Are there better open-source solvers I could for such problem that maybe support Interior Point method, too?
  • If I use a commercial one like Gurobi, how faster should I expect it to be?

Below I give an example of how the PWL function would look like:

$x$ -600 -300 -200 -150 -100 -50 0 50 100 150 200 300 500
$y_0$ -48000 -7500 -4000 -1500 -1000 -200 0 200 1000 1800 3000 6000 25000
$y_1$ -50000 -8000 -5000 -1500 -1500 -200 0 200 1000 2100 3000 7000 50000
$y_2$ -60000 -5000 -4000 -2000 -1000 -100 0 100 1500 3000 3000 8000 45000

For each time we have a new $y_t$ vector of y-values, whereas x-values are invariant. The PWL function is always increasing (not necessarily strictly) and passes through point $(0,0)$, for every $t$. I modelled this part as per below: $$ L_{t,i}(1-z_{t,i}) \leq y_{t,i} - (a_{t,i}x_{i}+b_{t,i}) \leq U_{t,i}(1-z_{t,i}), \quad \forall t, \forall i $$ where $L_{t,i}$ and $U_{t,i}$ are known lower and upper bounds of the PWL's linear segments and $z_{t,i}$ are binary variables.

$t$ is around 1000 and the number of breakpoints around 100, which leads up to the creation of around 1e5 binary variables.

$\endgroup$
1
  • $\begingroup$ These link, link may be helpful. $\endgroup$
    – A.Omidi
    Commented Jul 7 at 11:11

1 Answer 1

1
$\begingroup$
  • It may be worth sharing your piecewise linear function model, as there may be room for improvement with such - sometimes tricky - formulations.
  • It may be worth trying the HiGHS open-source solver, which is becoming more and more popular.
  • If you switch to GUROBI, you are likely to expect very big gains in terms of computation time (5-20 times less).
  • If your problem is a well identified optimization problem in the supply chain field (routing, packing, clustering, locating, etc...), Hexaly scales very well for HUGE problems.
$\endgroup$
1
  • $\begingroup$ I updated my post with an example of how the PWL function would look like. If it were convex -or at least a sum of convex functions- I would be able to convert it to an LP minimization problem, but this is not my case. $\endgroup$
    – Apostolos
    Commented Jul 7 at 16:59

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.