Cutoff parameter is more time consuming

Answered

Dongyun Kim

• September 12, 2023 08:43

Hello,

I am trying to solve a problem with Branch-and-Bound(Off parameters 'Heuristics', 'Presolve', 'Symmetry', 'Cuts') for the Binary Integer Programming model studying now

I'm currently interested in Cutoff and have two questions regarding it.

1. For my model(aim to minimize), I tested re-solving model(10 instances) by setting the cutoff value as the optimal value for the problem already solved with Branch-and-Bound(B&B). In this case, the time it took to solve the problem actually increased. Even if the solution was found at similar time as before, time to completion was slower.

I know if setting an upper bound, it should cut off values that are worse than that value from the branch-and-bound tree, reduce nodes that need to be explored. Could you advise me why this is happening?

Branch and Bound (computation time)

8.59 6.39 8.32 5.77 8.99 32.38 7.63 13.82 26.49 23.09

Adding Cutoff(Cutoff value = Optimal Value) parameter (computation time)

32.62, 11.11, 11.80, 5.47, 10.27, 28.06, 10.85, 30.75, 30.27, 17.92

 

2. Could you advise me when I get a lower bound on the LP relaxation objective value in a Branch-and-Bound tree using heuristics and if objective value of the LP relaxation is less than this, is there a way to cut off these nodes in the tree?

Related to

• Branch-and-Cut
• Callbacks

0

• 

  Michel Soares

  • September 12, 2023 19:30

  

  

  I am not sure if this is the cause, but it might be related to numeric problems. Have you tried slightly increasing the value for the cutoff?
  Additionally, can you post the logs for two runs (one with cutoff and another one without it)?

  1
