Hello,

the presolve of CPLEX does not update systematically the lower bound and the gap. So you have to check optimality before trusting them.

Dear all,

we are trying to solve a minimization problem using a Mixed Integer Linear Programming (MILP) model by using CPLEX 2211 on a Mac. 
The model has been tested on several instances without issues, until we encountered a case in which CPLEX stops with the status "Optimal" while reporting an optimality gap of 39%.

As shown in the logfile below, the problem arises because the best-bound (17.7633552) is far from the optimal solution value (29.5809).This does not appear to be a tolerance issue: in fact, we are using strict settings for `epgap` and `epagap` (both set to `1e-7`).

Version identifier: 22.1.1.0 | 2022-11-28 | 9160aff4dCPXPARAM_Threads                                 4CPXPARAM_TimeLimit                               3610CPXPARAM_WorkMem                                 16000CPXPARAM_MIP_Tolerances_AbsMIPGap                9.9999999999999995e-08CPXPARAM_MIP_Tolerances_MIPGap                   9.9999999999999995e-08CPXPARAM_MIP_Tolerances_Integrality              9.9999999999999995e-08CPXPARAM_MIP_Limits_TreeMemory                   16000Legacy callback                                  iTried aggregator 2 times.MIP Presolve eliminated 276 rows and 192 columns.MIP Presolve modified 1493 coefficients.Aggregator did 17 substitutions.Reduced MIP has 826 rows, 1109 columns, and 7907 nonzeros.Reduced MIP has 831 binaries, 0 generals, 0 SOSs, and 0 indicators.Presolve time = 0.01 sec. (12.53 ticks)Probing fixed 32 vars, tightened 18 bounds.Probing time = 0.02 sec. (35.39 ticks)Cover probing fixed 0 vars, tightened 13 bounds.Tried aggregator 2 times.Detecting symmetries...MIP Presolve eliminated 21 rows and 36 columns.MIP Presolve modified 83 coefficients.Aggregator did 2 substitutions.Reduced MIP has 803 rows, 1071 columns, and 7547 nonzeros.Reduced MIP has 799 binaries, 0 generals, 0 SOSs, and 0 indicators.Presolve time = 0.00 sec. (8.04 ticks)Probing time = 0.00 sec. (3.63 ticks)Clique table members: 4193.MIP emphasis: balance optimality and feasibility.MIP search method: dynamic search.Parallel mode: deterministic, using up to 4 threads.Root relaxation solution time = 0.02 sec. (28.03 ticks)        Nodes                                         Cuts/   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap      0     0       13.0505    59                     13.0505      638         *     0+    0                           30.0000       13.0505            56.50%      0     0       13.0505    55       30.0000      Cuts: 14     1152   56.50%*     0+    0                           29.6699       13.0505            56.01%      0     0       13.2974    74       29.6699      Cuts: 10     2802   49.97%      0     0       14.7354    80       29.6699      Cuts: 56     3858   49.97%      0     0       14.8005    86       29.6699      Cuts: 34     4090   49.97%      0     0       14.8251    88       29.6699      Cuts: 20     4227   49.97%Detecting symmetries...      0     0       14.8408    85       29.6699      Cuts: 19     4503   49.97%*     0+    0                           29.5809       14.8453            49.81%      0     0       15.6348    65       29.5809      Cuts: 26     5121   47.15%      0     0       17.7634    73       29.5809      Cuts: 27     5696   39.95%Detecting symmetries...Repeating presolve.Tried aggregator 2 times.MIP Presolve eliminated 369 rows and 571 columns.MIP Presolve modified 169 coefficients.Aggregator did 1 substitutions.Reduced MIP has 433 rows, 499 columns, and 3533 nonzeros.Reduced MIP has 373 binaries, 0 generals, 0 SOSs, and 0 indicators.Presolve time = 0.00 sec. (3.87 ticks)Represolve time = 0.00 sec. (8.45 ticks)Root node processing (before b&c):  Real time             =    0.54 sec. (1287.49 ticks)Parallel b&c, 4 threads:  Real time             =    0.00 sec. (0.00 ticks)  Sync time (average)   =    0.00 sec.  Wait time (average)   =    0.00 sec.                          ------------Total (root+branch&cut) =    0.54 sec. (1287.49 ticks)Obj: 29.5808544 FinalGap: 39.9498% BestObj: 17.7633552 Optimal Optimal

From the logfile, I guess that the presolve certified the optimality of the incumbent solution without updating the best bound. As a conseguence, CPLEX stops with status "Optimal" and a misleadingly large optimality gap.

Disabling presolve seems to solve the issue, but in other instances presolve can be very helpful.
For this reason, I would appreciate any suggestions or best practices on how to deal with this behavior while keeping presolve enabled, thanks.

Dear all,

