MIP heuristic solution does not result in calling the MIPSOL Callback
回答済み
Hey everyone,
I have the following problem while resolving a special variant of the TSP with drones (Formulated as MIP). Therefore I am using lazy constraints which are added in a MIPSOL Callback as usual.
The problem is, that if gurobi finds a MIP solution with help of heuristics, my MIPSOL Callback is not called. So if such a solution is found it will not be checked against violations of subtours and more. This can result in a wrong solution if the objective value of this heuristic solution is the best found value.
I found this (https://groups.google.com/forum/#!topic/gurobi/G36XEp-0yEA) discussion in the google group "Gurobi Optimization", which exactly describes the same problem, but without any solutions. I am logging the MIPSOL Callback calls so I am sure it will not be called. But why? This should be the case.
Maybe it is important to know that I am using gurobi in Java. Like the author of the google groups post the solving works fine if I disable the heuristics parameter ( environment.set( GRB.DoubleParam.Heuristics, 0.0 ) ).
I hope somebody can help me.
Thank you!
PS: Here you can find the logging of gurobi with heuristics and a part of the logging without heuristics: https://pastebin.com/g9wAdhBs
-
正式なコメント
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?. -
Hi,
I am sorry, I cannot see the additional logging. Can you please explain what I should see in the log?
A few comments:
- What does you MIPSOL calback look like?
- Please make sure to always add all violated lazy constraints. Due to threading and parallel computaiton is not enough to add a lazy constraint only once.
Best regards,
Sonja
0 -
I'm actually having a similar issue, but with branching solutions (with a * in the MIP logging).
I'm using the C++ API, and the first intruction after (where == GRB_CB_MIPSOL) is to print "Callback, objval = " + the value of the objective in this solution.The value of the objective is always rounded and casted to an int (all variables are integers in my problem).
My objective is of the form sum(x_i) where x_i are 0/1 variables. If the objective value is 1 in the callback, I also print the name of the objective variable which is set to 1, and add a lazy constraints addLazy(x_i == 0).
As you can see in the following log, heuristic solutions (H) go through the callback, but not the branching (*) one at the end, which terminate the solving process early (I need to remove all solution with (rounded) objective value 1, and there is still one at the end).
To be clear, the last line of the logging, which is
* 1093 950 14 1.0000000 1.00000 0.00% 223 209s
tells me that there is a solution with objective value 1, but does not go through the callback.
Edit : My mistake, the callback print is made before the logging print. So it seems to go through the callback, but for some reason the solving process still terminate early with a solution with objective value 1, which should not happen.
Any help is welcome,
Regards,
Baptiste Lambin
Optimize a model with 5024 rows, 14528 columns and 39872 nonzeros
Variable types: 0 continuous, 14528 integer (14528 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 2e+00]
Presolve removed 352 rows and 191 columns
Presolve time: 0.06s
Presolved: 4672 rows, 14337 columns, 38499 nonzeros
Variable types: 0 continuous, 14337 integer (14337 binary)Root relaxation: objective 2.083333e-01, 19225 iterations, 3.35 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time0 0 0.20833 0 310 - 0.20833 - - 5s
0 0 0.20833 0 634 - 0.20833 - - 5s
0 0 0.20833 0 563 - 0.20833 - - 5s
0 0 0.20833 0 354 - 0.20833 - - 7s
0 0 0.20833 0 371 - 0.20833 - - 7s
0 0 0.20833 0 438 - 0.20833 - - 10s
0 0 0.20833 0 505 - 0.20833 - - 10s
0 0 0.22599 0 339 - 0.22599 - - 13s
0 0 0.23729 0 477 - 0.23729 - - 13s
0 0 0.25424 0 628 - 0.25424 - - 14s
0 0 0.25424 0 647 - 0.25424 - - 14s
0 0 0.26342 0 696 - 0.26342 - - 14s
0 0 0.26507 0 690 - 0.26507 - - 15s
0 0 0.28784 0 789 - 0.28784 - - 15s
0 0 0.30145 0 778 - 0.30145 - - 15s
0 0 0.31207 0 807 - 0.31207 - - 16s
0 0 0.32568 0 719 - 0.32568 - - 16s
0 0 0.32696 0 840 - 0.32696 - - 17s
0 0 0.32705 0 848 - 0.32705 - - 17s
0 0 0.39837 0 788 - 0.39837 - - 18s
0 0 0.41041 0 793 - 0.41041 - - 18s
0 0 0.41626 0 854 - 0.41626 - - 19s
0 0 0.42033 0 752 - 0.42033 - - 19s
0 0 0.45896 0 779 - 0.45896 - - 20s
0 0 0.45896 0 860 - 0.45896 - - 20s
0 0 0.46558 0 815 - 0.46558 - - 21s
0 0 0.46558 0 828 - 0.46558 - - 21s
0 0 0.47208 0 717 - 0.47208 - - 22s
0 0 0.47208 0 765 - 0.47208 - - 22s
0 0 0.47208 0 757 - 0.47208 - - 23s
0 0 0.47676 0 704 - 0.47676 - - 23s
0 0 0.49671 0 354 - 0.49671 - - 27s
0 0 0.49671 0 503 - 0.49671 - - 27s
0 0 0.49906 0 663 - 0.49906 - - 28s
0 0 0.49906 0 590 - 0.49906 - - 28s
0 0 0.54249 0 828 - 0.54249 - - 29s
0 0 0.56667 0 800 - 0.56667 - - 30s
0 0 0.59669 0 885 - 0.59669 - - 31s
0 0 0.59835 0 848 - 0.59835 - - 31s
0 0 0.59835 0 798 - 0.59835 - - 32s
0 0 0.66545 0 765 - 0.66545 - - 32s
0 0 0.66545 0 750 - 0.66545 - - 33s
0 0 0.66545 0 797 - 0.66545 - - 33s
0 0 0.66545 0 778 - 0.66545 - - 33s
0 0 0.66545 0 334 - 0.66545 - - 36s
0 0 0.66545 0 575 - 0.66545 - - 37s
0 0 0.66545 0 422 - 0.66545 - - 41s
0 0 0.66545 0 422 - 0.66545 - - 42s
0 2 0.66545 0 421 - 0.66545 - - 45s
92 94 1.00000 23 400 - 0.66545 - 375 51s
259 260 1.00000 83 318 - 0.66545 - 276 55s
Callback, objval = 30
H 436 435 30.0000000 0.66545 97.8% 251 59s
Callback, objval = 19
H 442 440 19.0000000 0.66545 96.5% 254 59s
Callback, objval = 17
H 457 456 17.0000000 0.66545 96.1% 247 59s
Callback, objval = 2
H 467 468 2.0000000 0.66545 66.7% 250 59s
471 472 1.00000 127 186 2.00000 0.66545 66.7% 248 60s
668 667 1.00000 148 306 2.00000 0.66545 66.7% 237 65s
768 767 1.00000 176 307 2.00000 0.66545 66.7% 223 70s
838 838 1.00000 203 211 2.00000 0.66545 66.7% 212 76s
Callback, objval = 1
x_11_1_24
869 855 1.00000 212 291 2.00000 0.66545 66.7% 234 92s
Callback, objval = 1
x_11_1_31
938 875 0.66545 5 665 2.00000 0.66545 66.7% 244 95s
Callback, objval = 19
1042 967 1.00000 32 422 2.00000 0.66545 66.7% 234 105s
1044 968 1.00000 199 383 2.00000 0.66545 66.7% 234 111s
1047 970 1.00000 177 226 2.00000 0.66545 66.7% 233 117s
1049 972 1.00000 107 186 2.00000 0.66545 66.7% 233 120s
1051 973 1.00000 122 340 2.00000 0.66545 66.7% 232 125s
1053 974 1.00000 177 254 2.00000 0.66545 66.7% 232 132s
1055 976 1.00000 186 298 2.00000 0.66545 66.7% 231 138s
1057 977 1.00000 85 310 2.00000 0.66545 66.7% 231 147s
1059 978 1.00000 124 358 2.00000 0.66545 66.7% 230 151s
1061 980 1.00000 199 462 2.00000 0.66545 66.7% 230 156s
1063 981 1.00000 127 354 2.00000 0.66545 66.7% 230 161s
1065 982 1.00000 83 288 2.00000 0.66545 66.7% 229 165s
1067 984 1.00000 172 302 2.00000 0.66545 66.7% 229 171s
1069 985 1.00000 40 328 2.00000 0.66545 66.7% 228 177s
1071 986 1.00000 27 169 2.00000 0.72727 63.6% 228 181s
1075 989 1.00000 137 179 2.00000 0.72727 63.6% 227 188s
1077 990 1.00000 63 202 2.00000 0.73333 63.3% 227 190s
1081 993 1.00000 72 122 2.00000 0.80000 60.0% 226 196s
1085 996 1.00000 203 96 2.00000 0.80000 60.0% 225 201s
1089 998 1.00000 121 38 2.00000 1.00000 50.0% 224 205s
Callback, objval = 1
x_11_1_12
Callback, objval = 1
x_11_1_0
Callback, objval = 1
x_11_1_7
Callback, objval = 1
x_11_1_14
Callback, objval = 1
x_11_1_15
Callback, objval = 1
x_11_1_19
Callback, objval = 1
x_11_1_20
Callback, objval = 1
x_11_1_22
Callback, objval = 1
x_11_1_28
Callback, objval = 1
x_11_1_30
Callback, objval = 1
x_11_1_1
Callback, objval = 1
x_11_0_0
* 1093 950 14 1.0000000 1.00000 0.00% 223 209sCutting planes:
Gomory: 108
Cover: 137
Clique: 10
MIR: 245
Flow cover: 142
Zero half: 30
Lazy constraints: 11Explored 1093 nodes (1064323 simplex iterations) in 209.06 seconds
Thread count was 8 (of 8 available processors)Solution count 5: 1 2 17 ... 30
Optimal solution found (tolerance 1.00e-04)
Best objective 9.999999866071e-01, best bound 9.999999866071e-01, gap 0.0000%0 -
Hi Baptiste,
I wonder if adding some tolerances to your callback function would help. In particular, try checking if the objective value is greater than \( 0.99999 \) (1 - 1e-5). If so, identify the offending variables using the same tolerance and add the appropriate lazy constraints.
Gurobi uses a very small integer feasibility tolerance to determine if a variable is "close enough" to an integer to be considered integer-valued. My guess is that the solution found by Gurobi lies within this tolerance, but isn't properly detected by the checks in your callback function.
Just to be safe, I would remove the rounding. This can modify the solution information that Gurobi gives you, masking tolerance issues like this.
I hope this helps. Thanks!
Eli
0 -
Hi Eli,
It was actually a stupid mistake from my end. I used a vector<int> instead of vector<double> to get the current solution (using getSolution) and work on it. As getSolution returns a double (of course), it got truncated (instead of rounded), thus leading to some mistakes (as a value 0.999999 was casted to an int as 0).
For now, it seems that rounding still works to detect which variable is actually 1. But thanks for you answer anyway, I'll remind to always check the actual double value to see if there is any tolerance issue.
0
投稿コメントは受け付けていません。
コメント
5件のコメント