Skip to main content

QP solver works in an unstable way.

Answered
Hongyu Zhang
  • Edited
Gurobi-versary
First Comment
First Question

Hi, I encountered the problem that QP solver works in an unstable way. I am solving the QP problems at every iteration. This QP problem is one step in a modified Benders type algorithm. At every iteration, 756 new constraints (cuts) are added to the problem. For the first 23 iterations the solver works ok. However, the QP solver suddenly takes much more time to solve after the 23 iterations. 

For example at iteration 23, the log is:

Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 164054 rows, 107382 columns and 1338753 nonzeros
Model fingerprint: 0xc2fda6a2
Model has 1876 quadratic objective terms
Coefficient statistics:
Matrix range [3e-08, 9e+04]
Objective range [4e-11, 2e+01]
QObjective range [7e-02, 2e+00]
Bounds range [6e-01, 3e+05]
RHS range [1e-01, 2e+05]
Warning: Model contains large matrix coefficient range
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Presolve removed 109551 rows and 60994 columns
Presolve time: 0.45s
Presolved: 54503 rows, 46388 columns, 789446 nonzeros
Presolved model has 1876 quadratic objective terms
Ordering time: 0.53s
Ordering time: 1.20s

Barrier statistics:
Dense cols : 62
AA' NZ : 1.796e+06
Factor NZ : 1.611e+07 (roughly 170 MBytes of memory)
Factor Ops : 6.055e+09 (less than 1 second per iteration)
Threads : 8

Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 6.48426994e+13 -1.95781010e+14 3.53e+07 2.39e+05 7.83e+10 2s
1 2.30780707e+13 -1.48965948e+14 1.91e+07 1.30e+05 4.56e+10 2s
2 9.17891136e+12 -1.33874808e+14 1.15e+07 7.82e+04 3.07e+10 2s
3 7.91137041e+11 -1.10030794e+14 3.51e+06 2.38e+04 1.15e+10 3s
4 2.17837548e+11 -8.89072421e+13 1.93e+06 1.31e+04 6.78e+09 3s
5 6.03769303e+10 -7.85266738e+13 1.04e+06 7.03e+03 4.37e+09 3s
6 3.61265994e+09 -4.91634200e+13 2.42e+05 1.64e+03 1.36e+09 3s
7 1.22959900e+09 -3.84134934e+13 1.33e+05 9.01e+02 9.15e+08 3s
8 6.77854454e+08 -3.02708227e+13 9.64e+04 6.54e+02 7.27e+08 3s
9 2.54139180e+08 -2.18700152e+13 5.69e+04 3.86e+02 5.12e+08 3s
10 1.67321977e+08 -1.87392597e+13 4.53e+04 3.08e+02 4.32e+08 4s
11 6.48426994e+13 -1.95781010e+14 3.53e+07 2.39e+05 7.83e+10 4s
12 2.99831742e+11 -3.34320097e+12 2.22e+06 1.51e+04 5.52e+08 4s
13 2.43309692e+10 -8.10105087e+11 5.90e+05 3.93e+03 6.64e+07 4s
14 1.54235357e+09 -1.78797505e+11 1.41e+05 9.36e+02 7.90e+06 4s
15 2.23435394e+08 -6.80312249e+10 5.36e+04 3.57e+02 2.24e+06 4s
16 1.05231586e+08 -4.58000748e+10 3.61e+04 2.40e+02 1.35e+06 4s
17 5.33354313e+07 -3.08732269e+10 2.43e+04 1.62e+02 8.34e+05 5s
18 2.23223875e+07 -1.88637387e+10 1.48e+04 9.88e+01 4.80e+05 5s
19 2.37706916e+06 -4.87406691e+09 3.84e+03 2.56e+01 1.08e+05 5s
20 1.24593691e+06 -3.39225923e+09 2.67e+03 1.78e+01 6.95e+04 5s
21 4.55461665e+05 -1.86016525e+09 1.46e+03 9.74e+00 3.34e+04 5s
22 2.75024024e+05 -1.34176297e+09 1.06e+03 7.03e+00 2.26e+04 5s
23 1.52878349e+05 -9.07675288e+08 7.13e+02 4.75e+00 1.40e+04 6s
24 8.06500345e+04 -5.56255713e+08 4.37e+02 2.91e+00 7.81e+03 6s
25 5.77189648e+04 -4.10229971e+08 3.22e+02 2.15e+00 5.48e+03 6s
26 5.16328832e+04 -3.66510614e+08 2.88e+02 1.92e+00 4.82e+03 6s
27 3.47356116e+04 -2.36157205e+08 1.85e+02 1.23e+00 2.95e+03 6s
28 3.01151007e+04 -1.90166354e+08 1.49e+02 9.94e-01 2.31e+03 6s
29 2.23818033e+04 -1.10377007e+08 8.66e+01 5.77e-01 1.27e+03 7s
30 1.85170060e+04 -6.42490949e+07 5.04e+01 3.36e-01 7.12e+02 7s
31 1.71181663e+04 -4.73409797e+07 3.72e+01 2.47e-01 5.15e+02 7s
32 1.49475469e+04 -1.68368396e+07 1.32e+01 8.79e-02 1.76e+02 7s
33 1.31215513e+04 -2.05208999e+06 1.61e+00 1.07e-02 2.11e+01 7s
34 1.00292399e+04 -2.76420971e+05 2.27e-01 1.51e-03 2.91e+00 7s
35 8.53543189e+03 -1.95526428e+05 1.64e-01 1.09e-03 2.08e+00 7s
36 8.17136737e+03 -1.72343632e+05 1.46e-01 9.69e-04 1.84e+00 8s
37 7.89546501e+03 -1.60723517e+05 1.36e-01 9.08e-04 1.71e+00 8s
38 7.02957960e+03 -1.32061015e+05 1.14e-01 7.57e-04 1.41e+00 8s
39 6.36319538e+03 -1.12625997e+05 9.83e-02 6.54e-04 1.21e+00 8s
40 5.94751134e+03 -1.01019910e+05 8.90e-02 5.92e-04 1.09e+00 8s
41 4.89409241e+03 -8.14138282e+04 7.26e-02 4.83e-04 8.77e-01 8s
42 4.82765154e+03 -7.95756578e+04 7.11e-02 4.73e-04 8.57e-01 8s
43 4.49253510e+03 -7.09301469e+04 6.40e-02 4.26e-04 7.66e-01 9s
44 4.06926048e+03 -6.20694963e+04 5.67e-02 3.77e-04 6.72e-01 9s
45 2.91914045e+03 -3.86666099e+04 3.70e-02 2.46e-04 4.22e-01 9s
46 2.33954512e+03 -2.79061760e+04 2.75e-02 1.83e-04 3.07e-01 9s
47 1.73989926e+03 -1.77681331e+04 1.83e-02 1.22e-04 1.98e-01 9s
48 1.10610644e+03 -1.06390454e+04 1.17e-02 7.76e-05 1.19e-01 9s
49 8.24671446e+02 -7.44495159e+03 8.67e-03 5.77e-05 8.38e-02 10s
50 5.15422456e+02 -4.64783175e+03 5.67e-03 3.78e-05 5.23e-02 10s
51 2.97241338e+02 -2.69311150e+03 3.49e-03 2.32e-05 3.02e-02 10s
52 1.98086373e+02 -1.85105945e+03 2.47e-03 1.64e-05 2.07e-02 10s
53 1.41178629e+02 -1.38133525e+03 1.87e-03 1.25e-05 1.54e-02 10s
54 8.30805446e+01 -8.87014487e+02 1.22e-03 8.15e-06 9.79e-03 10s
55 5.47577519e+01 -5.98521969e+02 8.85e-04 5.89e-06 6.59e-03 10s
56 3.78199633e+01 -4.51993998e+02 6.48e-04 4.31e-06 4.94e-03 11s
57 2.85885779e+01 -3.84966836e+02 4.79e-04 3.19e-06 4.16e-03 11s
58 2.27839752e+01 -3.12861197e+02 4.00e-04 2.66e-06 3.37e-03 11s
59 1.63470815e+01 -2.37402301e+02 2.75e-04 1.83e-06 2.55e-03 11s
60 1.22887280e+01 -1.86459669e+02 2.07e-04 1.37e-06 1.99e-03 11s
61 1.11098501e+01 -1.70371677e+02 1.87e-04 1.24e-06 1.82e-03 11s
62 8.93789330e+00 -1.38729998e+02 1.44e-04 9.61e-07 1.48e-03 12s
63 7.41122958e+00 -1.16533131e+02 1.11e-04 7.39e-07 1.24e-03 12s
64 6.93434914e+00 -1.09336253e+02 1.05e-04 6.96e-07 1.16e-03 12s
65 6.78537877e+00 -1.07037751e+02 1.02e-04 6.82e-07 1.14e-03 12s
66 5.82949231e+00 -9.23652800e+01 8.46e-05 5.63e-07 9.82e-04 12s
67 5.06515293e+00 -7.95160040e+01 7.09e-05 4.72e-07 8.45e-04 12s
68 4.61638871e+00 -7.16159092e+01 6.42e-05 4.27e-07 7.62e-04 12s
69 4.13202163e+00 -6.43020115e+01 5.57e-05 3.71e-07 6.84e-04 13s
70 2.60266838e+00 -3.96274408e+01 3.23e-05 2.15e-07 4.22e-04 13s
71 2.22283189e+00 -3.37367968e+01 2.31e-05 1.54e-07 3.59e-04 13s
72 1.65543347e+00 -2.41542930e+01 1.13e-05 7.50e-08 2.57e-04 13s
73 1.36468987e+00 -1.81225617e+01 7.85e-06 5.22e-08 1.94e-04 13s
74 1.23950929e+00 -1.58639935e+01 6.56e-06 4.37e-08 1.70e-04 13s
75 1.00016329e+00 -1.12424539e+01 3.43e-06 2.28e-08 1.22e-04 14s
76 7.94250834e-01 -6.83743613e+00 1.30e-06 8.68e-09 7.57e-05 14s
77 6.07205738e-01 -2.83440051e+00 2.09e-07 1.39e-09 3.41e-05 14s
78 6.03943103e-01 -2.75740497e+00 1.89e-07 1.26e-09 3.33e-05 14s
79 5.56924660e-01 -9.73106797e-01 6.70e-09 4.46e-11 1.52e-05 14s
80 5.17702916e-01 -6.88815374e-02 4.10e-10 2.67e-12 5.81e-06 14s
81 5.05706078e-01 4.30962307e-01 1.94e-11 1.98e-13 7.41e-07 15s
82 5.04461712e-01 4.86505491e-01 2.12e-11 4.20e-14 1.78e-07 15s
83 5.04083134e-01 5.03659707e-01 9.16e-12 7.91e-16 4.20e-09 15s
84 5.04074193e-01 5.04073703e-01 2.08e-11 1.58e-15 4.85e-12 15s