we are trying to solve a minimization problem using a Mixed Integer Linear Programming (MILP) model by using CPLEX 2211 on a Mac. 
The model has been tested on several instances without issues, until we encountered a case in which CPLEX stops with the status "Optimal" while reporting an optimality gap of 39%.

As shown in the logfile below, the problem arises because the best-bound (17.7633552) is far from the optimal solution value (29.5809).This does not appear to be a tolerance issue: in fact, we are using strict settings for `epgap` and `epagap` (both set to `1e-7`).

Version identifier: 22.1.1.0 | 2022-11-28 | 9160aff4dCPXPARAM_Threads                                 4CPXPARAM_TimeLimit                               3610CPXPARAM_WorkMem                                 16000CPXPARAM_MIP_Tolerances_AbsMIPGap                9.9999999999999995e-08CPXPARAM_MIP_Tolerances_MIPGap                   9.9999999999999995e-08CPXPARAM_MIP_Tolerances_Integrality              9.9999999999999995e-08CPXPARAM_MIP_Limits_TreeMemory                   16000Legacy callback                                  iTried aggregator 2 times.MIP Presolve eliminated 276 rows and 192 columns.MIP Presolve modified 1493 coefficients.Aggregator did 17 substitutions.Reduced MIP has 826 rows, 1109 columns, and 7907 nonzeros.Reduced MIP has 831 binaries, 0 generals, 0 SOSs, and 0 indicators.Presolve time = 0.01 sec. (12.53 ticks)Probing fixed 32 vars, tightened 18 bounds.Probing time = 0.02 sec. (35.39 ticks)Cover probing fixed 0 vars, tightened 13 bounds.Tried aggregator 2 times.Detecting symmetries...MIP Presolve eliminated 21 rows and 36 columns.MIP Presolve modified 83 coefficients.Aggregator did 2 substitutions.Reduced MIP has 803 rows, 1071 columns, and 7547 nonzeros.Reduced MIP has 799 binaries, 0 generals, 0 SOSs, and 0 indicators.Presolve time = 0.00 sec. (8.04 ticks)Probing time = 0.00 sec. (3.63 ticks)Clique table members: 4193.MIP emphasis: balance optimality and feasibility.MIP search method: dynamic search.Parallel mode: deterministic, using up to 4 threads.Root relaxation solution time = 0.02 sec. (28.03 ticks)        Nodes                                         Cuts/   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap      0     0       13.0505    59                     13.0505      638         *     0+    0                           30.0000       13.0505            56.50%      0     0       13.0505    55       30.0000      Cuts: 14     1152   56.50%*     0+    0                           29.6699       13.0505            56.01%      0     0       13.2974    74       29.6699      Cuts: 10     2802   49.97%      0     0       14.7354    80       29.6699      Cuts: 56     3858   49.97%      0     0       14.8005    86       29.6699      Cuts: 34     4090   49.97%      0     0       14.8251    88       29.6699      Cuts: 20     4227   49.97%Detecting symmetries...      0     0       14.8408    85       29.6699      Cuts: 19     4503   49.97%*     0+    0                           29.5809       14.8453            49.81%      0     0       15.6348    65       29.5809      Cuts: 26     5121   47.15%      0     0       17.7634    73       29.5809      Cuts: 27     5696   39.95%Detecting symmetries...Repeating presolve.Tried aggregator 2 times.MIP Presolve eliminated 369 rows and 571 columns.MIP Presolve modified 169 coefficients.Aggregator did 1 substitutions.Reduced MIP has 433 rows, 499 columns, and 3533 nonzeros.Reduced MIP has 373 binaries, 0 generals, 0 SOSs, and 0 indicators.Presolve time = 0.00 sec. (3.87 ticks)Represolve time = 0.00 sec. (8.45 ticks)Root node processing (before b&c):  Real time             =    0.54 sec. (1287.49 ticks)Parallel b&c, 4 threads:  Real time             =    0.00 sec. (0.00 ticks)  Sync time (average)   =    0.00 sec.  Wait time (average)   =    0.00 sec.                          ------------Total (root+branch&cut) =    0.54 sec. (1287.49 ticks)Obj: 29.5808544 FinalGap: 39.9498% BestObj: 17.7633552 Optimal Optimal

From the logfile, I guess that the presolve certified the optimality of the incumbent solution without updating the best bound. As a conseguence, CPLEX stops with status "Optimal" and a misleadingly large optimality gap.

Disabling presolve seems to solve the issue, but in other instances presolve can be very helpful.
For this reason, I would appreciate any suggestions or best practices on how to deal with this behavior while keeping presolve enabled, thanks.

Hello, more clearly: the presolve of CPLEX does not update systematically the bound and the gap. So, if the presolve proves optimality (assuming minimization) the real bound may be greater than the one displayed.  (By real bound, I mean the max between the displayed bound and the best objective minus the optimality tolerances.)

