Skip to main content

User cuts are not counted in the MIP log

Ongoing
Jihye Jung
Gurobi-versary
First Comment
First Question

Hi, I'm working on a branch-and-cut algorithm in the python 3.8 environment and struggling with applying user cuts.

I set the callback function to print out the message when a user cut is added. This message has been shown several times during the branch-and-cut procedure.
The callback function also counts the number of added user cuts and prints the result after the optimization. This counter also shows that several cuts are added.

We know that the number of cuts is printed in the summary part of the MIP log like below.

(....)
CUT ADDED.............
CUT ADDED.............
* 1536 141 13 14.0000000 5.75000 58.9% 95.6 7s

Cutting planes:
User: 8

However, in some cases, I observed that no user cuts were counted in the MIP log while the callback function have printed the cut-adding message several times. (I've copied the example log below.)

Does it mean that the generated user cuts are ignored? Or, does it mean that the added user cuts did not contribute to the improvement of the lower bound?

Please help me with interpreting this result. Thank you very much in advance.

Changed value of parameter Presolve to 0
Prev: -1 Min: -1 Max: 2 Default: -1
Changed value of parameter PreCrush to 1
Prev: 0 Min: 0 Max: 1 Default: 0
Changed value of parameter Heuristics to 0.0
Prev: 0.05 Min: 0.0 Max: 1.0 Default: 0.05
Changed value of parameter Method to 2
Prev: -1 Min: -1 Max: 5 Default: -1
Changed value of parameter DegenMoves to 0
Prev: -1 Min: -1 Max: 2000000000 Default: -1
Changed value of parameter SubMIPNodes to 20
Prev: 500 Min: 0 Max: 2000000000 Default: 500
Changed value of parameter NodeMethod to 2
Prev: -1 Min: -1 Max: 2 Default: -1
Changed value of parameter Cuts to 0
Prev: -1 Min: -1 Max: 3 Default: -1
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (win64)
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 5518 rows, 2927 columns and 23643 nonzeros
Model fingerprint: 0xd9161232
Variable types: 2630 continuous, 297 integer (297 binary)
Coefficient statistics:
Matrix range [1e+00, 3e+01]
Objective range [1e+00, 3e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 2e+01]
Variable types: 2368 continuous, 559 integer (495 binary)
Root barrier log...

Ordering time: 0.07s

Barrier statistics:
AA' NZ : 1.666e+05
Factor NZ : 6.798e+05 (roughly 9 MBytes of memory)
Factor Ops : 1.372e+08 (less than 1 second per iteration)
Threads : 6

Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 3.27976543e+02 -5.12840687e+03 1.21e+02 0.00e+00 1.05e+01 0s
1 1.82060921e+02 -5.67004533e+03 3.24e+01 8.57e-01 3.14e+00 0s
2 1.42316528e+02 -3.92804282e+03 1.10e+01 9.99e-15 1.02e+00 0s
3 5.22579890e+01 -1.21350645e+03 1.68e+00 3.25e-14 1.88e-01 0s
4 4.87992078e+01 -7.29290361e+02 1.02e-01 3.12e-14 8.37e-02 0s
5 3.28988964e+01 -4.30653761e+02 4.56e-02 3.28e-14 4.92e-02 0s
6 2.25017857e+01 -2.58415619e+02 2.90e-02 2.62e-14 2.98e-02 0s
7 1.90031483e+01 -1.98231810e+02 1.97e-02 3.55e-14 2.30e-02 0s
8 1.51820317e+01 -1.07426452e+02 1.45e-02 2.92e-14 1.30e-02 0s
9 1.05292203e+01 -5.03448633e+01 1.26e-03 3.29e-14 6.36e-03 0s
10 6.71238804e+00 -1.81781909e+01 2.67e-04 2.84e-14 2.60e-03 0s
11 4.14405369e+00 -4.68545592e+00 4.50e-05 3.30e-14 9.22e-04 0s
12 2.66429745e+00 -2.82311244e-01 1.89e-05 2.49e-14 3.08e-04 0s
13 2.21155498e+00 1.17417286e+00 7.24e-06 3.91e-14 1.09e-04 0s
14 2.01443727e+00 1.56164532e+00 2.99e-06 3.55e-14 4.74e-05 0s
15 1.89338122e+00 1.69933886e+00 8.68e-07 3.55e-14 2.03e-05 0s
16 1.87254020e+00 1.78693998e+00 5.48e-07 2.84e-14 9.00e-06 0s
17 1.84320071e+00 1.81744873e+00 1.12e-07 4.26e-14 2.70e-06 0s
18 1.83581501e+00 1.82835290e+00 2.68e-08 4.26e-14 7.83e-07 0s
19 1.83371729e+00 1.83302290e+00 3.82e-09 7.11e-14 7.34e-08 0s
20 1.83333379e+00 1.83333302e+00 2.47e-12 1.14e-13 8.07e-11 0s
21 1.83333333e+00 1.83333333e+00 2.87e-11 8.53e-14 3.30e-14 0s

Barrier solved model in 21 iterations and 0.33 seconds
Optimal objective 1.83333333e+00


401 Dual superbasic variables remain

Root relaxation: objective 1.833333e+00, 868 iterations, 0.35 seconds

Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

0 0 2.12500 0 157 - 2.12500 - - 0s
0 0 2.12500 0 165 - 2.12500 - - 1s
0 2 2.12500 0 165 - 2.12500 - - 1s
25 32 3.26667 5 243 - 2.60694 - 1140 5s
91 95 3.89286 10 313 - 2.60694 - 851 10s
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
256 175 4.60897 11 322 - 2.60694 - 527 15s
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
409 279 4.26667 8 312 - 3.25000 - 493 20s
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
633 394 5.31250 11 360 - 3.25000 - 448 25s
822 498 5.50000 9 368 - 3.28571 - 421 30s
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
1065 601 4.37500 8 243 - 3.81994 - 398 35s
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
CUT ADDED.............
1256 676 3.81994 13 152 - 3.81994 - 389 42s
1258 680 3.81994 14 151 - 3.81994 - 391 47s
1262 684 3.81994 15 150 - 3.81994 - 397 50s
1280 696 3.81994 17 176 - 3.81994 - 414 55s
1317 724 4.00000 20 205 - 3.81994 - 446 60s
1367 744 4.28571 23 232 - 3.81994 - 469 65s
1429 749 infeasible 28 - 3.81994 - 483 70s
1496 767 4.11737 20 224 - 4.00000 - 496 76s
1563 779 5.25000 23 292 - 4.00000 - 511 80s
1604 776 infeasible 25 - 4.00000 - 520 86s
1696 787 5.00000 19 267 - 4.00000 - 530 90s
1833 782 5.00000 22 266 - 4.00000 - 538 96s
1895 787 5.00000 24 270 - 4.00000 - 547 100s
1964 789 infeasible 27 - 4.00000 - 555 105s
2058 808 5.12838 22 280 - 4.00000 - 558 110s
2156 799 4.14474 20 207 - 4.00000 - 561 116s
* 2222 750 26 18.0000000 4.00000 77.8% 565 119s
* 2248 707 21 14.0000000 4.00000 71.4% 562 119s
2281 707 5.00000 24 247 14.00000 4.11111 70.6% 563 122s
2427 679 4.13782 22 220 14.00000 4.11580 70.6% 561 126s
2559 680 5.01143 25 275 14.00000 4.13782 70.4% 555 132s
2849 586 8.03571 30 186 14.00000 4.37828 68.7% 529 137s
2980 563 5.09091 25 283 14.00000 4.59804 67.2% 520 140s
3096 568 5.09091 21 287 14.00000 5.00000 64.3% 516 148s
3410 559 5.00000 26 259 14.00000 5.00000 64.3% 509 156s
3729 548 infeasible 18 14.00000 5.00000 64.3% 501 162s
3867 548 7.50000 29 284 14.00000 5.00000 64.3% 499 171s
4162 543 6.06579 24 273 14.00000 5.00000 64.3% 491 179s
4416 545 5.00156 25 278 14.00000 5.00000 64.3% 485 186s
4603 536 cutoff 23 14.00000 5.00000 64.3% 485 191s
4831 516 cutoff 27 14.00000 5.00000 64.3% 482 196s
5035 472 cutoff 24 14.00000 5.08473 63.7% 477 200s
5352 340 10.21429 27 222 14.00000 5.13223 63.3% 471 209s
5629 257 6.00000 29 306 14.00000 5.34375 61.8% 461 214s
5938 103 6.00000 26 306 14.00000 6.00000 57.1% 450 223s
6618 0 infeasible 29 14.00000 6.00000 57.1% 430 228s

Explored 6881 nodes (2909545 simplex iterations) in 228.98 seconds
Thread count was 12 (of 12 available processors)

Solution count 2: 14 18

Optimal solution found (tolerance 1.00e-04)
Best objective 1.400000000000e+01, best bound 1.400000000000e+01, gap 0.0000%

User-callback calls 18451, time in user-callback 1.50 sec
Added 114 cuts.
0

Comments

3 comments

Date Votes
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Hi!

    The number of cuts shown in the final statistics is the number of actually applied cuts to improve the dual bound. Not every cut that you add in the cut callback will be added - there is still some filtering applied.

    I hope this answers your question.

    Cheers,
    Matthias

    0
  • Jihye Jung
    Gurobi-versary
    First Comment
    First Question

    Thank you for your answer, Matthias! 
    I'd like to ask you a few more questions, please.

    I understood that the user cuts generated in the callback function might be filtered out and not added to the model.

    When the "Cuts" parameter is set to 0, is there any way to check whether individual user cuts generated in the callback function are filtered or not?

    Also, I want to know the performance when I force all user cuts to be added without filtering.
    Will using cblazy instead of cbcut give me the experimental results I want?

    Thanks for your help again.

    Best regards,
    Jihye

    0
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Hi Jihye!

    You cannot modify the internal filtering mechanism. The best way to see how many of your cuts were added is to check the final statistics at the end.

    There is a fundamental difference between user cuts and lazy constraints. Please refer to this article for further information: What is the difference between user cuts and lazy constraints? – Gurobi Support Portal

    Cheers,
    Matthias

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post