Decision Optimization

 View Only

  • 1.  Cplex stops too early

    Posted Fri October 22, 2021 03:40 PM
    Hello,

    I am using Cplex 20.1 with the Python API to solve a MILP model. I do not use any callback.
    I set a time limit of 120 seconds and a mip relative gap tolerance of 10^-6, but Cplex stops after around 7 seconds with a gap of 0.51%.
    I don't understand this behavior, is there any other parameter that I should have set ? I tried to set parameters.mip.tolerances.absmipgap to a small value but it didn't change anything.

    For information, here is the beginning and the end of Cplex output :

    Version identifier: 20.1.0.0 | 2020-11-10 | 9bedb6d68
CPXPARAM_Read_DataCheck                          1
CPXPARAM_TimeLimit                               120
CPXPARAM_MIP_Tolerances_MIPGap                   9.9999999999999995e-07
Found incumbent of value 1382748.806125 after 0.00 sec. (0.94 ticks)
Warning:  Non-integral bounds for integer variables rounded.
Tried aggregator 2 times.
MIP Presolve eliminated 483 rows and 1654 columns.
Aggregator did 2 substitutions.
Reduced MIP has 1896 rows, 6072 columns, and 17342 nonzeros.
Reduced MIP has 5022 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (12.66 ticks)
Probing time = 0.02 sec. (4.30 ticks)
Tried aggregator 1 time.
Detecting symmetries...
Reduced MIP has 1896 rows, 6072 columns, and 17342 nonzeros.
Reduced MIP has 5022 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (10.92 ticks)
Probing time = 0.01 sec. (4.05 ticks)
Clique table members: 12573.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 32 threads.
Root relaxation solution time = 0.07 sec. (52.43 ticks)

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

*     0+    0                      1382748.8061  -198658.0750           114.37%
      0     0   -98216.4853   143  1382748.8061   -98216.4853     1685  107.10%
*     0+    0                       336452.8987   -98216.4853           129.19%
      0     0   -97990.9348    46   336452.8987     Cuts: 105     2179  129.12%
*     0+    0                        54989.4472   -97990.9348           278.20%
      0     0   -97990.1125    25    54989.4472      Cuts: 10     2227  278.20%
*     0+    0                       -26936.2499   -97990.1125           263.79%
      0     0   -97990.1125    23   -26936.2499       Cuts: 4     2229  263.79%
*     0+    0                       -87337.6679   -97990.1125            12.20%
Detecting symmetries...
      0     2   -97990.1125     7   -87337.6679   -97990.1125     2229   12.20%
Elapsed time = 1.08 sec. (373.90 ticks, tree = 0.02 MB, solutions = 4)

[...]

  8381     0   -97887.0775    27   -94224.5693       Cuts: 5   409595    3.89%
   8381     0   -97882.7386    33   -94224.5693      Cuts: 10   409652    3.88%
   8381     0   -97878.0557    60   -94224.5693   Impl Bds: 2   409717    3.88%
*  8381+    0                       -97368.6409   -97878.0557             0.52%
   8381     0  -1.00000e+75     0   -97368.6409   -97878.0557   409717    0.52%
   8381     0   -97872.7900    31   -97368.6409      Cuts: 10   409763    0.52%

Repeating presolve.
Presolve time = 0.01 sec. (4.82 ticks)
Represolve time = 0.01 sec. (6.02 ticks)

Root node processing (before b&c):
  Real time             =    0.98 sec. (372.35 ticks)
Parallel b&c, 32 threads:
  Real time             =    6.07 sec. (2391.13 ticks)
  Sync time (average)   =    1.20 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    7.05 sec. (2763.48 ticks)
​

    Thanks a lot for your help!



    ------------------------------
    Ccl _
    ------------------------------

    #DecisionOptimization


  • 2.  RE: Cplex stops too early

    IBM Champion
    Posted Fri October 22, 2021 04:37 PM
    Do not rely on the node log to get the final gap. Unless you have set the log frequency to 1 (print a line at every node), CPLEX may tighten the bound between the node at which the last log line occurred and the node at which it stopped. Also, in your case, it did a repeat presolve at the end and apparently did not do any more (or at least not many more) nodes, so the repeat presolve could have closed the gap. I suggest you call the Python equivalent of IloCplex.getMIPRelativeGap() (Java name) after the run to see what the gap is (and maybe the equivalent of IloCplex.getBestObjValue() to get the final bound).

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------

    Original Message


  • 3.  RE: Cplex stops too early

    Posted Mon October 25, 2021 10:09 AM

    Thanks a lot for your answer!

    In fact, I tried to call method model.solution.MIP.get_mip_relative_gap() and it returns a gap of 0.51% as well.

    I also tried to check solution and dual bound values (with model.solution.get_objective_value() and model.solution.MIP.get_best_objective()) and the values correspond to the last log line.

    Do you have any clues about what happens here?
    Thanks again!



    ------------------------------
    Ccl _
    ------------------------------

    Original Message


  • 4.  RE: Cplex stops too early

    IBM Champion
    Posted Mon October 25, 2021 11:25 AM
    You might want to collect kappa statistics (basis condition numbers) and check them. I'm not sure how CPLEX computes the gap, but it's possible that the gap used for convergence testing is from the presolved / modified model and the reported gap from the original model. If that's the case, and if there is some numerical instability, it might account for CPLEX reporting 0.51% but thinking the gap is smaller. (Full disclosure: Any time CPLEX does something I can't explain, my go-to theory is numerical issues.)

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------

    Original Message