Skip to main content

MILP with quadratic constraints taking too long to solve

Answered
vishnuvardhan mahamkali
  • Gurobi-versary
  • First Comment
  • First Question

Hello,

I have a MILP model with one quadratic constraint in the form xT@A@x <= b. Without adding the quadratic constraint, model solves quickly. When I add the Qconstraint, model.optimize keeps running for a long time (for days without returning any solution). 

Can anyone please help me with this. Thanks very much

I'm using gurobipy. Model has 2536 constraints.

 

thanks

vishnu

1

Comments

7 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    Edited
    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?.
  • Sonja Mars
    • Gurobi Staff

    Hi Vishnu,

    Can you post some parts of your log file of a run with the quadratic constraint? If Gurobi runs for day, the full log file might be a bit too much, but maybe the log until the roughly 100 nodes of the Branch-and-Bound tree are solved. 

    Also when you say "quickly" for the linear model, how long did this take?

    Thanks,

      Sonja

    0
  • vishnuvardhan mahamkali
    • Gurobi-versary
    • First Comment
    • First Question

    Hi Sonja,

    Thanks for your reply.

    Linear model solved in about 5 ms. Please see the log with Quadratic constraint below.

     

    Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (linux64)
    Optimize a model with 2568 rows, 3163 columns and 29406 nonzeros
    Model fingerprint: 0x71cabda7
    Model has 1 quadratic constraint
    Variable types: 2419 continuous, 744 integer (744 binary)
    Coefficient statistics:
    Matrix range [2e-06, 1e+04]
    QMatrix range [1e-13, 2e+02]
    QLMatrix range [2e-01, 6e+03]
    Objective range [1e+00, 1e+00]
    Bounds range [1e-02, 2e+06]
    RHS range [3e-04, 1e+05]
    QRHS range [2e+07, 2e+07]
    Warning: Quadratic constraint contains large coefficient range
    Consider reformulating model or setting NumericFocus parameter
    to avoid numerical issues.
    Variable types: 2417 continuous, 746 integer (744 binary)

    Root relaxation: objective 8.106607e-01, 731 iterations, 0.04 seconds

    Nodes | Current Node | Objective Bounds | Work
    Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

    0 0 0.81066 0 37 - 0.81066 - - 0s
    0 0 0.81066 0 39 - 0.81066 - - 0s
    0 0 0.81066 0 38 - 0.81066 - - 0s
    0 0 0.81066 0 25 - 0.81066 - - 0s
    0 0 0.81066 0 26 - 0.81066 - - 0s
    0 0 0.81066 0 11 - 0.81066 - - 0s
    0 0 0.81066 0 11 - 0.81066 - - 0s
    0 0 0.81066 0 10 - 0.81066 - - 0s
    0 0 0.81066 0 10 - 0.81066 - - 0s
    0 0 0.81066 0 8 - 0.81066 - - 0s
    0 0 0.81066 0 5 - 0.81066 - - 0s
    0 0 0.81066 0 5 - 0.81066 - - 0s
    0 0 0.81066 0 5 - 0.81066 - - 0s
    0 0 0.81066 0 9 - 0.81066 - - 0s
    0 0 0.81066 0 9 - 0.81066 - - 0s
    H 0 0 -0.0000000 0.81066 - - 0s
    0 2 0.81066 0 9 -0.00000 0.81066 - - 0s
    1816 451 0.81065 30 - -0.00000 0.81065 - 25.7 5s
    3894 1239 0.81065 33 4 -0.00000 0.81065 - 22.8 10s
    5523 1748 0.67710 43 - -0.00000 0.81065 - 22.6 15s
    6653 2010 0.81065 42 - -0.00000 0.81065 - 23.9 20s
    7566 2194 0.60525 55 - -0.00000 0.81065 - 23.9 25s
    8446 2339 0.81065 43 - -0.00000 0.81065 - 23.8 30s
    9060 2440 0.55093 50 1 -0.00000 0.81065 - 23.8 35s
    9647 2509 0.51771 52 - -0.00000 0.81065 - 24.0 40s
    10167 2590 0.22285 50 - -0.00000 0.81065 - 24.4 45s
    10581 2642 0.73976 53 - -0.00000 0.81065 - 24.8 51s
    10976 2708 0.08106 55 - -0.00000 0.81065 - 25.0 55s
    11384 2756 0.81065 45 - -0.00000 0.81065 - 25.3 60s
    11707 2795 0.17424 53 - -0.00000 0.81065 - 25.6 65s
    12015 2801 0.17424 53 - -0.00000 0.81065 - 26.1 70s
    12298 2828 0.17262 56 - -0.00000 0.81065 - 26.4 75s
    12589 2846 0.81065 42 - -0.00000 0.81065 - 26.8 81s
    12806 2859 0.81065 45 - -0.00000 0.81065 - 27.0 85s
    13067 2867 0.81065 45 - -0.00000 0.81065 - 27.2 90s
    13357 2896 0.81065 41 - -0.00000 0.81065 - 27.5 96s
    13595 2907 0.81065 45 - -0.00000 0.81065 - 27.6 100s
    13851 2915 0.81065 45 - -0.00000 0.81065 - 27.8 105s
    14068 2927 0.81065 45 - -0.00000 0.81065 - 28.0 110s
    14281 2947 0.81065 45 - -0.00000 0.81065 - 28.1 115s
    14555 2959 0.81065 45 - -0.00000 0.81065 - 28.3 121s
    14740 2959 0.81065 45 - -0.00000 0.81065 - 28.5 126s
    14927 2972 0.81065 40 - -0.00000 0.81065 - 28.7 130s
    15122 2978 0.81065 45 - -0.00000 0.81065 - 28.9 135s
    15306 2984 0.81065 45 - -0.00000 0.81065 - 29.0 141s
    15478 2993 0.81065 45 - -0.00000 0.81065 - 29.2 146s
    15634 2987 0.81065 45 - -0.00000 0.81065 - 29.5 151s
    15820 3013 0.81065 48 - -0.00000 0.81065 - 29.6 156s

    I tried to warm start the problem with solution from model with only linear constraints, then model is stuck for a long time and didn't start branch and bound for couple of hours before I killed the process.

    I wonder if this is because of the large coefficient range in the quadratic constraint ?

    Thanks for your help

    Vishnu

    0
  • Sonja Mars
    • Gurobi Staff

    Hi Vishnu,

    This model suffers from bad numerics. The coefficient range of the quadratic constraint is really huge. Where are these small coefficients coming from? 

    You might want to look at our numerics guidelines to get some hints on how to handle these issues.

    Best,

    Sonja

    0
  • vishnuvardhan mahamkali
    • Gurobi-versary
    • First Comment
    • First Question

    Hi Sonja,

    Thanks for your reply. The idea was to add a ellipsoid constraint using inverse of covariance matrix. I checked the min and max float values in the matrix and they look fine.

    I have done this to add quadratic constraint

    q_expr = QuadExpr()

    q_expr.addTerms(val, ind1_vars, ind2_vars)

    min and max of val is 0 and 163.0366 respectively and I haven't noticed any small numbers. I am not sure what I am doing wrong. The covariance matrix is not rank deficient, I have removed all the linearly dependent rows.

    Am I doing something wrong?

     

    Thanks

    Vishnu

    0
  • Sonja Mars
    • Gurobi Staff

    Hi Vishnu,

    I am not sure I understand.

    I was pointing to the range of your matrix coefficients. You have some numbers in there that are 0.0000000000001. This is still positive and if there is real zero somewhere the minimum will be a zero. However, still this small numbers on the one hand and 200 on the other hand in a single quadratic constraint make it hard for the solver to draw any conclusion. You should really try to find the source of those small coefficients and see if they are necessary.

    Best,

      Sonja

    0
  • vishnuvardhan mahamkali
    • Gurobi-versary
    • First Comment
    • First Question

    Hi Sonja,

    Sorry, my bad. I was mistaken. Data browser in my editor didn't show those really small floats. Indeed, there are really small numbers. It make sense, that is really a broad range of numbers in quadratic coefficients. May be it would be right to get rid of them. Thanks for your help.

    Vishnu

    0

Post is closed for comments.

Didn't find what you were looking for?

New post