Skip to main content

How to have a solution with 0 gap

Answered

Comments

12 comments

  • Gwyneth Butera
    Gurobi Staff Gurobi Staff

    Hi Deanna - Have you tried setting the MIPGap to something smaller? G.

    0
  • Deng Pan
    Gurobi-versary
    Conversationalist
    First Question

    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
  • Gwyneth Butera
    Gurobi Staff Gurobi Staff

    Hi Deanna - Can you share the start and end of the log as well as the MIPGap attribute? Thanks, G.

    0
  • Deng Pan
    Gurobi-versary
    Conversationalist
    First Question

    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 Time

    0 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
  • Deng Pan
    Gurobi-versary
    Conversationalist
    First Question

    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
  • Gwyneth Butera
    Gurobi Staff Gurobi Staff

    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
  • Deng Pan
    Gurobi-versary
    Conversationalist
    First Question

    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 Time

    0 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 85s

    Cutting 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: 6

    Explored 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
  • Gwyneth Butera
    Gurobi Staff Gurobi Staff

    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
  • Deng Pan
    Gurobi-versary
    Conversationalist
    First Question

    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
  • Steven Edwards
    Gurobi Staff Gurobi Staff

    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
  • Steven Edwards
    Gurobi Staff Gurobi Staff

    Apologies, the typesetting was confused. That line should be,

    print(m.Params.MIPGap)
    0
  • Deng Pan
    Gurobi-versary
    Conversationalist
    First Question

    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.