Gurobi log file

Ying Sun

unread,

Jan 22, 2015, 6:51:05 AM1/22/15

to gur...@googlegroups.com

Hi all,

I'm new to Gurobi and got the following question on the output log file of the solver. I'm trying to solve an Boolean LP and the end of the log file looks as:

Nodes | Current Node | Objective Bounds | Work

Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

...............

* 227 33 11 22.0302870 0.00000 100% 43.7 2s

* 245 36 11 18.0360173 0.00000 100% 42.9 2s

1233 39 0.00000 8 2 18.03602 0.00000 100% 33.1 5s

H 1422 49 14.3976070 0.00000 100% 38.5 9s

1570 38 0.00000 23 2 14.39761 0.00000 100% 38.3 10s

3044 26 cutoff 23 14.39761 0.00000 100% 35.2 15s

3908 6 cutoff 25 14.39761 0.00000 100% 34.3 20s

Explored 3941 nodes (137473 simplex iterations) in 20.09 seconds

Thread count was 4 (of 4 available processors)

Optimal solution found (tolerance 1.00e-04)

Best objective 1.439760702550e+01, best bound 1.439760702550e+01, gap 0.0%

The best lower bound stays at zero all the time (the objective function is always non-negative), and in the end the Gap jumps from 100% to 0% all of a sudden. Does it imply that the algorithm in fact did an exhaustive search?

Thanks in advance.

Best Regards,

Ying Sun

David Nehme

unread,

Jan 22, 2015, 11:39:13 AM1/22/15

to gur...@googlegroups.com

Yin,
Gurobi searched a total of 3941 nodes. Since your problem had more than 12 binary variables it did not do an exhaustive search. You are minimizing, so the bound displayed at each line is the minimum value of all the open nodes in the search tree and until node 3908, it still had at least one node with a 0 value for the lp relaxation. You can set the parameter
At node 3908, there were 6 unexplored nodes. We know that the node with the worst bound was 0, and the other 5 had bounds lower than the optimal solution.
There are a several ways you can get more detailed information. DisplayInterval to its minimum value of 1 second, you will see more log lines. This example demonstrates a callback that queries the values of GRB_CB_OBJBND which you could use to get the bound at each individual node.

Ying Sun

unread,

Jan 23, 2015, 2:37:00 AM1/23/15

to gur...@googlegroups.com

Thank you very much for the reply. I see the reason why best bound stays at zero.

The question that borders me now is that the problem had only 11 binary variables and the number of nodes explored is more than 2^11. Attach below is the complete log file. Many thanks!

-------------------------------------------------------------------------------------------------------------

Optimize a model with 4939 rows, 5929 columns and 99935 nonzeros

Presolve removed 2937 rows and 4675 columns

Presolve time: 0.28s

Presolved: 2002 rows, 1254 columns, 56247 nonzeros

Variable types: 1243 continuous, 11 integer (11 binary)

Root relaxation: objective 0.000000e+00, 1310 iterations, 0.14 seconds

Nodes | Current Node | Objective Bounds | Work

Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

0 0 0.00000 0 2 - 0.00000 - - 0s

H 0 0 309.5779009 0.00000 100% - 0s

0 2 0.00000 0 2 309.57790 0.00000 100% - 1s

H 31 30 96.7034024 0.00000 100% 88.0 1s

* 48 36 11 96.4814746 0.00000 100% 69.6 1s

* 49 36 11 53.1114516 0.00000 100% 69.1 1s

60 31 cutoff 11 53.11145 0.00000 100% 61.0 2s

H 78 32 50.7315164 0.00000 100% 64.1 2s

* 133 33 11 42.1533500 0.00000 100% 50.9 2s

* 134 33 11 35.8689571 0.00000 100% 50.7 2s

* 198 36 11 26.8158428 0.00000 100% 44.9 2s

* 227 33 11 22.0302870 0.00000 100% 43.7 2s

* 245 36 11 18.0360173 0.00000 100% 42.9 2s

364 45 0.00000 10 1 18.03602 0.00000 100% 38.3 3s

881 29 cutoff 11 18.03602 0.00000 100% 32.8 4s

1233 39 0.00000 8 2 18.03602 0.00000 100% 33.1 5s

1235 40 0.00000 7 2 18.03602 0.00000 100% 33.1 6s

1238 44 0.00000 15 2 18.03602 0.00000 100% 35.1 7s

1241 46 0.00000 16 9 18.03602 0.00000 100% 37.5 8s

1267 64 0.00000 21 4 18.03602 0.00000 100% 39.0 9s

H 1422 49 14.3976070 0.00000 100% 38.5 9s

1648 38 cutoff 24 14.39761 0.00000 100% 37.7 10s

2074 36 0.00000 23 2 14.39761 0.00000 100% 35.8 11s

2482 33 0.00000 23 2 14.39761 0.00000 100% 35.4 12s

2905 23 cutoff 25 14.39761 0.00000 100% 35.1 13s

2978 32 4.43415 23 2 14.39761 0.00000 100% 35.3 14s

3044 26 cutoff 23 14.39761 0.00000 100% 35.2 15s

3101 27 0.00000 23 2 14.39761 0.00000 100% 35.3 16s

3162 33 0.00000 21 4 14.39761 0.00000 100% 35.2 17s

3435 30 cutoff 24 14.39761 0.00000 100% 34.7 18s

3672 23 0.00000 24 1 14.39761 0.00000 100% 34.6 19s

3908 6 cutoff 25 14.39761 0.00000 100% 34.3 20s

Explored 3941 nodes (137473 simplex iterations) in 20.10 seconds

Thread count was 4 (of 4 available processors)

Optimal solution found (tolerance 1.00e-04)

Best objective 1.439760702550e+01, best bound 1.439760702550e+01, gap 0.0%

在 2015年1月23日星期五 UTC+8上午12:39:13，David Nehme写道：

Renan Garcia

unread,

Jan 28, 2015, 9:29:40 AM1/28/15

to gur...@googlegroups.com

Note that it is possible for Gurobi to introduce/imply integer variables during MIP preprocessing. For example, if you have the expression:

x + y = z

where x,y are binary and z is continuous, it's easy to see that z can be considered an integer and branching on it might be beneficial.

Renan

--

---
You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Reply all

Reply to author

Forward