• 

  Dongyun Kim

  • September 13, 2023 00:53

  

  

  

  Hello Michel,

  Plz see below log.

  (optimal objective value for instance 1 is 37.8)

  First, No Cutoff option

  instance: 1
  Set parameter Username
  Academic license - for non-commercial use only - expires 2024-09-02
  Set parameter Heuristics to value 0
  Set parameter PreCrush to value 1
  Set parameter Presolve to value 0
  Set parameter PreSparsify to value 0
  Set parameter Symmetry to value 0
  Set parameter Cuts to value 0
  Set parameter TimeLimit to value 3600

  Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (win64)

  CPU model: 13th Gen Intel(R) Core(TM) i7-13700F, instruction set [SSE2|AVX|AVX2]
  Thread count: 16 physical cores, 24 logical processors, using up to 24 threads

  Optimize a model with 3721 rows, 3007 columns and 31474 nonzeros
  Model fingerprint: 0xba4b421c
  Variable types: 0 continuous, 3007 integer (3007 binary)
  Coefficient statistics:
    Matrix range     [3e-01, 2e+00]
    Objective range  [2e+00, 2e+00]
    Bounds range     [1e+00, 1e+00]
    RHS range        [1e+00, 2e+00]
  Variable types: 0 continuous, 3007 integer (3007 binary)

  Root relaxation: objective 3.360000e+01, 1371 iterations, 0.03 seconds (0.07 work units)

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

       0     0   33.60000    0  149          -   33.60000      -     -    0s
       0     0   33.60000    0  284          -   33.60000      -     -    0s
       0     0   33.60000    0  137          -   33.60000      -     -    0s
       0     2   33.60000    0  137          -   33.60000      -     -    0s
  *  615   646              35      48.0000000   33.60000  30.0%  66.4    0s
  *  724   705              30      46.5000000   33.60000  27.7%  59.7    0s
  *  944   895              27      45.6000000   33.60000  26.3%  57.1    0s
  * 1786  1218              54      44.4000000   33.60000  24.3%  42.8    1s
  * 2722  1617              35      43.2000000   33.60000  22.2%  50.7    2s
  * 2730  1558              43      39.9000000   33.60000  15.8%  51.3    2s
  * 3354  1511              36      37.8000000   33.60000  11.1%  60.8    4s
    3794  1405     cutoff   31        37.80000   33.60000  11.1%  68.1    5s

  Explored 6366 nodes (532935 simplex iterations) in 8.40 seconds (20.73 work units)
  Thread count was 24 (of 24 available processors)

  Solution count 7: 37.8 39.9 43.2 ... 48

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

   

  Second, set cutoff 45.9(this value is from my heuristic algorithm)

  instance: 1
  Set parameter Username
  Academic license - for non-commercial use only - expires 2024-09-02
  Set parameter Heuristics to value 0
  Set parameter PreCrush to value 1
  Set parameter Presolve to value 0
  Set parameter PreSparsify to value 0
  Set parameter Symmetry to value 0
  Set parameter Cuts to value 0
  Set parameter TimeLimit to value 3600
  Set parameter Cutoff to value 45.9
  
  Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (win64)

  CPU model: 13th Gen Intel(R) Core(TM) i7-13700F, instruction set [SSE2|AVX|AVX2]
  Thread count: 16 physical cores, 24 logical processors, using up to 24 threads

  Optimize a model with 3721 rows, 3007 columns and 31474 nonzeros
  Model fingerprint: 0xba4b421c
  Variable types: 0 continuous, 3007 integer (3007 binary)
  Coefficient statistics:
    Matrix range     [3e-01, 2e+00]
    Objective range  [2e+00, 2e+00]
    Bounds range     [1e+00, 1e+00]
    RHS range        [1e+00, 2e+00]
  Variable types: 0 continuous, 3007 integer (3007 binary)

  Root relaxation: objective 3.360000e+01, 1371 iterations, 0.03 seconds (0.07 work units)

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

       0     0   33.60000    0  149          -   33.60000      -     -    0s
       0     0   33.60000    0  284          -   33.60000      -     -    0s
       0     0   33.60000    0  137          -   33.60000      -     -    0s
       0     2   33.60000    0  137          -   33.60000      -     -    0s
  *  606   578              37      45.9000000   33.60000  26.8%  69.2    0s
  *  952   867              26      45.6000000   33.60000  26.3%  55.9    0s
  * 2186  1477              25      44.1000000   33.60000  23.8%  39.4    1s
  * 2737  1570              28      43.8000000   33.60000  23.3%  50.7    3s
  * 2920  1543              41      42.0000000   33.60000  20.0%  52.1    3s
  * 3175  1509              36      37.8000000   33.60000  11.1%  55.4    3s
    4535  1333   35.96667   28  477   37.80000   34.39451  9.01%  61.5    5s
   10666  1389   37.12500   50  352   37.80000   36.01579  4.72%  67.5   10s

  Explored 15354 nodes (1042336 simplex iterations) in 13.82 seconds (34.26 work units)
  Thread count was 24 (of 24 available processors)

  Solution count 6: 37.8 42 43.8 ... 45.9

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

  third, set cufoff 37.8

  instance: 1
  Set parameter Username
  Academic license - for non-commercial use only - expires 2024-09-02
  Set parameter Heuristics to value 0
  Set parameter PreCrush to value 1
  Set parameter Presolve to value 0
  Set parameter PreSparsify to value 0
  Set parameter Symmetry to value 0
  Set parameter Cuts to value 0
  Set parameter TimeLimit to value 3600
  Set parameter Cutoff to value 37.8
  Tier:4, Stack:8, Weight limit:10
  H1:1.5, H2:1.8, C:2.1
  Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (win64)

  CPU model: 13th Gen Intel(R) Core(TM) i7-13700F, instruction set [SSE2|AVX|AVX2]
  Thread count: 16 physical cores, 24 logical processors, using up to 24 threads

  Optimize a model with 3721 rows, 3007 columns and 31474 nonzeros
  Model fingerprint: 0xba4b421c
  Variable types: 0 continuous, 3007 integer (3007 binary)
  Coefficient statistics:
    Matrix range     [3e-01, 2e+00]
    Objective range  [2e+00, 2e+00]
    Bounds range     [1e+00, 1e+00]
    RHS range        [1e+00, 2e+00]
  Variable types: 0 continuous, 3007 integer (3007 binary)

  Root relaxation: objective 3.360000e+01, 1371 iterations, 0.04 seconds (0.07 work units)

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

       0     0   33.60000    0  149          -   33.60000      -     -    0s
       0     0   33.60000    0  284          -   33.60000      -     -    0s
       0     0   33.60000    0  137          -   33.60000      -     -    0s
       0     2   33.60000    0  137          -   33.60000      -     -    0s
    3511  1706   37.46250   32  284          -   33.60000      -  92.3    5s
  * 5109  1665              35      37.8000000   33.60000  11.1%  87.2    6s
    9370  2456   35.96667   28  293   37.80000   34.80000  7.94%  82.5   10s
   17253  3365     cutoff   28        37.80000   35.70000  5.56%  75.2   15s
   24131  3935     cutoff   33        37.80000   36.08333  4.54%  79.1   20s
   30715  2448   37.25000   27  315   37.80000   36.90000  2.38%  80.1   25s
   34776   307   37.50000   33  265   37.80000   37.14000  1.75%  82.4   31s

  Explored 42304 nodes (3096123 simplex iterations) in 32.55 seconds (77.71 work units)
  Thread count was 24 (of 24 available processors)

  Solution count 1: 37.8 

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

  Fourth, set cut off 38(roundup 37.8)

  instance: 1
  Set parameter Username
  Academic license - for non-commercial use only - expires 2024-09-02
  Set parameter Heuristics to value 0
  Set parameter PreCrush to value 1
  Set parameter Presolve to value 0
  Set parameter PreSparsify to value 0
  Set parameter Symmetry to value 0
  Set parameter Cuts to value 0
  Set parameter TimeLimit to value 3600
  Set parameter Cutoff to value 38
  Tier:4, Stack:8, Weight limit:10
  H1:1.5, H2:1.8, C:2.1
  Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (win64)

  CPU model: 13th Gen Intel(R) Core(TM) i7-13700F, instruction set [SSE2|AVX|AVX2]
  Thread count: 16 physical cores, 24 logical processors, using up to 24 threads

  Optimize a model with 3721 rows, 3007 columns and 31474 nonzeros
  Model fingerprint: 0xba4b421c
  Variable types: 0 continuous, 3007 integer (3007 binary)
  Coefficient statistics:
    Matrix range     [3e-01, 2e+00]
    Objective range  [2e+00, 2e+00]
    Bounds range     [1e+00, 1e+00]
    RHS range        [1e+00, 2e+00]
  Variable types: 0 continuous, 3007 integer (3007 binary)

  Root relaxation: objective 3.360000e+01, 1371 iterations, 0.04 seconds (0.07 work units)

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

       0     0   33.60000    0  149          -   33.60000      -     -    0s
       0     0   33.60000    0  284          -   33.60000      -     -    0s
       0     0   33.60000    0  137          -   33.60000      -     -    0s
       0     2   33.60000    0  137          -   33.60000      -     -    0s
  * 3438  1647              43      37.8000000   33.60000  11.1%  92.0    4s
    3606  1660   36.35143   21  261   37.80000   33.60000  11.1%  93.8    5s
    9045  1985   36.01579   24  409   37.80000   34.87000  7.75%   102   10s
   15520  1964     cutoff   28        37.80000   36.36041  3.81%  97.7   15s

  Explored 20854 nodes (2096009 simplex iterations) in 19.42 seconds (49.17 work units)
  Thread count was 24 (of 24 available processors)

  Solution count 1: 37.8 

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

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

  Time consumption results for instance 1

  1. No cutoff: 8.40s

  2. set cutoff 45.9: 13.82s

  3. set cutoff 37.8: 32.55s

  4. set cutoff 38: 19.42s

  Below are the results of the experiment on 10 instances

  1. No cutoff:

  8.40     6.43     8.57     5.80     9.02     32.95     7.82     14.10     26.60     23.05

  2. set cutoff (from my heuristics): 

  13.82     6.82     20.07     8.65     14.33     27.71     9.52     14.97     56.28     42.44

  3. set cutoff (optimal object value):

  32.55     10.88     11.93     5.51     10.32     27.85     10.64     31.14     30.44     17.96

  4. set cutoff (roundup optimal ~):

  19.42     11.33     11.66     6.01     9.60     32.47     8.88     25.83     28.07     23.27

   

   

   

   

  0
• 

  Michel Soares

  • September 13, 2023 11:50

  

  

  A few things that I notice from the logs:
  1. You arrive at better/best solutions earlier using cutoffs.

  2. In tighter cutoff scenarios, the solver takes longer to prove optimality and ends up exploring more nodes.

  Although I cannot tell you the reason for this, I have a possible explanation:

  Poor branching decisions when cutoff is set. Default gurobi parameters for branching might not be ideal for this atypical situation (no cuts, heuristic and cutoff set). You might want to try fixing VarBranch and BranchDir parameters and see if the situation changes.

  Hopefully someone else on Gurobi's side can enlighten us on this question.

  0
• 

  Dongyun Kim

  • September 13, 2023 22:39

  

  

  

  Thanks for your advise.

  I will try.

  0

Please sign in to leave a comment.