Skip to main content

MIQP Model taking forever to compute

Answered
Gaurav Malik
  • Edited
Collaborator
Curious

Hello! 

I am trying to run an MIQP model with indicator constraints and it is taking forever to compute. I have already let it run for 4 days non-stop and still could not get it solved. Please find the .mps file on the following link: https://drive.google.com/file/d/1wcl_jurd4sbm4qCAi9PUjL67sYfe1yMT/view?usp=sharing 

I understand that the model size is fairly large. It has:

Model has 5024 quadratic objective terms
Model has 4632 general constraints
Variable types: 3015 continuous, 1544 integer (1544 binary)

And the Objective function has bilinear terms. 


However, the coefficient statistics do not look that bad:

Coefficient statistics:
  Matrix range     [9e-06, 2e+01]
  Objective range  [2e-04, 2e+02]
  QObjective range [2e-04, 2e+01]
  Bounds range     [1e+00, 2e+04]
  RHS range        [6e-02, 5e+02]
  GenCon rhs range [6e-02, 1e+02]
  GenCon coe range [9e-06, 2e+01]

So, my question is: Is this issue a fundamental issue of scaling in which Gurobi can't really help OR am I getting this issue due to some numerical or modelling error. Any help would be appreciated. 

P.S.- One of the continuous variable is negative while others are non-negative. If I make all of them non-negative, then it is solved (although also in quite some time) but I would really need that variable to be negative. 
P.S.2- Can you please let me know once you have accessed the .mps file. I will remove it from the link afterwards.

Related to

1

Comments

3 comments

Date Votes
  • Maliheh Aramon
    Gurobi Staff Gurobi Staff

    Hi, 

    The model numerics are not great mainly because the coefficient matrix spans over a wide range of 7 orders of magnitude. However, using Gurobi version 11.0.3 and NoRelHeurTime=60, the gap is around 8.4% in 2 minutes. Do you want to solve the model to optimality? 

    You can consider experimenting with different combinations of the parameters below:

    Best regards,

    Maliheh

    0
  • Gaurav Malik
    • Edited
    Collaborator
    Curious

    Hello Maliheh, 

     

    Thanks for the reply. The coefficient matrix only starts from 9e-6 which is almost 1e-5. Do you still think that it is a serious issue?
    I have already experimented with NoRelHeurTime parameter. It does help in finding good feasible solutions but the optimality is not proved. 
    MIPFocus=2 also doesn't change a lot. 

    I will try the other parameters.

    The optimality gap of 8% does not really tell anything in this case. I will be needing something more like 0.1%. Is there anything more that can be done?

    Thanks in advance!

    Regards

    Gaurav 

    0
  • Maliheh Aramon
    Gurobi Staff Gurobi Staff

    The coefficient matrix only starts from 9e-6 which is almost 1e-5. Do you still think that it is a serious issue?

    As explained in the Gurobi Numerical Guidelines section "Advanced User Scaling," we ideally prefer the matrix coefficient range to be within six orders of magnitude or less, specifically between 1e-3 and 1e6. There is no warning message in the log indicating that this is causing a numerical issue. However, better model numerics typically lead to better performance.

    Is there anything more that can be done?

    Based on the runs I conducted, the bottleneck in closing the gap appears to be slow progress in improving the best bound. The parameters previously shared focus on model strengthening and generating cutting planes more aggressively. You can add the parameters VarBranch=3 and BranchDir=1|-1 to the previous list to experiment with.

    Other suggestions include:

    • Define the tightest possible lower and upper bounds for all variables participating in the bilinear terms.
    • Consider potential reformulation ideas, if possible, to reduce the number of bilinear terms.

    Maliheh

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post