Skip to main content

Cutoff parameter is more time consuming

Answered

Comments

4 comments

  • Michel Soares
    Thought Leader

    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
    First Comment
    Gurobi-versary
    First Question

    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
    Thought Leader

    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
    First Comment
    Gurobi-versary
    First Question

    Thanks for your advise.

    I will try.

    0

Please sign in to leave a comment.