How to have a solution with 0 gap
Answered
Hi,
Is there a way to force Gurobi to generate solution with 0 gap? I got optimal solution with positive gap for a MIP model that minimize cost. I found a solution with lower objective function value, and I plugged the solution in the model in Gurobi, and Gurobi actually achieved that "better" objective value. This means the solution is not optimal. Is there a way to make Gurobi to "work harder" to find the optimal solution with 0 gap? The tolerance is default 1.00e-04.
Thank you!
Sincerely,
Deanna
-
Hi Deanna - Have you tried setting the MIPGap to something smaller? G.
0 -
Hi, Gwyneth,
I tried the following code:
Gap=m.setParam('MIPGap', 0)
But the gap is still the same as before. Before I report the gap with this code:
Gap=max(0, abs(m.ObjVal-m.ObjBound)/abs(m.ObjVal))
Is there anything I do wrong or can improve?
Deanna
0 -
Hi Deanna - Can you share the start and end of the log as well as the MIPGap attribute? Thanks, G.
0 -
Hi, Gwyneth,
Below is the entire log:
Gurobi 9.1.1 (win64) logging started Sat Apr 3 17:09:29 2021
Changed value of parameter LogFile to P1_48_LFW_NoCap_Log 5 480 0.01 0.01 1 04032021-170929.txt
Prev: Default:
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 19906 rows, 14665 columns and 84414 nonzeros
Model fingerprint: 0x0d94c138
Variable types: 7190 continuous, 7475 integer (7475 binary)
Coefficient statistics:
Matrix range [1e+00, 3e+02]
Objective range [8e+01, 2e+04]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 5e+02]
Found heuristic solution: objective 1131674.0000
Presolve removed 2737 rows and 54 columns
Presolve time: 0.26s
Presolved: 17169 rows, 14611 columns, 101700 nonzeros
Variable types: 7181 continuous, 7430 integer (7425 binary)Deterministic concurrent LP optimizer: primal and dual simplex
Showing first log only...Concurrent spin time: 0.05s
Solved with dual simplex
Root relaxation: objective 8.667023e+05, 4190 iterations, 0.49 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time0 0 866702.308 0 141 1131674.00 866702.308 23.4% - 0s
H 0 0 1112932.0000 866702.308 22.1% - 1s
H 0 0 1112002.0000 866702.308 22.1% - 1s
H 0 0 1108081.0000 866702.308 21.8% - 1s
H 0 0 1102100.0000 866702.308 21.4% - 2s
H 0 0 997009.00000 866715.912 13.1% - 2s
...1161 590 937829.000 27 326 937829.000 937372.819 0.05% 219 140s
1185 608 937497.532 18 189 937829.000 937497.532 0.04% 222 145s...
Explored 1185 nodes (313558 simplex iterations) in 145.09 seconds
Thread count was 8 (of 8 available processors)Solution count 10: 937829 937855 937894 ... 940344
Optimal solution found (tolerance 1.00e-04)
Best objective 9.378290000000e+05, best bound 9.377479372686e+05, gap 0.0086%User-callback calls 23605, time in user-callback 0.27 sec
About the MIPGap attribute, the only part that I use MIPGap is the code:
Gap=m.setParam('MIPGap', 0)
So I guess I need to add more attributes?
Thank you
Deanna
0 -
Or do you mean this:
Gap=max(0, abs(m.ObjVal-m.ObjBound)/abs(m.ObjVal))
The one above and the one I sent in the previous email:Gap=m.setParam('MIPGap', 0), are the only two lines about gap I have in my script.
0 -
Hi Deanna -
Thanks for sharing the log; however, the full log is too long, so I edited it.
At the start you can see that the LogFile parameter is changed, but I don't see any indication that the MIPGap parameter is changed, so this is likely the reason for the behavior you are seeing. Can you let us know where in you code you are changing it?
Changed value of parameter LogFile to P1_48_LFW_NoCap_Log 5 480 0.01 0.01 1 04032021-170929.txt
Prev: Default:As for the attribute, I would like you to print out the MIPGap attribute. This is different than the parameter you are setting.
Gwyneth
0 -
Hi, Gwyneth,
The only code I have about the log is the code to change the name of log when I export the log to a txt file. I rerun the model without exporting the log file (so in this way there is no code related to log in my model), and you can see "Changed value of parameter LogFile...' is gone but the gap is still there.
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 19906 rows, 14665 columns and 84414 nonzeros
Model fingerprint: 0x0d94c138
Variable types: 7190 continuous, 7475 integer (7475 binary)
Coefficient statistics:
Matrix range [1e+00, 3e+02]
Objective range [8e+01, 2e+04]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 5e+02]
Found heuristic solution: objective 1131674.0000
Presolve removed 2737 rows and 54 columns
Presolve time: 0.24s
Presolved: 17169 rows, 14611 columns, 101700 nonzeros
Variable types: 7181 continuous, 7430 integer (7425 binary)Deterministic concurrent LP optimizer: primal and dual simplex
Showing first log only...Concurrent spin time: 0.03s
Solved with dual simplex
Root relaxation: objective 8.667023e+05, 4190 iterations, 0.39 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time0 0 866702.308 0 141 1131674.00 866702.308 23.4% - 0s
H 0 0 1112932.0000 866702.308 22.1% - 0s
H 0 0 1112002.0000 866702.308 22.1% - 1s
H 0 0 1108081.0000 866702.308 21.8% - 1s
H 0 0 1102100.0000 866702.308 21.4% - 1s
H 0 0 997009.00000 866715.912 13.1% - 2s
0 0 887018.508 0 221 997009.000 887018.508 11.0% - 2s
H 0 0 984838.00000 887018.508 9.93% - 3s
H 0 0 979948.00000 887018.508 9.48% - 3s
0 0 887162.142 0 234 979948.000 887162.142 9.47% - 3s
0 0 900502.971 0 236 979948.000 900502.971 8.11% - 3s
H 0 0 976505.00000 900502.971 7.78% - 4s
0 0 902823.792 0 244 976505.000 902823.792 7.55% - 4s
0 0 904322.994 0 266 976505.000 904322.994 7.39% - 4s
0 0 904324.514 0 277 976505.000 904324.514 7.39% - 4s
H 0 0 968640.00000 904324.514 6.64% - 6s
0 0 913623.243 0 308 968640.000 913623.243 5.68% - 6s
H 0 0 954598.00000 913623.243 4.29% - 6s...........
H 1131 568 937829.00000 937085.113 0.08% 197 78s
1134 570 937123.172 9 371 937829.000 937123.172 0.08% 196 80s
1155 585 937328.038 13 287 937829.000 937328.038 0.05% 208 85sCutting planes:
Learned: 6
Gomory: 9
Cover: 21
Projected implied bound: 1
Clique: 7
MIR: 39
Flow cover: 199
Zero half: 8
Network: 57
RLT: 6
Relax-and-lift: 6Explored 1185 nodes (313558 simplex iterations) in 90.01 seconds
Thread count was 8 (of 8 available processors)Solution count 10: 937829 937855 937894 ... 940344
Optimal solution found (tolerance 1.00e-04)
Best objective 9.378290000000e+05, best bound 9.377479372686e+05, gap 0.0086%On a related node, the gap is 0 when I run the same model with a smaller problem ( i.e., fewer nodes and arcs).
I am not sure how to print out MIPGap attribute. I use print(GRB.Attr.MIPGap), but it just returns MIPGap. I use Python. Could you let me know how to do that?
Thank you!
Deanna
0 -
Hi Deanna -
Again, it is not clear that the MIPGap parameter has been changed. Can you please share how you change the parameter and where?
Can you please print the MIPGap parameter immediately before calling optimize so we can check it? Yo umay need to call .update() first.
As for the MIPGap attribute, did you have a look at the documentation in the link? You'll see it is a *model* attribute, so you need to access it via the model.
Gwyneth
0 -
Hi, Gwyneth,
I don't think I changed any MIPGap parameter, at least I don't recall. As I said, the only places I did something about the Gap are the two line of code I have sent:
Gap=m.setParam('MIPGap', 0)
Gap=max(0, abs(m.ObjVal-m.ObjBound)/abs(m.ObjVal))
I checked the link and the link "Attribute Examples" on the linked page, but I did not see any attribute about MIPGap.
Can I send my code to you? As I am confused about what you asked.
Thank you!
Deanna
0 -
Hi Deanna,
This really is strange. Although it appears you are setting the MIPGap parameter with m.setParam('MIPGap', 0), the log file suggests that this update is not coming through. Gwyneth, was asking you to print the value of this attribute, e.g. `print(m.Params.MIPGap)`, to ensure that the parameter was updating correctly. The only way I can understand the behavior you are observing is if you are possibly updating the parameter after the m.optimize() step, if you have the parameter change syntax wrong (however it looks fine to me), or if you are updating the parameter of a different model object.
Happy to have a look at your code, if you are happy to share it.
Thanks,
Steve
0 -
Apologies, the typesetting was confused. That line should be,
print(m.Params.MIPGap)
0 -
Hi, Steve,
The problem is solved. You are right that I actually put MIPGap attribute setting after optimize... I should've thought of that as I use MIPFocus and put it in the right place. Anyway, thank you!
Deanna
0
Please sign in to leave a comment.
Comments
12 comments