メインコンテンツへスキップ

Why is Gurobi taking too much time after finding the optimal solution?

回答済み
Khadija HADJ SALEM
  • Gurobi-versary
  • First Comment
  • First Question

Hi, 

I'm trying to solve a big ILP problem. The solution takes little time, less than 5 seconds (good news!)

But the problem is that Gurobi does some extra iterations that take a lot of time.

What is the purpose of these iterations? Is there an option to ignore them?

I am using the following parameters:

gurobi_params = {'TimeLimit':300, 'NodefileStart':0.5, 'Presolve':1, 'Symmetry': 1, 'Heuristics':0.05, 'Cuts': 1}

 

Below the output of Gurobi:

Gurobi Optimizer version 9.0.1 build v9.0.1rc0 (mac64)
Optimize a model with 352578 rows, 349206 columns and 3035395 nonzeros
Model fingerprint: 0xbb75fdcf
Variable types: 0 continuous, 349206 integer (347763 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+03]
Objective range [2e+01, 2e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 4e+00]
Found heuristic solution: objective 72900.000000
Presolve removed 347701 rows and 343620 columns
Presolve time: 2.54s
Presolved: 4877 rows, 5586 columns, 59295 nonzeros
Variable types: 0 continuous, 5586 integer (4146 binary)
Root relaxation: objective 2.124210e+03, 2943 iterations, 0.63 seconds

Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 2124.20966 0 39 72900.0000 2124.20966 97.1% - 3s
H 0 0 44437.500000 2124.20966 95.2% - 3s
H 0 0 35167.500000 2124.20966 94.0% - 3s
H 0 0 34537.500000 2124.20966 93.8% - 4s
0 0 18345.3521 0 25 34537.5000 18345.3521 46.9% - 4s
0 0 18384.3493 0 26 34537.5000 18384.3493 46.8% - 5s
0 0 18571.6008 0 25 34537.5000 18571.6008 46.2% - 5s
0 0 20125.8886 0 21 34537.5000 20125.8886 41.7% - 6s
0 0 20214.9556 0 29 34537.5000 20214.9556 41.5% - 7s
0 0 20290.8973 0 23 34537.5000 20290.8973 41.2% - 7s
0 0 21583.9107 0 21 34537.5000 21583.9107 37.5% - 7s
0 0 21583.9107 0 27 34537.5000 21583.9107 37.5% - 7s
0 0 23915.1185 0 20 34537.5000 23915.1185 30.8% - 7s
0 0 26461.2849 0 12 34537.5000 26461.2849 23.4% - 7s
0 0 31275.0000 0 9 34537.5000 31275.0000 9.45% - 8s
H 0 0 32175.000000 31275.0000 2.80% - 8s
0 0 31275.0000 0 3 32175.0000 31275.0000 2.80% - 8s
0 0 31275.0000 0 30 32175.0000 31275.0000 2.80% - 8s
0 0 31275.0000 0 21 32175.0000 31275.0000 2.80% - 8s
H 0 0 31837.500000 31275.0000 1.77% - 8s
0 0 31275.0000 0 12 31837.5000 31275.0000 1.77% - 8s
0 0 31275.0000 0 11 31837.5000 31275.0000 1.77% - 8s
0 0 31275.0000 0 1 31837.5000 31275.0000 1.77% - 8s
* 0 0 0 31275.000000 31275.0000 0.00% - 8s

Cutting planes:
Gomory: 1
Cover: 2
MIR: 9
StrongCG: 6
GUB cover: 1
Zero half: 3
RLT: 1
Relax-and-lift: 10
Explored 1 nodes (4791 simplex iterations) in 8.38 seconds
Thread count was 1 (of 4 available processors)
Solution count 7: 31275 31837.5 32175 ... 72900
Optimal solution found (tolerance 1.00e-04)
Best objective 3.127500000000e+04, best bound 3.127500000000e+04, gap 0.0000%