Barrier solved model in 84 iterations and 15.15 seconds
Optimal objective 5.04074193e-01


User-callback calls 36246, time in user-callback 0.07 sec

However, when I am at iteration 24,

It is:

Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 164810 rows, 107382 columns and 1376563 nonzeros
Model fingerprint: 0xd65e127c
Model has 1876 quadratic objective terms
Coefficient statistics:
Matrix range [3e-08, 9e+04]
Objective range [4e-11, 2e+01]
QObjective range [7e-02, 2e+00]
Bounds range [6e-01, 3e+05]
RHS range [1e-01, 2e+05]
Warning: Model contains large matrix coefficient range
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Presolve removed 109633 rows and 60916 columns
Presolve time: 0.46s
Presolved: 55177 rows, 46466 columns, 818354 nonzeros
Presolved model has 1876 quadratic objective terms
Ordering time: 0.65s
Elapsed ordering time = 5s
Elapsed ordering time = 6s
Elapsed ordering time = 8s
Elapsed ordering time = 10s
Elapsed ordering time = 10s
Ordering time: 11.01s

Barrier statistics:
AA' NZ : 3.933e+07
Factor NZ : 7.830e+08 (roughly 6.0 GBytes of memory)
Factor Ops : 1.651e+13 (roughly 70 seconds per iteration)
Threads : 8

Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 6.63854293e+13 -1.94541185e+14 3.55e+07 2.42e+05 7.75e+10 120s
1 1.44911927e+13 -1.37385643e+14 1.50e+07 1.02e+05 3.47e+10 228s

 

