Very slow solve time for scip vs fmincon

[Greg Hendrickson]

Dear Dr. Löfberg,

I tried to solve a non-linear program using SCIP in YALMIP, but the computation time took  over 30 minutes for the primal-dual gap to reach 10%. Solving the exact same program with FMINCON produces a local minimum in about 1.5 seconds. I am not sure if there is a problem in my script, or if it is a problem that has to do with SCIP itself that leads to such a long computation time.

I attached a zip of my code if you want to take a look. I am still fairly new to optimization but will try to answer whatever questions I can.

Thank you for your help.

[Johan Löfberg]

scip is a global solver for nonlinear problems, s you should expect it to be arbitrarily many orders slower than fmincon. Indeed you should expect it to fail on most non-trivially sized problems

[Johan Löfberg]

appears to be a pretty simple problem though with some very benign geometry, yalmips global solver bmibnb solvers it a couple of seconds (so scip simply performs very badly here)

>> optimize(Constraints,Objective,sdpsettings('solver','bmibnb'))

* Starting YALMIP global branch & bound.

* Upper solver     : fmincon

* Lower solver     : GUROBI

* LP solver        : GUROBI

* -Extracting bounds from model

* -Perfoming root-node bound propagation

* -Calling upper solver (no solution found)

* -Branch-variables : 43

* -More root-node bound-propagation

* -Performing LP-based bound-propagation 

* -And some more root-node bound-propagation

* Warning: 16 branch variables are unbounded from above

* Starting the b&b process

 Node       Upper       Gap(%)       Lower     Open   Time

    1 :   3.45799E+05     1.41    3.40967E+05    2     2s  Solution found by upper solver  

    2 :   3.45799E+05     1.41    3.40967E+05    1     2s  Terminated in bound propagation  

    3 :   3.45799E+05     0.00    3.45791E+05    2     3s    

* Finished.  Cost: 345798.6301 (lower bound: 345791.0824, relative gap 0.0021827%)

* Termination with relative gap satisfied 

* Timing: 29% spent in upper solver (3 problems solved)

*         1% spent in lower solver (2 problems solved)

*         41% spent in LP-based domain reduction (295 problems solved)

*         8% spent in upper heuristics (185 candidates tried)

tisdag 16 mars 2021 kl. 20:28:47 UTC+1 skrev ghen...@gmail.com:

[Greg]

Thank you for your quick response. I tried running bmibnb but it still calls scip as the lower solver since I don't have gurobi.

The example I provided was actually a simplified model so that fmincon was able to solve it, but the full formulation includes binary variables and adds additional constraints at a more resolved time step. Currently, I can't get the model to converge in a finite time with scip and I'm trying to find out if I need a commercial solver.

Are you able to run this new script with bmibnb or any other global solver?

[Johan Löfberg]

It's a bit optimistic to setup an absolutely huge mixed-integer nonconvex nonlinear program and just send it to a global solver. Start by testing a model of a couple of orders of magnitudes smaller to see if there is any chance at all

yalmip is complaining about your implications as you don't have bounds on all variables in those, leading to crappy big-M models

also note that your model appears to be badly scaled, for instance objective has massive spread in coefficients

>> Objective

Nonlinear scalar (real, 22 variables)

Coefficients range: 0.9007 to 1000000

no solver likes data like this

[Greg]

Alright, thank you for your advice! I'll take a closer look at the data.

[Greg]

Just to clarify, when you recommend testing a model a couple orders of magnitude smaller, are you talking about the magnitude of the objective function?

[Johan Löfberg]

No, smaller problem in terms of variables and constraints. You don't run a ultramarathon before you know you can walk.

[Greg]

Makes sense, thank you!