Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only

  • 1.  Root relaxation is taking long time for MIP problem

    Posted Mon July 11, 2022 10:22 AM
    Hello CPLEX Experts,
    I have an MIP problem which is taking long time at root relaxation, Even I have tried different LPMETHOD to solve it, it is taking almost same time. Any advise how can I reduce the run time? I have attached below CPLEX log for your reference.

    Presolve has eliminated 5209859 rows and 6089225 columns...
    Presolve has improved bounds 498312 times...
    Presolve has eliminated 5210222 rows and 6092110 columns...
    Presolve has improved bounds 500833 times...
    Presolve has eliminated 5210610 rows and 6094590 columns...
    Presolve has improved bounds 502862 times...
    Aggregator has done 2413460 substitutions...
    Tried aggregator 3 times.
    MIP Presolve eliminated 5228158 rows and 6143952 columns.
    MIP Presolve modified 1566 coefficients.
    Aggregator did 2413749 substitutions.
    Reduced MIP has 408566 rows, 860523 columns, and 3723727 nonzeros.
    Reduced MIP has 425 binaries, 375 generals, 0 SOSs, and 0 indicators.
    Presolve time = 99.20 sec. (44533.23 ticks)
    Probing time = 4.50 sec. (36.72 ticks)
    Tried aggregator 1 time.
    MIP Presolve eliminated 4115 rows and 8298 columns.
    Reduced MIP has 404448 rows, 852225 columns, and 3702818 nonzeros.
    Reduced MIP has 425 binaries, 375 generals, 0 SOSs, and 0 indicators.
    Presolve time = 3.67 sec. (1761.54 ticks)
    Probing time = 4.34 sec. (36.46 ticks)
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 32 threads.
    Root relaxation solution time = 5601.89 sec. (1058740.06 ticks)

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

    * 0+ 0 4.23265e+16 0.0000 100.00%
    * 0+ 0 3.51737e+15 0.0000 100.00%
    0 0 1.76241e+12 44 3.51737e+15 1.76241e+12 502164 99.95%
    * 0+ 0 1.76241e+12 1.76241e+12 0.00%
    0 0 cutoff 1.76241e+12 1.76241e+12 502206 0.00%
    Elapsed time = 7073.27 sec. (1787090.71 ticks, tree = 0.01 MB, solutions = 3)

    Mixed integer rounding cuts applied: 9
    Gomory fractional cuts applied: 4

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

    Solution pool: 4 solutions saved.

    MIP - Integer optimal solution: Objective = 1.7624093313e+12
    Solution time = 7074.47 sec. Iterations = 502206 Nodes = 0
    Deterministic time = 1787558.10 ticks (252.68 ticks/sec)


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

    #DecisionOptimization


  • 2.  RE: Root relaxation is taking long time for MIP problem

    Posted Mon July 11, 2022 11:14 AM
    You mentioned trying different values of LPMETHOD. Did that include 4 (barrier method)? Also, what are the ranges for your model coefficients? (If the model has numerical issues, I think that could slow down solution at the root.)

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

    Original Message


  • 3.  RE: Root relaxation is taking long time for MIP problem

    Posted Tue July 12, 2022 10:52 AM
    Hello @Paul Rubin thanks for your prompt reply. I have tried PRIMAL SIMPLEX, DUAL SIMPLEX and BARRIER as LPMETHOD but all are taking almost similar time as above.

    As CPLEX ​doesn't provide coefficient ranges, below coefficient statistics I got from GUROBI solver.
    Coefficient statistics:
    Matrix range [1e-03, 2e+04]
    Objective range [1e+07, 1e+07]
    Bounds range [1e+00, 1e+04]
    RHS range [1e+00, 1e+08]

    Also another point is, GUROBI can solve this problem within 5 mins but CPLEX really struggling to get optimum solution in a limited time (e.g. 30 mins).

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

    Original Message


  • 4.  RE: Root relaxation is taking long time for MIP problem

    Posted Tue July 12, 2022 11:22 AM
    CPLEX will show you the coefficient ranges if you know how to ask for them. :-) In any case, I do not see any red flags, although I usually try (via scaling) to avoid getting seven or eight orders of magnitude difference between smallest and largest in any category.

    It is possible that some of the presolve reductions performed by CPLEX could be making the root problem harder for CPLEX to solve. I had one model a while back where turning off symmetry reduction helped a lot. Unfortunately, with so many parameters controlling various aspects of the presolve, it's an NP-hard problem to find the optimal combination. There is a section in the user manual (User's Manual for CPLEX > Advanced programming techniques > Manual control of presolve) that might shed some light.

    Speaking of the user's manual, I would also recommend taking a look at the sections under Continuous optimization > Solving LPs: simplex optimizers > Diagnosing performance problems to see if anything regarding ill-conditioning or numerical difficulties is helpful.

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

    Original Message


Related Content