As you can see, I stop the solver because it is clearly something different happened at iteration 24 and makes QP behaves badly. 

Could anyone tell me how can I fix this?

Many thanks!

0

Comments

4 comments

Date Votes
  • Official comment
    Simranjit Kaur
    Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    Hi,

    The number of nonzeros in the Barrier algorithm increases by 1 order of magnitude and the number of operations required to factor the \(AA^T\) matrix increases by 4 orders of magnitude from iteration 23 to iteration 24. This explains the increased computation time.
    This is very likely caused by numerical problems. The barrier algorithm is very prone to shaky numerics and the ranges of your coefficients are in \(\texttt{[3e-08,9e+04]}\). This is a range of 12 orders of magnitude(!), which means a very hard time for the barrier algorithm to work properly. You should have a look at the Guideline for Numerical Issues and try to rescale your model. This will very likely solve your problem.

    Crosspost to stackoverflow.

    Best regards,
    Jaromił

    1
  • Hongyu Zhang
    Gurobi-versary
    First Comment
    First Question

    Hi Jaromił Najman, 

    Thanks for your reply. I understood it should be numerical issues. I have read the numerical issues guideline, however, I think I cannot reformulate the model. I tried all parameters as well and they didn't work. I think another difference between these two iterations is dense column, in 23 we have 62 dense column but non in 24, it seems that Gurobi chose a different factorisation method in 24? 

    I think the major challenge in 24 is factorisation, is there any way to fix it to a certain method?

    I also checked my model and I don't even know where 3e-08 comes from, because all the parameters are in a reasonable range. Is there any way to locate where is this extremely small coefficient?

     

    Kind regards,

    Richard.

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    Hi Richard,

    How did you check your model? Did you use the Model.write() function in order to write an LP file and inspect it by hand? You can write an LP file before the optimization of each iteration. I don't think there is a better way other than fixing the coefficient ranges in order to make the barrier algorithm more stable.

    You could also try experimenting with the Presolve and PreSparsify parameters in order to reduce the number of nonzeros of your model.

    Best regards,
    Jaromił

    0

Post is closed for comments.

Didn't find what you were looking for?

New post