Dear all,

we are trying to solve a minimization problem using a Mixed Integer Linear Programming (MILP) model by using CPLEX 2211 on a Mac. 
The model has been tested on several instances without issues, until we encountered a case in which CPLEX stops with the status "Optimal" while reporting an optimality gap of 39%.

As shown in the logfile below, the problem arises because the best-bound (17.7633552) is far from the optimal solution value (29.5809).This does not appear to be a tolerance issue: in fact, we are using strict settings for `epgap` and `epagap` (both set to `1e-7`).

Version identifier: 22.1.1.0 | 2022-11-28 | 9160aff4dCPXPARAM_Threads                                 4CPXPARAM_TimeLimit                               3610CPXPARAM_WorkMem                                 16000CPXPARAM_MIP_Tolerances_AbsMIPGap                9.9999999999999995e-08CPXPARAM_MIP_Tolerances_MIPGap                   9.9999999999999995e-08CPXPARAM_MIP_Tolerances_Integrality              9.9999999999999995e-08CPXPARAM_MIP_Limits_TreeMemory                   16000Legacy callback                                  iTried aggregator 2 times.MIP Presolve eliminated 276 rows and 192 columns.MIP Presolve modified 1493 coefficients.Aggregator did 17 substitutions.Reduced MIP has 826 rows, 1109 columns, and 7907 nonzeros.Reduced MIP has 831 binaries, 0 generals, 0 SOSs, and 0 indicators.Presolve time = 0.01 sec. (12.53 ticks)Probing fixed 32 vars, tightened 18 bounds.Probing time = 0.02 sec. (35.39 ticks)Cover probing fixed 0 vars, tightened 13 bounds.Tried aggregator 2 times.Detecting symmetries...MIP Presolve eliminated 21 rows and 36 columns.MIP Presolve modified 83 coefficients.Aggregator did 2 substitutions.Reduced MIP has 803 rows, 1071 columns, and 7547 nonzeros.Reduced MIP has 799 binaries, 0 generals, 0 SOSs, and 0 indicators.Presolve time = 0.00 sec. (8.04 ticks)Probing time = 0.00 sec. (3.63 ticks)Clique table members: 4193.MIP emphasis: balance optimality and feasibility.MIP search method: dynamic search.Parallel mode: deterministic, using up to 4 threads.Root relaxation solution time = 0.02 sec. (28.03 ticks)        Nodes                                         Cuts/   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap      0     0       13.0505    59                     13.0505      638         *     0+    0                           30.0000       13.0505            56.50%      0     0       13.0505    55       30.0000      Cuts: 14     1152   56.50%*     0+    0                           29.6699       13.0505            56.01%      0     0       13.2974    74       29.6699      Cuts: 10     2802   49.97%      0     0       14.7354    80       29.6699      Cuts: 56     3858   49.97%      0     0       14.8005    86       29.6699      Cuts: 34     4090   49.97%      0     0       14.8251    88       29.6699      Cuts: 20     4227   49.97%Detecting symmetries...      0     0       14.8408    85       29.6699      Cuts: 19     4503   49.97%*     0+    0                           29.5809       14.8453            49.81%      0     0       15.6348    65       29.5809      Cuts: 26     5121   47.15%      0     0       17.7634    73       29.5809      Cuts: 27     5696   39.95%Detecting symmetries...Repeating presolve.Tried aggregator 2 times.MIP Presolve eliminated 369 rows and 571 columns.MIP Presolve modified 169 coefficients.Aggregator did 1 substitutions.Reduced MIP has 433 rows, 499 columns, and 3533 nonzeros.Reduced MIP has 373 binaries, 0 generals, 0 SOSs, and 0 indicators.Presolve time = 0.00 sec. (3.87 ticks)Represolve time = 0.00 sec. (8.45 ticks)Root node processing (before b&c):  Real time             =    0.54 sec. (1287.49 ticks)Parallel b&c, 4 threads:  Real time             =    0.00 sec. (0.00 ticks)  Sync time (average)   =    0.00 sec.  Wait time (average)   =    0.00 sec.                          ------------Total (root+branch&cut) =    0.54 sec. (1287.49 ticks)Obj: 29.5808544 FinalGap: 39.9498% BestObj: 17.7633552 Optimal Optimal

From the logfile, I guess that the presolve certified the optimality of the incumbent solution without updating the best bound. As a conseguence, CPLEX stops with status "Optimal" and a misleadingly large optimality gap.

Disabling presolve seems to solve the issue, but in other instances presolve can be very helpful.
For this reason, I would appreciate any suggestions or best practices on how to deal with this behavior while keeping presolve enabled, thanks.