Decision Optimization

Decision Optimization

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

 View Only

  • 1.  Numerical effect

    Posted Sat January 21, 2012 12:01 PM

    Originally posted by: apscomeup


    Hi everyone!

    I have a problem to solve in IBM ILOG Optimization Studio.
    The problem is MIP and big.
    The problem has BigM in formulation(it gives better results than indicator constraints).

    The problem uses data from Access database which are prepared by Matlab.

    So, i solved the problem twice. Matlab prepared the same initial data twice too. Next, you can see the log of CPLEX.
    First time
    Tried aggregator 2 times.
    MIP Presolve eliminated 7512 rows and 4992 columns.
    MIP Presolve modified 1504 coefficients.
    Aggregator did 1915 substitutions.
    Reduced MIP has 1742 rows, 1622 columns, and 29132 nonzeros.
    Reduced MIP has 168 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Probing time = 0.00 sec.
    Tried aggregator 1 time.
    Presolve time = 0.09 sec.
    Probing time = 0.02 sec.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 2 threads.
    Root relaxation solution time = 1.11 sec.

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

    0 0 0.0044 9 0.0044 2162
    • 0+ 0 0.0110 0.0044 2162 60.11%
    • 0+ 0 0.0109 0.0044 2162 59.73%
    0 2 0.0044 9 0.0109 0.0044 2162 59.73%
    Elapsed real time = 27.49 sec. (tree size = 0.01 MB, solutions = 2)
    1 3 0.0046 9 0.0109 0.0044 7984 59.73%
    3 5 0.0052 9 0.0109 0.0046 11081 57.78%
    • 4+ 4 0.0094 0.0046 11347 51.20%
    • 4+ 4 0.0066 0.0046 11347 30.09%
    4 6 0.0052 15 0.0066 0.0046 11347 30.09%
    11 11 0.0056 7 0.0066 0.0049 16353 24.90%
    • 13 11 integral 0 0.0065 0.0049 16532 24.67%
    • 20 16 integral 0 0.0053 0.0050 17593 6.86%
    21 17 0.0053 11 0.0053 0.0050 17838 6.86%
    27 17 0.0062 1 0.0053 0.0050 23190 6.86%
    • 44 22 integral 0 0.0053 0.0050 24494 6.28%
    45 21 cutoff 0.0053 0.0050 24495 6.28%
    Elapsed real time = 48.78 sec. (tree size = 0.19 MB, solutions = 7)
    61 20 cutoff 0.0053 0.0050 36955 4.83%
    • 70 19 integral 0 0.0052 0.0051 41184 2.23%
    • 87+ 8 0.0051 0.0051 63773 0.46%
    • 90 8 integral 0 0.0051 0.0051 63800 0.40%
    • 98+ 4 0.0051 0.0051 70861 0.25%
    • 110 3 integral 0 0.0051 0.0051 82814 0.19%

    Root node processing (before b&c):
    Real time = 27.33
    Parallel b&c, 2 threads:
    Real time = 52.20
    Sync time (average) = 5.48
    Wait time (average) = 14.74
    Total (root+branch&cut) = 79.53 sec.

    Second time
    Tried aggregator 2 times.
    MIP Presolve eliminated 7512 rows and 4992 columns.
    MIP Presolve modified 1504 coefficients.
    Aggregator did 1915 substitutions.
    Reduced MIP has 1742 rows, 1622 columns, and 29132 nonzeros.
    Reduced MIP has 168 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Probing time = 0.00 sec.
    Tried aggregator 1 time.
    Presolve time = 0.06 sec.
    Probing time = 0.00 sec.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 2 threads.
    Root relaxation solution time = 0.86 sec.

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

    0 0 0.0044 9 0.0044 2145
    • 0+ 0 0.0110 0.0044 2145 60.11%
    0 0 0.0044 10 0.0110 Covers: 1 2350 60.11%
    Heuristic still looking.
    • 0+ 0 0.0084 0.0044 2350 47.63%
    0 2 0.0044 10 0.0084 0.0044 2350 47.63%
    Elapsed real time = 18.60 sec. (tree size = 0.01 MB, solutions = 2)
    1 3 0.0046 8 0.0084 0.0044 9123 47.63%
    • 15 15 integral 0 0.0066 0.0044 12174 32.79%
    • 17+ 15 0.0060 0.0044 14865 26.48%
    • 23 18 integral 0 0.0058 0.0047 15134 19.30%
    • 24 16 integral 0 0.0057 0.0047 15140 18.52%
    25 15 cutoff 0.0057 0.0047 15142 18.52%
    • 30+ 13 0.0055 0.0047 15604 14.92%
    • 36 12 integral 0 0.0053 0.0047 16876 12.54%
    37 13 0.0051 7 0.0053 0.0047 17045 12.54%
    38 12 cutoff 0.0053 0.0047 26686 12.54%
    • 41 10 integral 0 0.0052 0.0047 27045 10.74%
    56 13 cutoff 0.0052 0.0047 36141 9.63%
    Elapsed real time = 29.38 sec. (tree size = 0.01 MB, solutions = 7)
    • 81+ 10 0.0052 0.0049 41873 5.48%
    • 84 10 integral 0 0.0051 0.0049 41918 4.31%
    • 85 9 integral 0 0.0051 0.0049 41934 4.28%
    92 5 cutoff 0.0051 0.0051 54787 0.89%

    Cover cuts applied: 2

    Root node processing (before b&c):
    Real time = 18.53
    Parallel b&c, 2 threads:
    Real time = 21.36
    Sync time (average) = 3.70
    Wait time (average) = 5.66
    Total (root+branch&cut) = 39.89 sec.

    You can see the decision is near to each other(at least, equal with high accuracy). But log is different.
    it is resonable to suggest that the reason of difference is in data which prepares Matlab. But it seems it is ok. No difference.

    The question is, can it be any numerical effect in Matlab data, which is a reason of such difference in decision process?

    PS. I tried to solve the problem which is much bigger. In that case the difference is much bigger too. Using the same data sometimes CPLEX can not solve the problem for an hours and sometimes solve it very quickly.
    #DecisionOptimization
    #OPLusingCPLEXOptimizer


  • 2.  Re: Numerical effect

    Posted Mon February 20, 2012 03:27 AM

    Originally posted by: SystemAdmin


    The first step to analyze a problem like this would be to compare the two models that are actually solved. To do so export the models to an LP file and compare the two files. Are they different? If so, what are the differences?
    Since this question is not related to OPL I suggest you re-post it on the CPLEX Forum. You will find better help there.
    #DecisionOptimization
    #OPLusingCPLEXOptimizer


Related Content