Changed value of parameter Presolve to 0
Prev: 1 Min: -1 Max: 2 Default: -1
Gurobi Optimizer version 9.0.1 build v9.0.1rc0 (mac64)
Optimize a model with 352578 rows, 349206 columns and 3035395 nonzeros
Model fingerprint: 0xe607ebb8
Coefficient statistics:
Matrix range [1e+00, 1e+03]
Objective range [2e+01, 2e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 4e+00]
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 9.600000e+01 0.000000e+00 1s
478 1.7395601e-05 1.161036e+02 0.000000e+00 5s
1068 6.9486811e-05 1.198295e+02 0.000000e+00 11s
1568 2.3113483e-04 1.409482e+02 0.000000e+00 15s
1998 2.9597862e-04 1.780212e+02 0.000000e+00 21s
2358 3.3036883e-04 1.060322e+02 0.000000e+00 26s
2738 3.6378157e-04 1.135277e+02 0.000000e+00 30s
3392 7.6198176e+03 3.775868e+01 1.583990e+11 36s
7734 1.3791078e+04 1.576771e+01 2.386803e+12 40s
11816 1.3791078e+04 1.576771e+01 2.387224e+12 45s
14956 1.3791078e+04 1.576771e+01 2.387224e+12 50s
18724 1.3791078e+04 1.576771e+01 2.387224e+12 55s
22178 1.3791078e+04 1.576771e+01 2.387224e+12 60s
25632 1.3791078e+04 1.576771e+01 2.387224e+12 65s
30028 1.1554935e+04 0.000000e+00 2.059425e+07 70s
35366 3.3040972e+03 0.000000e+00 6.695145e+06 75s
41018 2.8391605e+03 0.000000e+00 6.155459e+05 80s
46984 2.4733519e+03 0.000000e+00 1.362413e+06 85s
51694 2.2948979e+03 0.000000e+00 2.395347e+05 90s
58916 2.1226743e+03 0.000000e+00 7.585140e+05 95s
65824 1.9534857e+03 0.000000e+00 7.572953e+04 100s
71790 1.9324472e+03 0.000000e+00 4.620954e+04 105s
73674 1.9220671e+03 0.000000e+00 2.211478e+06 111s
77128 1.9125714e+03 0.000000e+00 7.097591e+03 115s
81685 1.9136874e+03 0.000000e+00 0.000000e+00 119s

Solved in 81685 iterations and 119.11 seconds
Optimal objective 1.913687405e+03
0

コメント

6件のコメント

日付 投票
  • 正式なコメント
    Simranjit Kaur
    • 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
    編集済み

    Hi,

    There are 2 calls to Model.optimize() which can be seen at the 2 lines stating the Gurobi version

    Gurobi Optimizer version 9.0.1 build v9.0.1rc0 (mac64)

    Are you using a third party software to call Gurobi?

    Could you provide a minimal working example?

    Best regards,
    Jaromił

    0
  • Khadija HADJ SALEM
    • Gurobi-versary
    • First Comment
    • First Question

    Hi again, 

    I have a function (below) to compute the root relaxation of my model. So, for this reason, I have 2 calls to Model.Optimize(). 

    Best regards, 

    Khadija

    def compute_root_relax(model):
      r = model.relax()
      r.Params.Presolve=0 
      r.optimize()
      if (r.Status != GRB.OPTIMAL):
         print ("Root relaxation optimization status: ", r.Status)
      return r
    0
  • Jaromił Najman
    • Gurobi Staff

    Hi Khadija,

    Ok, so this explains the two optimizations.

    Just for my understanding. You are first optimizing your integer problem and get the solution 3.1274e+04. Next, you construct a relaxation of your integer problem using the relax() function, which solves your original model but the integer variables are relaxed to be continuous. Is there a particular reason for turning off the Presolve? Note that for your original integer problem which has been solved quickly, you did not turn off presolving. Presolve is in most cases essential for good performance.

    Best regards,
    Jaromił

    0
  • Khadija HADJ SALEM
    • Gurobi-versary
    • First Comment
    • First Question

    No, I have no specific reason to turn off the Presolve parameter. I just tried to compute the root relaxation of my model with Gurobi's default parameters.
    I tried to solve my model again by activating Presolve (= 1) when I call my function relax() and Gurobi takes over 120 seconds to solve my model with relaxed variables.

    So, is there another way to improve this?

    Thank again.

    Best regards!

    Khadija

    0
  • Jaromił Najman
    • Gurobi Staff
    編集済み

    Hi Khadija,

    It seems like the Presolve algorithms for integer variables are essential for simplifying and quickly solving the root relaxation. You could try and add one binary variable to the objective which is redundant, e.g., \( + b\) in the case of minimization. This might help.

    What exactly are you using the relaxed model for? Are you interested in the optimal solution of the relaxed model? You can access various information on the root relaxation during the first optimization run already by the use of callbacks. Thus, you maybe don't have to re-solve the relaxed model. In particular, you would use the MIPNODE callback.

    You could also try the Gurobi parameter tuning tool to find settings improving the solution performance of the relaxed model.

    Best regards,
    Jaromił

    0

投稿コメントは受け付けていません。

お探しのものを見つけられませんでしたか？

新規投稿