Skip to main content

Numerical Issues When Adding Var Bounds

Answered
Lukas Winkel
Gurobi-versary
Conversationalist
First Question

Hey everyone,

I am currently solving a variety of similar QPs. For some of those QP I run into numerical troubles, when adding upper and lower bounds on the variables, which I can not explain.

Here are two examples, the first working without problems, the second runs into problems. The only difference between the two is the addition of a linear term to the objective function (+ 0.5 * z_146) and the addition of a lower bound (0.5 <= z_146).

Example *.lp and log in comments!

Does anyone have a clue what is going on? SOlving both examples without the 0.5 bounds is possible without problems.

Regards
Lukas

0

Comments

5 comments

Date Votes
  • Lukas Winkel
    • Edited
    Gurobi-versary
    Conversationalist
    First Question

    Example 1:

    QP: https://seafile.rlp.net/f/7b9ccb57b96847bea7c9/

    Log:

    Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (linux64)
    Optimize a model with 500 rows, 250 columns and 29984 nonzeros
    Model fingerprint: 0x5d3ac412
    Model has 14992 quadratic objective terms
    Coefficient statistics:
    Matrix range     [2e-10, 1e+02]
    Objective range  [2e+00, 4e+03]
    QObjective range [4e-10, 1e+02]
    Bounds range     [5e-01, 1e+00]
    RHS range        [4e+00, 8e+03]
    Warning: Model contains large quadratic objective coefficient range
    Presolve removed 258 rows and 8 columns
    Presolve time: 0.01s
    Presolved: 242 rows, 242 columns, 29726 nonzeros
    Presolved model has 14984 quadratic objective terms

    Extra 182 simplex iterations after uncrush
    836 3.4238577e+02 0.000000e+00 0.000000e+00 1s

    Solved in 836 iterations and 1.08 seconds
    Optimal objective 3.423857678e+02


    Example 2:

    QP:https://seafile.rlp.net/f/2bb2b0dbbbdd49d9a0c5/

    Log:

    Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (linux64)
    Optimize a model with 500 rows, 250 columns and 29984 nonzeros
    Model fingerprint: 0xf78bebb8
    Model has 14992 quadratic objective terms
    Coefficient statistics:
    Matrix range     [2e-10, 1e+02]
    Objective range  [2e+00, 4e+03]
    QObjective range [4e-10, 1e+02]
    Bounds range     [5e-01, 1e+00]
    RHS range.       [4e+00, 8e+03]
    Warning: Model contains large quadratic objective coefficient range
    Presolve removed 258 rows and 8 columns
    Presolve time: 0.01s
    Presolved: 242 rows, 242 columns, 29726 nonzeros
    Presolved model has 14984 quadratic objective terms

    Warning: 1 variables dropped from basis
    ...
    Warning: 1 variables dropped from basis
    2886 3.6225607e+10 0.000000e+00 2.441409e+11 5s
    Warning: 1 variables dropped from basis
    ...
    Warning: 1 variables dropped from basis

    Stopped in 3184 iterations and 5.84 seconds
    Numeric error
    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    Hi Lukas,

    This seemingly unexpected behavior is most likely due to the fact that the coefficient ranges in your Matrix and QObjectiveMatrix reach from 1e-10 to 1e2. This is already bad for linear problems, for quadratic problems, this is even worse! With these numerics, even a seemingly small change to the model may already affect the solution process and end up in a numerical disaster due to, e.g., a different simplex basis or not recognizing whether a Matrix is PSD.

    The good news is that the latest Gurobi version 9.1 solves both problems seemingly without numerical issues. Thus, if possible I would recommend to upgrade to the latest version. This does not mean that you should not have a closer look at your coefficients and try to improve the ranges of those. You could start by having a look at our Guidelines for Numerical Issues.

    My colleague Ed Klotz has published a great article on numerical issues in MIPs which may be applicable for QPs in your case. It is definitely worth a read when tackling numerically unstable problems!

    Best regards,
    Jaromił

    0
  • Lukas Winkel
    Gurobi-versary
    Conversationalist
    First Question

    Thank you for the fast reply, Jaromil!

    Updating Gurobi is a good idea. Curiously, the version was not the problem, but a parameter change I forgot about was the issue.

    While we are at it, do you maybe know what is going on here? I added a SOC-constraint and the solver is not able to handle it.

    *.lp: https://seafile.rlp.net/f/0b8ae8802f5a4e429f0d/

    Log:

    Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (linux64)
    Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
    Optimize a model with 100 rows, 50 columns and 2398 nonzeros
    Model fingerprint: 0x0905a5e0
    Model has 1199 quadratic objective terms
    Model has 2 quadratic constraints
    Coefficient statistics:
    Matrix range [1e-07, 9e+01]
    QMatrix range [2e-07, 9e+01]
    QLMatrix range [3e+01, 1e+04]
    Objective range [9e+00, 4e+03]
    QObjective range [2e-07, 9e+01]
    Bounds range [1e+00, 1e+00]
    RHS range [2e+01, 8e+03]
    QRHS range [3e+06, 3e+06]
    Warning: Only barrier available for SOCP models
    Presolve removed 50 rows and 0 columns
    Presolve time: 0.00s
    Presolved: 205 rows, 206 columns, 6245 nonzeros
    Presolved model has 3 second-order cone constraints
    Ordering time: 0.00s

    Barrier statistics:
    AA' NZ : 2.043e+04
    Factor NZ : 2.066e+04
    Factor Ops : 2.776e+06 (less than 1 second per iteration)
    Threads : 1

    Objective Residual
    Iter Primal Dual Primal Dual Compl Time
    0 -6.85525667e+06 -1.05152215e+06 1.69e+05 7.90e+00 4.24e+04 0s
    1 -3.20318642e+06 -1.63051940e+05 6.25e+04 1.02e+00 1.44e+04 0s
    2 -2.61533425e+06 7.52860752e+05 3.88e+04 7.97e-01 8.65e+03 0s
    3 -2.86156260e+06 -1.10784854e+05 2.30e+04 6.79e-01 7.18e+03 0s
    4 -4.24464126e+06 -5.44285193e+05 1.89e+04 6.94e-01 1.92e+04 0s
    5 -6.90971920e+06 2.06445893e+06 4.81e+04 1.92e+00 2.86e+05 0s
    6* -7.52224821e+06 1.03513278e+07 6.34e+02 3.33e-01 2.40e+02 0s
    7* -1.12587815e+07 2.47776606e+07 8.08e+01 6.82e-01 5.60e+02 0s
    8 -5.51629142e+06 -3.26365808e+06 3.82e+02 1.56e+00 4.33e+05 0s
    9 -2.31581301e+06 -3.17638325e+06 7.13e+01 3.44e-01 7.48e+04 0s
    10 -1.24065079e+06 -1.12313817e+06 2.74e+01 4.69e-02 1.46e+04 0s
    11 -9.52671555e+05 -6.61299534e+05 1.37e+01 6.67e-03 5.05e+03 0s
    12 -5.87700755e+05 -3.07327385e+05 5.62e+00 9.35e-03 2.11e+03 0s
    13 -2.33660288e+05 -1.26701861e+05 1.63e+00 1.12e-02 6.57e+02 0s
    14 -8.24381814e+04 -6.20613262e+04 7.24e-01 1.27e-02 4.33e+02 0s
    15 8.85244294e+03 -2.68259479e+04 1.31e-03 1.58e-03 1.36e+02 0s
    16 1.33992876e+03 -1.01253835e+03 1.66e-03 2.52e-02 8.98e+00 0s
    17 3.54067267e+02 -1.82575693e+02 4.98e-04 8.97e-01 2.06e+00 0s
    18 5.76567158e+01 -3.22885387e+01 2.36e-04 1.10e+00 3.48e-01 0s
    19 -5.91894041e+00 -4.02077453e+00 3.58e-04 7.95e+00 4.84e-02 0s
    20 -8.83861539e-01 -3.87557768e-01 1.59e-04 4.58e+01 4.31e-03 0s
    21 -3.44625780e-01 -9.66819855e-02 1.42e-04 1.04e+03 1.35e-03 0s
    22 -6.45580172e-02 -2.39000210e-01 3.26e-04 3.50e+05 1.11e-03 0s
    23 9.87041308e-04 -5.64814303e-03 1.35e-04 7.49e+02 1.34e-04 0s
    24 -7.01948296e-04 -1.21719013e-03 2.35e-02 2.51e+02 4.23e-06 0s
    25 4.54459362e-04 1.24015243e-03 1.32e-02 1.35e+03 7.92e-06 0s
    26 -2.26349979e-03 -3.65999858e-03 3.30e-02 3.19e+02 3.90e-05 0s
    27 1.37899826e-03 -6.02722059e-04 2.25e-02 5.76e+02 3.12e-05 0s
    28 1.39850370e-03 -8.45377432e-03 7.70e-03 3.95e+01 5.00e-05 0s
    29 -9.53687056e-04 -9.89684610e-04 1.21e-04 3.37e+02 2.68e-06 0s
    30 -1.79051772e-03 -1.88022223e-03 4.21e-03 6.71e+03 3.78e-06 0s
    31 -5.54073031e-04 -7.37661403e-04 2.28e-03 1.39e+04 2.92e-06 0s
    32 -5.72125035e-03 -7.29370961e-03 5.62e-02 5.51e+04 1.93e-04 0s
    33 -5.46900397e-03 -7.16283996e-03 5.52e-02 5.46e+04 1.90e-04 0s
    34 -1.67637837e-02 -6.78080766e-03 3.26e-02 5.29e+04 1.77e-04 0s
    35 -9.25178067e-03 -5.64651480e-03 1.80e-02 2.87e+04 9.84e-05 0s
    36 -5.04236257e-03 -4.20947968e-03 9.92e-03 1.55e+04 5.87e-05 0s
    37 -2.17998038e-02 -2.83169116e-02 2.05e-02 1.70e+04 1.54e-04 0s
    38 7.05297644e-04 6.91245510e-04 6.30e-03 5.65e+02 8.42e-06 0s
    39 -1.74039299e-03 -1.76833921e-03 3.09e-03 1.32e+03 1.62e-05 0s
    40 5.54296439e-05 7.17855815e-05 9.62e-04 7.39e+02 5.21e-06 0s
    41 1.41468729e-04 1.47618321e-04 4.49e-03 8.75e+02 4.22e-06 0s
    42 1.95693879e-03 1.23293950e-04 2.26e-02 5.87e+02 1.08e-05 0s
    43 -6.57219048e-05 -1.28814578e-03 1.36e-02 2.23e+03 9.00e-06 0s
    44 -1.21648179e-02 -4.96538127e-03 3.61e-02 3.35e+03 4.43e-05 0s
    45 -1.21406966e-02 -4.96094904e-03 3.61e-02 3.36e+03 4.43e-05 0s
    46 -8.89818017e-03 -4.94708065e-03 1.37e-01 3.16e+03 4.32e-05 0s
    47 -1.92954924e-02 -5.69246072e-03 7.54e-02 4.09e+03 6.62e-05 0s
    48 -1.75032879e-02 -6.06323714e-03 6.18e-02 3.39e+03 5.78e-05 0s
    49 -9.07262897e-03 -7.81815511e-03 3.43e-02 6.18e+03 7.04e-05 0s
    50 1.71321469e-03 1.63499380e-03 2.92e-03 4.14e+03 5.00e-07 0s
    51 -1.20900201e-03 -5.97027729e-05 3.84e-03 1.27e+05 1.34e-07 0s
    52 -1.48014752e-03 1.57123536e-05 2.97e-03 6.13e+04 5.83e-08 0s
    53 3.43167035e-01 1.47720665e-05 1.41e-03 9.30e+05 4.40e-05 0s

    Barrier performed 53 iterations in 0.07 seconds
    Numerical trouble encountered
    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    HI Lukas,

    Sorry for not getting back to you in the past days. It is possible that the underlying constraint matrix is almost singular resulting in numerical trouble. You could try setting the BarHomogeneous parameter to 1 or increasing the NumericFocus parameter in order to possibly overcome the numerical issues. The Jacobian of the quadratic variables is almost fully dense. You could try reformulating terms such as \(\sum_j z_i \cdot z_j\) as \(z_i \cdot w_i\) with the additional constraint \(w_i = \sum_j z_j\) to improve the numerics.

    The range of your QMatrix [2e-07, 9e+01] is still considered large, regarding the fact that you are solving a quadratic problem. You should try to reduce the range of the matrix if possible.

    Best regards,
    Jaromił

    0
  • Lukas Winkel
    Gurobi-versary
    Conversationalist
    First Question

    Thanks!

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post