Any configurable parameters for the nonconvex quadratic solver?
Answered
I'm trying to use Gurobi to find reasonable local optima to a model with *lots* of bilinear terms: 15 for each hour of the year = 131400. It's actually working surprising well - see log below for a solution in progress. Since I don't expect a problem of this size to ever solve to its global optimum I'd like to set a parameter similar to MIPFocus so Gurobi prioritizes finding feasible solutions. But MIPFocus doesn't seem to do anything in my case. Do Gurobi's MIP-related parameters apply to the nonconvex spatial branching algorithm as well? Or are there other parameters I can set, and if so where can I find information about them?
On a side note, I really hope Gurobi continues development of nonlinear functionality. Very few nonlinear solvers can deal with large-scale problems so these new features are very welcome, And it gives you a unique selling point over Cplex. :)
julia> res, pp = runmodel(2019)
Reading input data...
0.082434 seconds (7.01 k allocations: 4.359 MiB)
Building model...
Academic license - for non-commercial use only
4.717896 seconds (30.47 M allocations: 1.934 GiB, 27.80% gc time, 19.13% compilation time)
Solving model...
Gurobi Optimizer version 9.0.3 build v9.0.3rc0 (win64)
Optimize a model with 788416 rows, 1051201 columns and 2864536 nonzeros
Model fingerprint: 0x00890e0c
Model has 131400 quadratic constraints
Coefficient statistics:
Matrix range [1e-06, 1e+00]
QMatrix range [1e+00, 1e+00]
QLMatrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 2e+05]
RHS range [1e-01, 1e+05]
Presolve removed 385622 rows and 140342 columns
Continuous model is non-convex -- solving as a MIP.
Presolve removed 464321 rows and 219056 columns
Presolve time: 2.31s
Presolved: 849635 rows, 832145 columns, 2864281 nonzeros
Presolved model has 131385 bilinear constraint(s)
Variable types: 832145 continuous, 0 integer (0 binary)
Root barrier log...
Ordering time: 0.10s
Barrier statistics:
AA' NZ : 2.453e+06
Factor NZ : 9.788e+06 (roughly 700 MBytes of memory)
Factor Ops : 2.082e+08 (less than 1 second per iteration)
Threads : 12
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 1.22300002e+07 4.47306217e+08 2.34e+05 0.00e+00 3.55e+03 5s
1 1.25291144e+06 1.15442012e+08 2.84e+04 9.99e-16 4.45e+02 6s
2 5.49459623e+04 9.22264157e+06 1.28e+03 1.33e-15 2.15e+01 6s
3 8.66014798e+03 1.36564786e+06 1.83e+02 1.28e-15 2.99e+00 6s
4 2.59426362e+03 5.77401530e+05 3.83e+01 1.28e-15 6.97e-01 7s
5 1.41404723e+03 2.43949609e+05 1.18e+01 1.03e-15 2.06e-01 7s
6 9.09461351e+02 1.04761655e+05 1.11e+00 5.31e-16 5.47e-02 7s
7 9.05827655e+02 1.74024821e+04 1.50e-06 3.50e-16 7.85e-03 7s
8 1.11662465e+03 5.62185455e+03 9.32e-07 8.64e-17 2.14e-03 8s
9 1.29414308e+03 4.77989909e+03 1.03e-06 7.37e-17 1.66e-03 8s
10 1.36418866e+03 3.63673213e+03 1.17e-06 5.33e-17 1.08e-03 8s
11 1.61477665e+03 2.65501291e+03 8.56e-07 2.70e-17 4.95e-04 9s
12 1.73696625e+03 2.31873370e+03 2.75e-07 2.87e-17 2.77e-04 9s
13 1.79285024e+03 2.13432648e+03 5.94e-07 4.06e-17 1.62e-04 9s
14 1.82771297e+03 2.05377999e+03 1.74e-06 2.21e-11 1.08e-04 10s
15 1.84897044e+03 2.01257533e+03 1.25e-06 1.15e-10 7.78e-05 10s
16 1.87578722e+03 1.98349078e+03 7.01e-07 2.42e-10 5.12e-05 10s
17 1.88486017e+03 1.96785407e+03 5.45e-07 3.00e-10 3.95e-05 10s
18 1.89097851e+03 1.94919984e+03 4.57e-07 3.46e-10 2.77e-05 11s
19 1.89754486e+03 1.93561679e+03 3.07e-07 3.74e-10 1.81e-05 11s
20 1.90184266e+03 1.92484490e+03 2.20e-07 3.64e-10 1.09e-05 12s
21 1.90528102e+03 1.92158367e+03 1.32e-07 2.78e-10 7.75e-06 12s
22 1.90626438e+03 1.91790553e+03 1.07e-07 1.81e-10 5.54e-06 13s
23 1.90713036e+03 1.91629885e+03 8.61e-08 1.39e-10 4.36e-06 13s
24 1.90770501e+03 1.91536040e+03 7.21e-08 1.15e-10 3.64e-06 14s
25 1.90907250e+03 1.91417565e+03 3.83e-08 8.50e-11 2.43e-06 14s
26 1.90961502e+03 1.91317777e+03 2.48e-08 6.09e-11 1.69e-06 15s
27 1.90992509e+03 1.91219965e+03 1.72e-08 3.68e-11 1.08e-06 15s
28 1.91013259e+03 1.91160777e+03 1.22e-08 2.23e-11 7.02e-07 16s
29 1.91024206e+03 1.91126685e+03 9.40e-09 1.44e-11 4.87e-07 17s
30 1.91031415e+03 1.91112917e+03 7.73e-09 1.12e-11 3.88e-07 17s
31 1.91037300e+03 1.91106951e+03 6.32e-09 9.77e-12 3.31e-07 18s
32 1.91046018e+03 1.91092841e+03 4.23e-09 6.37e-12 2.23e-07 18s
33 1.91054406e+03 1.91079711e+03 2.26e-09 4.01e-12 1.20e-07 19s
34 1.91059034e+03 1.91074269e+03 1.18e-09 2.63e-12 7.25e-08 20s
35 1.91060779e+03 1.91069592e+03 1.28e-09 1.68e-12 4.19e-08 20s
36 1.91061974e+03 1.91067860e+03 8.70e-10 1.68e-12 2.80e-08 20s
37 1.91062822e+03 1.91066586e+03 6.95e-10 3.41e-12 1.79e-08 21s
38 1.91063301e+03 1.91065738e+03 8.95e-10 4.06e-12 1.16e-08 21s
39 1.91063740e+03 1.91065182e+03 5.97e-10 3.65e-12 6.85e-09 21s
40 1.91064013e+03 1.91064879e+03 5.72e-10 2.90e-12 4.12e-09 22s
41 1.91064163e+03 1.91064704e+03 7.09e-10 2.24e-12 2.56e-09 22s
42 1.91064246e+03 1.91064609e+03 3.98e-10 1.79e-12 1.72e-09 22s
43 1.91064278e+03 1.91064464e+03 3.35e-10 1.11e-12 8.80e-10 23s
44 1.91064329e+03 1.91064409e+03 4.27e-10 5.37e-13 3.80e-10 23s
45 1.91064349e+03 1.91064382e+03 1.16e-09 2.93e-13 1.57e-10 23s
46 1.91064358e+03 1.91064369e+03 1.28e-09 2.42e-13 5.14e-11 24s
47 1.91064361e+03 1.91064364e+03 1.46e-09 1.01e-13 1.51e-11 24s
48 1.91064361e+03 1.91064362e+03 6.30e-10 2.57e-14 2.71e-12 24s
Barrier solved model in 48 iterations and 24.31 seconds
Optimal objective 1.91064361e+03
Root crossover log...
181077 DPushes remaining with DInf 3.7382007e-01 26s
10571 DPushes remaining with DInf 5.1120378e+07 31s
Restart crossover...
184702 DPushes remaining with DInf 1.9036158e-01 34s
102478 DPushes remaining with DInf 3.2018893e-01 35s
12095 DPushes remaining with DInf 2.5989389e+11 40s
6528 DPushes remaining with DInf 7.5522047e+09 46s
4101 DPushes remaining with DInf 5.9439082e+07 50s
498 DPushes remaining with DInf 7.6328654e+09 56s
0 DPushes remaining with DInf 7.6328733e+09 57s
31574 PPushes remaining with PInf 2.4469140e+03 57s
22391 PPushes remaining with PInf 1.7420352e+03 60s
15649 PPushes remaining with PInf 1.5998145e+03 66s
12470 PPushes remaining with PInf 1.5983557e+03 71s
8167 PPushes remaining with PInf 1.5614087e+03 76s
5444 PPushes remaining with PInf 1.5612246e+03 81s
3177 PPushes remaining with PInf 1.5386127e+03 86s
1364 PPushes remaining with PInf 1.5015118e+03 90s
0 PPushes remaining with PInf 1.4649147e+03 94s
Push phase complete: Pinf 1.4649147e+03, Dinf 3.7951466e+01 94s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
164714 1.9105908e+03 0.000000e+00 3.795147e+01 95s
165251 1.9106709e+03 0.000000e+00 5.873060e-01 97s
166158 1.9106737e+03 0.000000e+00 5.983224e-01 101s
166773 1.9106436e+03 0.000000e+00 0.000000e+00 104s
166773 1.9106436e+03 0.000000e+00 0.000000e+00 105s
Root relaxation: objective 1.910644e+03, 166773 iterations, 101.82 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1910.64359 0 71874 - 1910.64359 - - 105s
H 0 0 1840.3771040 1910.64359 3.82% - 105s
0 0 1909.51135 0 71704 1840.37710 1909.51135 3.76% - 818s
H 0 0 1845.6194413 1909.51135 3.46% - 820s
H 0 0 1846.3335915 1909.51135 3.42% - 842s
0 0 1908.16639 0 71340 1846.33359 1908.16639 3.35% - 1469s
0 0 1906.96404 0 71360 1846.33359 1906.96404 3.28% - 2143s
H 0 0 1848.1408745 1906.96404 3.18% - 2145s
H 0 0 1849.2498978 1906.96404 3.12% - 2166s
0 0 1905.22834 0 70112 1849.24990 1905.22834 3.03% - 3520s
0 0 1904.65654 0 69933 1849.24990 1904.65654 3.00% - 4414s
H 0 0 1852.1359523 1904.65654 2.84% - 4415s
H 0 0 1853.5890739 1904.65654 2.76% - 4435s
0 0 1904.21890 0 68587 1853.58907 1904.21890 2.73% - 5312s
0 0 1904.11336 0 68496 1853.58907 1904.11336 2.73% - 5900s
H 0 0 1857.2266487 1904.11336 2.52% - 5917s
0 0 1904.08828 0 68407 1857.22665 1904.08828 2.52% - 6189s
-
Hi Niclas,
Gurobi's performance seems pretty good given the number of bilinear terms and the problem size.
Do Gurobi's MIP-related parameters apply to the nonconvex spatial branching algorithm as well? Or are there other parameters I can set, and if so where can I find information about them?
All MIP specific parameters also directly affect non-convex problems. There are a few specific parameters, which focus on quadratic problems only, e.g., PreMIQCPForm. You can have a look at the parameter descriptions to get more information. Parameters aiming for quadratic problems often have the capital letter "Q" in their name.
I have also noticed that you are using version 9.0.3. You should try upgrading to the latest Gurobi version 9.1.1 if possible. In the latest version, you could try the new No Relaxation Heuristic, which specifically focuses on finding feasible points before the root relaxation has been computed. The documentation of most important parameters might help here.
Best regards,
Jaromił0 -
Thank you, that was helpful. Now I know I can play around with all the MIP parameters, and if they don't seem to do anything then it's probably something problem specific.
I actually had 9.1.1 installed but for some reason Julia's Gurobi interface wasn't detecting the latest version, but I resolved that issue yesterday. I'll try 9.1.1 on my problem and see if it helps.
I have another unrelated question but I'll start another thread for that (to help maintain googlability).
0
Please sign in to leave a comment.
Comments
2 comments