How to improve optimization speed (quadratic + general constraints)
I’m working on a model with quadratic constraints and several general constraints (including max, min, abs, and power functions). I’m noticing that the best bound convergence is quite slow, even though feasible solutions are found relatively quickly. Any suggestions on model reformulation, constraint handling, or parameter tuning would be greatly appreciated!
Questions
- Why does the best bound improve so slowly in this type of model?
- Are there recommended parameter settings to improve convergence?
- Can the formulation of quadratic/general constraints be improved to speed things up?
Example of some quadratic constraints:
qc0: [ a1 * x + a2 * y + a3 * z ] = 0
qc1: [ b1 * x + b2 * y + b3 * z ] = 0
qc2: [ c1 * x + c2 * y + c3 * z ] = 0
qc3: u1_sq + [ - u1^2 ] = 0
qc4: p1 + [ - r1 * u1_sq ] = 0
qc5: - k1 * l1 + [ r1 * vol1_expA ] = 0
qc6: r2_lhs + [ - r2 * vol2_expB ] = 0
qc7: r2_rhs + [ - k2 * c1 * v1_abs ] = 0
qc8: c1_1_sq + [ - c1_1^2 ] = 0
qc9: c1_2_sq + [ - c1_2^2 ] = 0
qc10: c1_3_sq + [ - c1_3^2 ] = 0
qc11: d1_c1_1_sq + [ - c1_1_sq * x ] = 0
qc12: d2_c1_2_sq + [ - c1_2_sq * y ] = 0
qc13: d3_c1_3_sq + [ - c1_3_sq * z ] = 0
qc14: p2 + [ - u2 * r2 ] = 0
Non-default parameters:
TimeLimit 1000
MIPGap 0.01
MIPGapAbs 0.01
Method 2
DisplayInterval 1
NonConvex 2
Optimize a model with 122 rows, 275 columns and 292 nonzeros (Max)
Model fingerprint: 0xc93566b1
Model has 1 linear objective coefficients
Model has 126 quadratic constraints
Model has 9 simple general constraints
3 MAX, 2 MIN, 4 ABS
Model has 2 function constraints treated as nonlinear
2 POW
Variable types: 275 continuous, 0 integer (0 binary)
Coefficient statistics:
Matrix range [1e-02, 1e+03]
QMatrix range [5e-01, 2e+00]
QLMatrix range [1e+00, 2e+03]
Objective range [1e+00, 1e+00]
Bounds range [1e-03, 1e+02]
RHS range [6e-01, 8e+01]
QRHS range [1e-02, 2e+03]
GenCon const rng [2e+00, 2e+00]
NLCon coe range [1e+00, 1e+00]
Presolve removed 87 rows and 170 columns
Presolve time: 0.01s
Presolved: 266 rows, 111 columns, 701 nonzeros
Presolved model has 2 quadratic constraint(s)
Presolved model has 57 bilinear constraint(s)
Presolved model has 2 nonlinear constraint(s)
Solving non-convex MINLP to global optimality
Variable types: 104 continuous, 7 integer (7 binary)
Found heuristic solution: objective 0.9227001
Root barrier log...
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 2.519e+03
Factor NZ : 4.578e+03
Factor Ops : 1.214e+05 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -5.33847941e-01 1.17190944e+03 4.41e+03 0.00e+00 4.14e+01 0s
1 7.77091072e-01 4.17891474e+02 3.18e+02 1.79e-03 3.51e+00 0s
2 9.07788053e-01 7.05547595e+01 3.03e+01 1.37e-05 3.63e-01 0s
3 9.23055765e-01 2.54045459e+01 1.34e+00 1.36e-07 6.86e-02 0s
4 9.23847600e-01 2.32205578e+00 6.83e-02 3.47e-17 3.65e-03 0s
5 9.31807061e-01 1.42258545e+00 1.62e-06 1.28e-17 1.27e-03 0s
6 9.86354326e-01 1.06487849e+00 1.30e-12 1.73e-18 2.03e-04 0s
7 9.97367960e-01 1.00950609e+00 2.53e-12 5.96e-19 3.13e-05 0s
8 9.99193406e-01 1.00248118e+00 1.70e-12 7.36e-19 8.48e-06 0s
9 9.99711851e-01 1.00084274e+00 1.65e-12 1.30e-13 2.92e-06 0s
10 9.99929239e-01 1.00009014e+00 1.47e-12 1.17e-11 4.17e-07 0s
11 9.99984667e-01 1.00000222e+00 1.68e-12 2.03e-12 4.57e-08 0s
12 9.99991403e-01 9.99993130e-01 9.55e-13 6.34e-13 4.53e-09 0s
13 9.99991998e-01 9.99992614e-01 7.81e-13 8.93e-13 1.64e-09 0s
14 9.99992375e-01 9.99992380e-01 9.09e-13 1.92e-12 9.43e-11 0s
Barrier solved model in 14 iterations and 0.08 seconds (0.01 work units)
Optimal objective 9.99992375e-01
Crossover time: 0.00 seconds (0.00 work units)
Root relaxation: objective 9.999925e-01, 75 iterations, 0.04 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.99999 0 19 0.92270 0.99999 8.38% - 0s
0 0 0.99999 0 19 0.92270 0.99999 8.38% - 0s
0 0 0.99999 0 33 0.92270 0.99999 8.38% - 0s
0 0 0.99999 0 33 0.92270 0.99999 8.38% - 0s
0 0 0.99999 0 33 0.92270 0.99999 8.38% - 0s
0 0 0.99999 0 33 0.92270 0.99999 8.38% - 0s
0 0 0.99999 0 33 0.92270 0.99999 8.38% - 0s
0 0 0.99999 0 33 0.92270 0.99999 8.38% - 0s
0 0 0.99996 0 35 0.92270 0.99996 8.37% - 0s
H 0 0 0.9300082 0.99996 7.52% - 0s
H 0 2 0.9300082 0.99996 7.52% - 0s
0 2 0.99996 0 34 0.93001 0.99996 7.52% - 0s
H 155 178 0.9300082 0.99471 6.96% 7.3 0s
H 215 178 0.9300082 0.99471 6.96% 6.4 0s
H 235 178 0.9300082 0.99471 6.96% 6.4 0s
H 265 178 0.9300082 0.99471 6.96% 5.8 0s
H 959 429 0.9300085 0.98746 6.18% 3.8 1s
6385 3102 infeasible 59 0.93001 0.98593 6.01% 5.9 2s
H16505 7254 0.9300085 0.98345 5.75% 6.5 2s
20323 8758 infeasible 60 0.93001 0.98345 5.75% 6.7 3s
H23960 11136 0.9300085 0.98345 5.75% 6.9 3s
37350 17575 0.95969 58 45 0.93001 0.98284 5.68% 7.1 4s
H53286 22739 0.9300085 0.98190 5.58% 7.3 4s
59500 25816 0.96125 57 48 0.93001 0.98142 5.53% 7.4 5s
H79951 32625 0.9300085 0.98079 5.46% 7.5 5s
82848 34781 0.96645 51 34 0.93001 0.98076 5.46% 7.5 6s
107692 44370 infeasible 61 0.93001 0.98021 5.40% 7.7 7s
134856 54233 0.96480 59 37 0.93001 0.97961 5.33% 7.7 8s
154050 61365 0.96942 50 37 0.93001 0.97934 5.30% 7.7 9s
H154222 61365 0.9300085 0.97934 5.30% 7.7 9s
178876 69725 0.96591 56 39 0.93001 0.97888 5.25% 7.8 10s
203745 78408 infeasible 62 0.93001 0.97852 5.22% 7.8 11s
227741 86388 0.97440 49 42 0.93001 0.97817 5.18% 7.8 12s
H233283 87887 0.9300085 0.97810 5.17% 7.8 12s
H239472 89557 0.9300085 0.97803 5.16% 7.8 12s
H248544 91873 0.9300085 0.97791 5.15% 7.8 12s
248653 92377 infeasible 54 0.93001 0.97789 5.15% 7.8 13s
272648 99502 infeasible 68 0.93001 0.97761 5.12% 7.9 14s
H291251 104226 0.9300085 0.97740 5.10% 7.9 14s
H292862 104678 0.9300085 0.97739 5.09% 7.9 14s
295332 106114 infeasible 58 0.93001 0.97735 5.09% 7.9 15s
H301941 107672 0.9300085 0.97728 5.08% 7.9 15s
316221 113028 infeasible 65 0.93001 0.97715 5.07% 7.9 16s
342224 120316 infeasible 65 0.93001 0.97693 5.05% 8.0 17s
H348748 121305 0.9300085 0.97687 5.04% 8.0 17s
H352036 122234 0.9300085 0.97685 5.04% 8.0 17s
361585 126244 0.96536 54 34 0.93001 0.97678 5.03% 8.0 18s
385087 133117 infeasible 63 0.93001 0.97656 5.01% 8.0 19s
410867 140056 0.93129 59 44 0.93001 0.97636 4.98% 8.0 20s
433540 145211 infeasible 59 0.93001 0.97619 4.97% 8.0 21s
458845 152187 infeasible 66 0.93001 0.97599 4.94% 8.0 22s
H460260 152187 0.9300085 0.97599 4.94% 8.0 22s
H462279 152819 0.9300085 0.97597 4.94% 8.0 22s
478935 158685 0.95336 55 47 0.93001 0.97585 4.93% 8.0 23s
504662 166828 infeasible 54 0.93001 0.97571 4.91% 8.0 24s
527166 172959 0.94089 80 48 0.93001 0.97556 4.90% 8.0 25s
551924 179038 0.96633 54 43 0.93001 0.97539 4.88% 8.0 26s
574583 184746 infeasible 55 0.93001 0.97522 4.86% 8.0 27s
H597275 189919 0.9300085 0.97507 4.85% 8.0 27s
599369 190186 infeasible 54 0.93001 0.97506 4.84% 8.0 28s
H603283 191489 0.9300085 0.97505 4.84% 8.0 28s
617763 194408 0.93087 59 44 0.93001 0.97494 4.83% 8.0 29s
640301 200450 0.95679 58 47 0.93001 0.97481 4.82% 8.0 30s
652910 203247 infeasible 51 0.93001 0.97474 4.81% 8.0 31s
674828 209920 infeasible 56 0.93001 0.97461 4.80% 8.0 32s
700248 215805 0.95419 57 39 0.93001 0.97448 4.78% 8.0 33s
H719987 219616 0.9300085 0.97437 4.77% 8.0 33s
722700 220766 0.95977 62 49 0.93001 0.97435 4.77% 8.0 34s
H722807 220766 0.9300085 0.97435 4.77% 8.0 34s
742649 225739 0.96973 57 47 0.93001 0.97423 4.75% 8.0 35s
765732 230853 0.97024 54 48 0.93001 0.97411 4.74% 8.0 36s
H776601 232985 0.9300085 0.97406 4.74% 8.0 36s
H778594 233108 0.9300085 0.97405 4.74% 8.0 36s
H780213 233317 0.9300085 0.97405 4.74% 8.0 36s
H782784 234359 0.9300085 0.97403 4.73% 8.0 36s
783527 234735 0.97377 48 42 0.93001 0.97403 4.73% 8.0 37s
H784375 234735 0.9300085 0.97403 4.73% 8.0 37s
807733 240780 0.93188 55 53 0.93001 0.97391 4.72% 8.0 38s
H810207 240926 0.9300085 0.97390 4.72% 8.0 38s
H810310 240926 0.9300085 0.97390 4.72% 8.0 38s
H812362 241447 0.9300085 0.97389 4.72% 8.0 38s
H819040 242850 0.9300085 0.97385 4.71% 8.0 38s
825872 244068 infeasible 60 0.93001 0.97381 4.71% 8.0 39s
848587 249692 cutoff 61 0.93001 0.97369 4.70% 8.0 40s
873892 255089 infeasible 62 0.93001 0.97357 4.68% 7.9 41s
H882569 256652 0.9300085 0.97353 4.68% 7.9 41s
H888737 258010 0.9300085 0.97350 4.68% 7.9 41s
H889147 258010 0.9300085 0.97350 4.68% 7.9 41s
893308 259360 0.95458 58 40 0.93001 0.97347 4.67% 7.9 42s
918629 265559 infeasible 67 0.93001 0.97336 4.66% 7.9 43s
940879 269411 infeasible 61 0.93001 0.97326 4.65% 7.9 44s
H940987 269411 0.9300085 0.97326 4.65% 7.9 44s
H942146 269528 0.9300085 0.97326 4.65% 7.9 44s
H944782 270681 0.9300085 0.97325 4.65% 7.9 44s
H952239 272569 0.9300085 0.97322 4.65% 7.9 44s
959160 274077 0.93459 62 46 0.93001 0.97318 4.64% 7.9 45s
981866 279112 0.97064 52 46 0.93001 0.97308 4.63% 7.9 46s
1006933 284010 0.96281 54 43 0.93001 0.97299 4.62% 7.9 47s
H1022406 286607 0.9300085 0.97291 4.61% 7.9 47s
1025612 287745 infeasible 52 0.93001 0.97291 4.61% 7.9 48s
H1029864 288160 0.9300085 0.97288 4.61% 7.8 48s
1048457 292138 infeasible 56 0.93001 0.97280 4.60% 7.8 49s
1071402 297613 infeasible 52 0.93001 0.97270 4.59% 7.8 50s
1091970 301606 infeasible 66 0.93001 0.97262 4.58% 7.8 51s
H1094378 301998 0.9300086 0.97262 4.58% 7.8 51s
1112752 306582 0.95280 51 47 0.93001 0.97253 4.57% 7.8 52s
1135483 311830 0.93282 69 44 0.93001 0.97245 4.56% 7.8 53s
H1148747 314764 0.9300086 0.97240 4.56% 7.8 53s
1157524 316784 0.94491 61 50 0.93001 0.97237 4.55% 7.8 54s
1174253 320643 infeasible 58 0.93001 0.97231 4.55% 7.7 55s
1201030 326832 0.96452 63 51 0.93001 0.97221 4.54% 7.7 56s
1226238 332267 0.94929 53 37 0.93001 0.97212 4.53% 7.7 57s
1252722 337920 cutoff 61 0.93001 0.97204 4.52% 7.7 58s
H1266806 340699 0.9300086 0.97199 4.51% 7.6 58s
H1274516 341926 0.9300086 0.97197 4.51% 7.6 58s
1278788 343022 0.96904 58 41 0.93001 0.97195 4.51% 7.6 59s
H1281275 343022 0.9300086 0.97195 4.51% 7.6 59s
1301551 348194 infeasible 68 0.93001 0.97188 4.50% 7.6 60s-
A few things from your log that usually explain slow bound movement here.
1) Nearly all your constraints are equalities defining auxiliary products/powers (u1_sq = u1^2, c1_1_sq = c1_1^2, d1_c1_1_sq = c1_1_sq * x, …). Each bilinear equality gets spatial branching, and the relaxation of a product is only as tight as the bounds on its factors. If x, y, z, u1, r1, r2, c1_* have loose or infinite bounds, the McCormick relaxation is nearly useless: heuristics find incumbents fast but the dual bound crawls. Putting tight finite lower/upper bounds on every variable appearing inside a product is by far the highest-leverage fix, often orders of magnitude.
2) You chain products (c1_1 → c1_1_sq → d1_c1_1_sq). Each extra auxiliary level adds relaxation gap. Substitute out a level where you can, or express the composite term as one general constraint instead of two nested bilinears.
3) Parameters, in order:
- MIPGapAbs 0.01 with an objective near 0.93 is roughly a 1% absolute tolerance, so it is competing with your MIPGap; one of the two is doing nothing. Pick one.
- FuncNonlinear=1 for the pow/abs general constraints (Gurobi 11+) gives exact handling instead of a fine piecewise approximation that bloats the model.
- Try Presolve=2 and Cuts=2. Also try Heuristics=0.05: your log has a lot of H-lines, i.e. time spent in heuristics that are not helping the bound.
- Method=2 at the root is fine, but barrier at every node on a small model is often slower than dual simplex; check NodeMethod.
4) Coefficient ranges look clean (1e+00), but check bound ranges too: “big enough” bounds like 1e+6 behave like infinite bounds for the relaxation.
If the gap is still stuck after tightening bounds, write the model out (model.write("m.lp")) and post it - it is much easier to see where the relaxation is weak.
0
Please sign in to leave a comment.
Comments
1 comment