Setting lower cutoff drastically degrades quality of solutions, solution speed

[lpsinger]

According to the CPLEX documentation for the lower cutoff parameter:

Sets the lower cutoff tolerance in a MIP. When the problem is a maximization problem, CPLEX cuts off or discards solutions that are less than the specified cutoff value. If the model has no solution with an objective value greater than or equal to the cutoff value, then CPLEX declares the model infeasible. In other words, setting the lower cutoff value c for a maximization problem is similar to adding this constraint to the objective function of the model: obj >= c.

However, this parameter is not behaving as expected in many cases. In problems like the attached example, if I set the lower cutoff to 0.1, it does not find any feasible solutions. However, if I leave the parameter unset, it rapidly finds feasible solutions with objective values >> 0.1.

I have set the time limit to 10 seconds in the example below, but I get the same outcome with this sav file if I set it to 4 hours.

example.sav.gz

With lowercutoff set

>>> from docplex.mp.model_reader import ModelReader
>>> model = ModelReader.read("example.sav.gz")
>>> model.context.cplex_parameters.emphasis.mip = model.cplex.parameters.emphasis.mip.values.feasibility
>>> model.context.cplex_parameters.mip.pool.capacity = 0
>>> model.context.cplex_parameters.mip.tolerances.lowercutoff = 0.1
>>> model.context.cplex_parameters.parallel = model.cplex.parameters.parallel.values.opportunistic
>>> model.context.cplex_parameters.threads = 12
>>> model.context.cplex_parameters.timelimit = 10
>>> model.context.solver.log_output = True
>>> model.solve()
Checking license ...
License found. [0.01 s]
Version identifier: 22.1.1.0 | 2023-06-15 | d64d5bd77
CPXPARAM_Read_DataCheck                          1
CPXPARAM_Threads                                 12
CPXPARAM_Parallel                                -1
CPXPARAM_Emphasis_MIP                            1
CPXPARAM_MIP_Pool_Capacity                       0
CPXPARAM_TimeLimit                               10
CPXPARAM_MIP_Tolerances_LowerCutoff              0.10000000000000001
Tried aggregator 2 times.
MIP Presolve eliminated 18600 rows and 5688 columns.
MIP Presolve added 25956 rows and 6489 columns.
MIP Presolve modified 50 coefficients.
Aggregator did 5165 substitutions.
Reduced MIP has 31684 rows, 33747 columns, and 131413 nonzeros.
Reduced MIP has 6794 binaries, 0 generals, 4900 SOSs, and 343 indicators.
Presolve time = 0.06 sec. (208.45 ticks)
Probing fixed 0 vars, tightened 490 bounds.
Probing time = 0.01 sec. (5.94 ticks)
Cover probing fixed 0 vars, tightened 273 bounds.
Tried aggregator 1 time.
Detecting symmetries...
MIP Presolve modified 50 coefficients.
Reduced MIP has 31684 rows, 33747 columns, and 131413 nonzeros.
Reduced MIP has 6794 binaries, 0 generals, 4900 SOSs, and 343 indicators.
Presolve time = 0.04 sec. (74.74 ticks)
Probing fixed 0 vars, tightened 542 bounds.
Probing time = 0.03 sec. (19.36 ticks)
Cover probing fixed 0 vars, tightened 156 bounds.
Clique table members: 9599.
Problem contains 2 user cuts.
MIP emphasis: integer feasibility.
MIP search method: dynamic search.
Parallel mode: opportunistic, using up to 12 threads.
Root relaxation solution time = 0.16 sec. (503.94 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.9463   512                      0.9463     3935         
      0     0        0.9447   322                  Cuts: 5071     5313         
      0     0        0.9483   670                   Cuts: 629    26976         
      0     0        0.9481   474                  Cuts: 3376    27921         
Detecting symmetries...
      0    -1       -0.0000     0                Impl Bds: 11       -1         
      0     2        0.9481  1062                      0.9447    27921         
Elapsed time = 10.02 sec. (14948.97 ticks, tree = 0.02 MB)
      1     7        0.9481   652                      0.9447    90843         
      2    11        0.9481   631                      0.9447    91038         
      4     3        0.9481   714                      0.9447    89779         
      5     4        0.9481   711                      0.9447    89782         
      7     6        0.9481   666                      0.9447    89862         
      9     8        0.9481   662                      0.9447    89866         

Clique cuts applied:  901
Cover cuts applied:  973
Implied bound cuts applied:  2469
Flow cuts applied:  922
Mixed integer rounding cuts applied:  553
Gomory fractional cuts applied:  37
User cuts applied:  1

Root node processing (before b&c):
  Real time             =    4.52 sec. (14562.94 ticks)
Parallel b&c, 12 threads:
  Real time             =    5.52 sec. (14741.86 ticks)
  Sync time (average)   =    4.33 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =   10.04 sec. (29304.80 ticks)
* solve: time limit exceeded, no integer solution

Without lowercutoff set

>>> from docplex.mp.model_reader import ModelReader
>>> model = ModelReader.read("example.sav.gz")
>>> model.context.cplex_parameters.emphasis.mip = model.cplex.parameters.emphasis.mip.values.feasibility
>>> model.context.cplex_parameters.mip.pool.capacity = 0
>>> # model.context.cplex_parameters.mip.tolerances.lowercutoff = 0.1
>>> model.context.cplex_parameters.parallel = model.cplex.parameters.parallel.values.opportunistic
>>> model.context.cplex_parameters.threads = 12
>>> model.context.cplex_parameters.timelimit = 10
>>> model.context.solver.log_output = True
>>> model.solve()
Checking license ...
License found. [0.02 s]
Version identifier: 22.1.1.0 | 2023-06-15 | d64d5bd77
CPXPARAM_Read_DataCheck                          1
CPXPARAM_Threads                                 12
CPXPARAM_Parallel                                -1
CPXPARAM_Emphasis_MIP                            1
CPXPARAM_MIP_Pool_Capacity                       0
CPXPARAM_TimeLimit                               10
Tried aggregator 2 times.
MIP Presolve eliminated 18600 rows and 5688 columns.
MIP Presolve added 25956 rows and 6489 columns.
MIP Presolve modified 50 coefficients.
Aggregator did 5165 substitutions.
Reduced MIP has 31684 rows, 33747 columns, and 131413 nonzeros.
Reduced MIP has 6794 binaries, 0 generals, 4900 SOSs, and 343 indicators.
Presolve time = 0.07 sec. (208.45 ticks)
Probing fixed 0 vars, tightened 490 bounds.
Probing time = 0.01 sec. (5.94 ticks)
Cover probing fixed 0 vars, tightened 273 bounds.
Tried aggregator 1 time.
Detecting symmetries...
MIP Presolve modified 50 coefficients.
Reduced MIP has 31684 rows, 33747 columns, and 131413 nonzeros.
Reduced MIP has 6794 binaries, 0 generals, 4900 SOSs, and 343 indicators.
Presolve time = 0.04 sec. (74.74 ticks)
Probing fixed 0 vars, tightened 542 bounds.
Probing time = 0.04 sec. (19.36 ticks)
Cover probing fixed 0 vars, tightened 156 bounds.
Clique table members: 9599.
Problem contains 2 user cuts.
MIP emphasis: integer feasibility.
MIP search method: dynamic search.
Parallel mode: opportunistic, using up to 12 threads.
Root relaxation solution time = 0.16 sec. (503.94 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.9463   512                      0.9463     3935         
      0     0        0.9447   322                  Cuts: 5071     5313         
      0     0        0.9439   319                   Cuts: 629     8831         
*     0+    0                            0.0000        0.9439              --- 
      0     0        0.9442   425        0.0000     Cuts: 350    10453     --- 
*     0+    0                            0.5035        0.9439            87.48%
      0     0        cutoff              0.5035        0.9439    10453   87.48%
Detecting symmetries...
      0     2        0.9442   425        0.5035        0.9439    10453   87.48%
Elapsed time = 4.03 sec. (11909.49 ticks, tree = 0.02 MB)
     21    29        0.9448   375        0.5158        0.9439    12311   82.99%
     37    34        0.9452   290        0.5158        0.9439    12700   82.99%
     73    33        0.9448   378        0.5158        0.9439    12696   82.99%
    119    62        0.9448   384        0.5158        0.9439    17163   82.99%
    146    20        0.9450   340        0.5158        0.9439    11586   82.99%
    169    45        0.9447   299        0.5158        0.9439    14217   82.99%
    197    97        0.9458   224        0.5158        0.9439    17922   82.99%
    230    83        0.9454   300        0.5158        0.9439    18482   82.99%
    278   113        0.9446   270        0.5158        0.9439    21275   82.99%
    365   219        0.9452   215        0.5158        0.9439    32061   82.99%
Elapsed time = 5.68 sec. (15063.89 ticks, tree = 5.67 MB)
    437   350        0.9461   181        0.5158        0.9439    46097   82.99%
    524   375        0.9454   162        0.5158        0.9439    48120   82.99%
    578   473        0.9442   138        0.5158        0.9439    50780   82.99%
    624   511        0.9457   120        0.5158        0.9439    52140   82.99%
    636   547        0.9453   111        0.5158        0.9439    56672   82.99%
    639   641        0.9479   628        0.5158        0.9439   119111   82.99%
    651   574        0.9451   278        0.5158        0.9439    83666   82.99%
    681   566        0.9453   175        0.5158        0.9439    74405   82.99%
Starting limited solution polishing.
    721   646        0.9454   227        0.5158        0.9439   125265   82.99%
    748   656        0.9453   199        0.5158        0.9439   126910   82.99%
Elapsed time = 10.03 sec. (24915.36 ticks, tree = 65.50 MB)
    760   681        0.9438    77        0.5158        0.9439   167681   82.99%
    769   707        0.9460   168        0.5158        0.9439   215805   82.99%
    802   708        0.9454   195        0.5158        0.9439   211468   82.99%
    852   789        0.9443   177        0.5158        0.9439   224891   82.99%
    885   783        0.9458   149        0.5158        0.9439   221992   82.99%

Clique cuts applied:  493
Cover cuts applied:  570
Implied bound cuts applied:  1193
Flow cuts applied:  479
Mixed integer rounding cuts applied:  364
Gomory fractional cuts applied:  50

Root node processing (before b&c):
  Real time             =    3.56 sec. (11796.89 ticks)
Parallel b&c, 12 threads:
  Real time             =    6.48 sec. (19432.17 ticks)
  Sync time (average)   =    0.25 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =   10.04 sec. (31229.06 ticks)
* solve: time limit exceeded
docplex.mp.solution.SolveSolution(obj=0.515848,values={x865:0.95,x866:0...

[lpsinger]

Here is a workaround using callbacks:

>>> from docplex.mp.model_reader import ModelReader
>>> from docplex.mp.callbacks.cb_mixin import ModelCallbackMixin
>>> from cplex.callbacks import MIPInfoCallback
>>> class LowerCutoffCallback(ModelCallbackMixin, MIPInfoCallback):
...     def __init__(self, env):
...         MIPInfoCallback.__init__(self, env)
...         ModelCallbackMixin.__init__(self)
...     def __call__(self):
...         if self.get_best_objective_value() <= 0.1:
...             self.abort()
... 
>>> model = ModelReader.read("example.sav.gz")
>>> model.context.cplex_parameters.emphasis.mip = model.cplex.parameters.emphasis.mip.values.feasibility
>>> model.context.cplex_parameters.mip.pool.capacity = 0
>>> # model.context.cplex_parameters.mip.tolerances.lowercutoff = 0.1
>>> model.register_callback(LowerCutoffCallback)
<__main__.LowerCutoffCallback object at 0x102453250>
>>> model.context.cplex_parameters.parallel = model.cplex.parameters.parallel.values.opportunistic
>>> model.context.cplex_parameters.threads = 12
>>> model.context.cplex_parameters.timelimit = 10
>>> model.context.solver.log_output = True
>>> model.solve()
Checking license ...
License found. [0.03 s]
Version identifier: 22.1.1.0 | 2023-06-15 | d64d5bd77
CPXPARAM_Read_DataCheck                          1
CPXPARAM_Threads                                 12
CPXPARAM_Parallel                                -1
CPXPARAM_Emphasis_MIP                            1
CPXPARAM_MIP_Pool_Capacity                       0
CPXPARAM_TimeLimit                               10
Legacy callback                                  i
Tried aggregator 2 times.
MIP Presolve eliminated 18600 rows and 5688 columns.
MIP Presolve added 25956 rows and 6489 columns.
MIP Presolve modified 50 coefficients.
Aggregator did 5165 substitutions.
Reduced MIP has 31684 rows, 33747 columns, and 131413 nonzeros.
Reduced MIP has 6794 binaries, 0 generals, 4900 SOSs, and 343 indicators.
Presolve time = 0.06 sec. (208.45 ticks)
Probing fixed 0 vars, tightened 490 bounds.
Probing time = 0.01 sec. (5.94 ticks)
Cover probing fixed 0 vars, tightened 273 bounds.
Tried aggregator 1 time.
Detecting symmetries...
MIP Presolve modified 50 coefficients.
Reduced MIP has 31684 rows, 33747 columns, and 131413 nonzeros.
Reduced MIP has 6794 binaries, 0 generals, 4900 SOSs, and 343 indicators.
Presolve time = 0.04 sec. (74.74 ticks)
Probing fixed 0 vars, tightened 542 bounds.
Probing time = 0.04 sec. (19.36 ticks)
Cover probing fixed 0 vars, tightened 156 bounds.
Clique table members: 9599.
Problem contains 2 user cuts.
MIP emphasis: integer feasibility.
MIP search method: dynamic search.
Parallel mode: opportunistic, using up to 12 threads.
Root relaxation solution time = 0.16 sec. (503.94 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.9463   512                      0.9463     3935         
      0     0        0.9447   322                  Cuts: 5071     5313         
      0     0        0.9439   319                   Cuts: 629     8831         
*     0+    0                            0.0000        0.9439              --- 
      0     0        0.9442   425        0.0000     Cuts: 350    10453     --- 
*     0+    0                            0.5001        0.9439            88.73%
      0     0        cutoff              0.5001        0.9439    10453   88.73%
Detecting symmetries...
      0     2        0.9442   425        0.5001        0.9439    10453   88.73%
Elapsed time = 4.06 sec. (11909.26 ticks, tree = 0.02 MB)
*     7+    6                            0.5025        0.9439            87.85%
      7     8        0.9448   393        0.5025        0.9439    11054   87.85%
     20    30        0.9448   381        0.5145        0.9439    12144   83.45%
     40    35        0.9450   301        0.5145        0.9439    12488   83.45%
     57    26        0.9452   341        0.5145        0.9439    14251   83.45%
     72    19        0.9450   334        0.5145        0.9439    11701   83.45%
     81    38        0.9456   279        0.5145        0.9439    14736   83.45%
     90    47        0.9455   266        0.5145        0.9439    14781   83.45%
    103    35        0.7141   226        0.5145        0.9439    14022   83.45%
    108    43        0.9454   314        0.5145        0.9439    14729   83.45%
    161    80        0.9456   234        0.5145        0.9439    18820   83.45%
Elapsed time = 5.88 sec. (15311.31 ticks, tree = 1.49 MB)
    205   235        0.9444   449        0.5145        0.9439    38080   83.45%
    272   191        0.9459   192        0.5145        0.9439    26388   83.45%
    314   223        0.9463   153        0.5145        0.9439    29414   83.45%
    356   240        0.9463   164        0.5145        0.9439    38317   83.45%
    399   363        0.9449   218        0.5145        0.9439    52578   83.45%
    439   384        0.9450   178        0.5145        0.9439    54303   83.45%
Starting limited solution polishing.
    450   420        0.9449   216        0.5145        0.9439    68825   83.45%
    476   350        0.9466   570        0.5145        0.9439    64028   83.45%
    516   518        0.9478   498        0.5145        0.9439   126167   83.45%
    546   472        0.9450   206        0.5145        0.9439    77246   83.45%
Elapsed time = 10.02 sec. (25156.31 ticks, tree = 19.40 MB)
    579   445        0.9466   501        0.5145        0.9439    69124   83.45%
    605   551        0.9482   455        0.5145        0.9439   128242   83.45%
    626   578        0.9451   153        0.5145        0.9439   148544   83.45%
    644   498        0.9466   514        0.5145        0.9439    79035   83.45%
    655   509        0.9466   510        0.5145        0.9439   124785   83.45%
    666   520        0.9466   504        0.5145        0.9439   125026   83.45%
    676   539        0.9466   493        0.5145        0.9439   125824   83.45%
    686   554        0.9466   470        0.5145        0.9439   135258   83.45%
*   688+  554                            0.5217        0.9439            80.94%
    688   556        0.9466   483        0.5217        0.9439   135441   80.94%

Clique cuts applied:  493
Cover cuts applied:  570
Implied bound cuts applied:  1221
Flow cuts applied:  479
Mixed integer rounding cuts applied:  364
Gomory fractional cuts applied:  50

Root node processing (before b&c):
  Real time             =    3.55 sec. (11795.74 ticks)
Parallel b&c, 12 threads:
  Real time             =    6.49 sec. (22750.13 ticks)
  Sync time (average)   =    0.25 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =   10.03 sec. (34545.88 ticks)
* solve: time limit exceeded
docplex.mp.solution.SolveSolution(obj=0.521686,values={x940:0.95,x941:0...