Decision Optimization

 View Only
  • 1.  Cplex presolve is taking too long time for MIP model

    Posted Tue May 17, 2022 11:03 AM
    Hi Cplex experts,

    Cplex presolve is taking too long time for MIP model even after symmetry parameter set to 2. Is there any other way to reduce total run time.
    Below is the cplex log:
    =====================================================================================
    Version identifier: 20.1.0.0 
    CPXPARAM_Preprocessing_Symmetry 2
    Aggregator has done 1075825 substitutions...
    Aggregator has done 1151291 substitutions...
    Aggregator has done 1151478 substitutions...
    Tried aggregator 13 times.
    MIP Presolve eliminated 3139377 rows and 4421476 columns.
    MIP Presolve modified 29446 coefficients.
    Aggregator did 1151495 substitutions.
    Reduced MIP has 276632 rows, 1396614 columns, and 5492068 nonzeros.
    Reduced MIP has 2538 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 73.33 sec. (34893.20 ticks)
    Tried aggregator 2 times.
    MIP Presolve eliminated 125 rows and 0 columns.
    MIP Presolve modified 199 coefficients.
    Aggregator did 125 substitutions.
    Reduced MIP has 276382 rows, 1396489 columns, and 5491300 nonzeros.
    Reduced MIP has 2538 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 3.44 sec. (1796.50 ticks)
    Probing fixed 46 vars, tightened 3056 bounds.
    Probing time = 1.83 sec. (245.60 ticks)
    Clique table members: 294.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 8 threads.
    Root relaxation solution time = 311.94 sec. (81784.11 ticks)

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

    0 0 2232.5239 156 2232.5239 1613
    0 0 2232.5329 96 Cuts: 1013 5623
    0 0 2232.5329 97 Cuts: 656 10987
    0 0 2232.5329 95 Cuts: 577 26275
    * 0+ 0 2232.5452 2232.5329 0.00%

    Clique cuts applied: 1
    Cover cuts applied: 1
    Implied bound cuts applied: 60
    Flow cuts applied: 279
    Mixed integer rounding cuts applied: 191
    Gomory fractional cuts applied: 34

    Root node processing (before b&c):
    Real time = 1653.73 sec. (450080.54 ticks)
    Parallel b&c, 8 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) = 1653.73 sec. (450080.54 ticks)

    Solution pool: 1 solution saved.

    MIP - Integer optimal, tolerance (0.0001/1e-06): Objective = 2.2325452330e+03
    Current MIP best bound = 2.2325329471e+03 (gap = 0.0122858, 0.00%)
    Solution time = 1653.77 sec. Iterations = 26275 Nodes = 0 (1)
    Deterministic time = 450100.48 ticks (272.17 ticks/sec)

    ------------------------------
    ORE2021
    ------------------------------


  • 2.  RE: Cplex presolve is taking too long time for MIP model

    IBM Champion
    Posted Tue May 17, 2022 11:48 AM
    I don't think the issue is presolve. CPLEX reports 73 seconds for the initial presolve plus 3.4 seconds for additional presolving and 1.8 seconds for probing. So presolve, all told, took about a minute and a quarter. Solving the root LP apparently took 312 seconds (a bit over five minutes). You might want to experiment with using the interior point solver at the root, just to see if that's faster.

    The bulk of the root node processing time you highlighted in red seems to be consumed by cut generation, bound tightening and finding an initial feasible solution (perhaps via heuristics). If you want to speed that up, you can try turning off (or turning down the intensity of) some cut types and perhaps turning off some heuristics. However, bear in mind that with your current settings you are getting an optimal solution at the root node without any branching. If you tinker with the settings, CPLEX may need to branch, and it is entirely possible it could take longer to solve the model.

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



  • 3.  RE: Cplex presolve is taking too long time for MIP model

    Posted Thu May 19, 2022 01:41 AM
    Dear @Paul Rubin Thank you very much for your prompt reply. I tried barrier algorithm but it takes even more time.

    Below is the cplex log with cplex default parameter settings. Looks like symmetry detection consumes most of the time.
    Are there any better parameter settings where I can speed up the total run time?

    Version identifier: 20.1.0.0 | 2020-11-10 | 9bedb6d68
    Aggregator has done 1075641 substitutions...
    Aggregator has done 1151266 substitutions...
    Aggregator has done 1151453 substitutions...
    Tried aggregator 13 times.
    MIP Presolve eliminated 3139410 rows and 4421509 columns.
    MIP Presolve modified 30326 coefficients.
    Aggregator did 1151470 substitutions.
    Reduced MIP has 276584 rows, 1396501 columns, and 5491898 nonzeros.
    Reduced MIP has 2498 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 73.64 sec. (34893.52 ticks)
    Tried aggregator 2 times.
    Detecting symmetries...
    Elapsed time for symmetry detection = 8.63 sec. (10000.12 ticks)
    Elapsed time for symmetry detection = 16.84 sec. (20014.19 ticks)
    Elapsed time for symmetry detection = 25.14 sec. (30018.32 ticks)
    Elapsed time for symmetry detection = 42.86 sec. (40035.49 ticks)
    Elapsed time for symmetry detection = 68.69 sec. (50035.55 ticks)
    Elapsed time for symmetry detection = 98.31 sec. (60047.42 ticks)
    Elapsed time for symmetry detection = 124.81 sec. (70061.74 ticks)
    Elapsed time for symmetry detection = 150.92 sec. (80062.33 ticks)
    Elapsed time for symmetry detection = 201.03 sec. (90066.40 ticks)
    Elapsed time for symmetry detection = 262.39 sec. (100075.26 ticks)
    Elapsed time for symmetry detection = 318.89 sec. (110075.33 ticks)
    Elapsed time for symmetry detection = 377.81 sec. (120075.33 ticks)
    Elapsed time for symmetry detection = 433.66 sec. (130075.33 ticks)
    Elapsed time for symmetry detection = 464.34 sec. (140093.78 ticks)
    Elapsed time for symmetry detection = 517.59 sec. (150094.86 ticks)
    Elapsed time for symmetry detection = 549.86 sec. (160094.86 ticks)
    Elapsed time for symmetry detection = 618.31 sec. (170094.91 ticks)
    Elapsed time for symmetry detection = 686.53 sec. (180094.91 ticks)
    Elapsed time for symmetry detection = 751.38 sec. (190094.91 ticks)
    Elapsed time for symmetry detection = 810.69 sec. (200094.95 ticks)
    Elapsed time for symmetry detection = 867.89 sec. (210094.98 ticks)
    Elapsed time for symmetry detection = 927.03 sec. (220094.98 ticks)
    Elapsed time for symmetry detection = 956.13 sec. (230095.04 ticks)
    Elapsed time for symmetry detection = 1022.09 sec. (240095.04 ticks)
    Elapsed time for symmetry detection = 1036.95 sec. (250098.05 ticks)
    Elapsed time for symmetry detection = 1074.94 sec. (260098.12 ticks)
    Found 3.721999e+38214 symmetric permutations.
    MIP Presolve eliminated 130514 rows and 1017608 columns.
    MIP Presolve modified 220 coefficients.
    Aggregator did 127 substitutions.
    Reduced MIP has 145943 rows, 378766 columns, and 1531137 nonzeros.
    Reduced MIP has 2498 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 1130.53 sec. (274056.87 ticks)
    Probing fixed 69 vars, tightened 36736 bounds.
    Probing time = 2.45 sec. (1030.05 ticks)
    Clique table members: 347.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 8 threads.
    Root relaxation solution time = 119.75 sec. (35146.32 ticks)

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

    * 0+ 0 70340.5074 -19876.5635 128.26%
    0 0 2232.5930 214 70340.5074 2232.5930 60228 96.83%
    0 0 2232.5987 113 70340.5074 Cuts: 1454 65123 96.83%
    0 0 2232.6004 100 70340.5074 Cuts: 743 68280 96.83%
    0 0 2232.6004 92 70340.5074 Cuts: 559 69933 96.83%
    0 0 2232.6005 82 70340.5074 Cuts: 414 71576 96.83%
    * 0+ 0 2232.8050 2232.6005 0.01%

    Clique cuts applied: 4
    Cover cuts applied: 1
    Implied bound cuts applied: 165
    Flow cuts applied: 443
    Mixed integer rounding cuts applied: 361
    Gomory fractional cuts applied: 56

    Root node processing (before b&c):
    Real time = 1433.67 sec. (406876.19 ticks)
    Parallel b&c, 8 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) = 1433.67 sec. (406876.19 ticks)

    Solution pool: 2 solutions saved.

    MIP - Integer optimal, tolerance (0.0001/1e-06): Objective = 2.2328050029e+03
    Current MIP best bound = 2.2326004657e+03 (gap = 0.204537, 0.01%)
    Solution time = 1433.70 sec. Iterations = 73052 Nodes = 0 (1)
    Deterministic time = 406896.13 ticks (283.81 ticks/sec)​

    ------------------------------
    ORE2021
    ------------------------------



  • 4.  RE: Cplex presolve is taking too long time for MIP model

    Community Leadership
    Posted Thu May 19, 2022 02:52 AM
    Did you consider the symmetry parameter?
    https://www.ibm.com/docs/en/icos/20.1.0?topic=parameters-symmetry-breaking-mip-models

    ------------------------------
    Xavier
    ------------------------------



  • 5.  RE: Cplex presolve is taking too long time for MIP model

    IBM Champion
    Posted Thu May 19, 2022 11:47 AM
    You mentioned a nondefault setting (2) for the symmetry parameter. Since symmetry detection is eating up a lot of time, is there a reason not to use the default setting (or setting 0, which turns it off entirely)?

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



  • 6.  RE: Cplex presolve is taking too long time for MIP model

    Posted Fri May 20, 2022 10:49 AM
    Edited by ORE2021 Fri May 20, 2022 10:51 AM
    Hello @Paul Rubin, I tried running by turning off the symmetry detection (by setting 0), it helps a bit for this instance but for other instance (similar model) it is not helping rather deteriorated the run time.
    But later I tried to run with CPLEX 12.6 vs CPLEX20.1, and wonder that older version (12.6) is much more faster.
    I have attached the cplex log for your kind reference.
    Dear @Xavier Nodet, any advise on why CPLEX 12.6 is faster than cplex 20.1?

    Below is the run time summary:
    ​CPLEX12.6 (Default settings) : Total (root+branch&cut) = 538.92 sec. (182482.05 ticks)
    ​CPLEX20.1 (Default settings) : Total (root+branch&cut) = 1057.97 sec. (342575.29 ticks)

    ------------------------------
    ORE2021
    ------------------------------

    Attachment(s)

    txt
    cplex_126.txt   6 KB 1 version
    txt
    cplex_201.txt   12 KB 1 version


  • 7.  RE: Cplex presolve is taking too long time for MIP model

    IBM Champion
    Posted Fri May 20, 2022 11:44 AM
    Since the 12.6 log does not mention symmetry, I wonder if the difference is that 12.6 with default settings does not detect enough symmetry to be worth chasing and 20.1 with default settings does. If you run 20.1 on this model with symmetry detection turned off, how does the run time compare to 12.6?

    As far as the second problem instance (which does worse without symmetry detection), perhaps you could get better results there (and maybe on the first instance) if you added symmetry-breaking constraints rather than using CPLEX to break symmetries. What those constraints would look like depends on your model.

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