Decision Optimization

Decision Optimization

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

 View Only

  • 1.  Terminating the MIP optimization

    Posted Sun March 28, 2010 12:44 PM

    Originally posted by: SystemAdmin


    I've run 2 cases under different cuts and probes values with the same terminating criteria. While one of this is terminated without dropping within the EpGap I set (4%). Please see the following node logs
    Case 2:
    1 of 1 MIP starts provided solutions.
    MIP start 'm1' defined initial solution with objective -4592.5659.
    Tried aggregator 3 times.
    MIP Presolve eliminated 190153 rows and 64086 columns.
    MIP Presolve modified 79045 coefficients.
    Aggregator did 4462 substitutions.
    Reduced MIP has 57190 rows, 33030 columns, and 256793 nonzeros.
    Reduced MIP has 15388 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 1.17 sec.
    Clique table members: 20245.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: none, using 1 thread.
    Root relaxation solution time = 32.33 sec.

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

    • 0+ 0 -4592.5659 0 ---
    0 0 -3460.6744 322 -4592.5659 -3460.6744 40404 24.65%
    0 0 -3490.2645 929 -4592.5659 Cuts: 188 43570 24.00%
    0 0 -3506.7209 902 -4592.5659 Cuts: 96 46353 23.64%
    0 0 -3506.8998 943 -4592.5659 Cuts: 29 46672 23.64%
    0 0 -3507.1370 1017 -4592.5659 Cuts: 21 47512 23.63%
    0 0 -3507.8035 1163 -4592.5659 Cuts: 32 48680 23.62%
    0 0 -3507.8086 1017 -4592.5659 Cuts: 23 48742 23.62%
    0 0 -3507.8091 1038 -4592.5659 Cuts: 15 48789 23.62%
    0 0 -3507.9859 1158 -4592.5659 Cuts: 16 49452 23.62%
    Heuristic still looking.
    Heuristic still looking.
    • 0+ 0 -3742.2824 -3507.9859 49544 6.26%
    • 0+ 0 -3741.6587 -3507.9859 49544 6.25%
    0 2 -3508.0236 1087 -3741.6587 -3508.0869 49544 6.24%
    Elapsed time = 115.83 sec. (tree size = 0.00 MB, solutions = 3)

    GUB cover cuts applied: 7
    Clique cuts applied: 3
    Cover cuts applied: 31
    Implied bound cuts applied: 124
    Flow cuts applied: 20
    Mixed integer rounding cuts applied: 157
    Flow path cuts applied: 0
    Zero-half cuts applied: 0
    Gomory fractional cuts applied: 6
    Disjunctive cuts applied: 0
    Solution status = Optimal
    Solution value = -3741.66
    Solutin time = 454.66
    case number: 2

    Case 4
    1 of 1 MIP starts provided solutions.
    MIP start 'm1' defined initial solution with objective -4592.5659.
    Tried aggregator 3 times.
    MIP Presolve eliminated 190153 rows and 64086 columns.
    MIP Presolve modified 79045 coefficients.
    Aggregator did 4462 substitutions.
    Reduced MIP has 57190 rows, 33030 columns, and 256793 nonzeros.
    Reduced MIP has 15388 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Elapsed time 10.01 sec. for 31% of probing (1761 nz added).
    Elapsed time 20.02 sec. for 47% of probing (41 vars fixed, 4583 nz added).
    Elapsed time 30.04 sec. for 58% of probing (41 vars fixed, 5151 nz added).
    Elapsed time 40.06 sec. for 65% of probing (41 vars fixed, 6242 nz added).
    Elapsed time 50.07 sec. for 69% of probing (41 vars fixed, 8644 nz added).
    Elapsed time 60.08 sec. for 84% of probing (41 vars fixed, 9630 nz added).
    Probing fixed 41 vars, tightened 3846 bounds.
    Probing added 10097 nonzeros.
    Probing changed sense of 1198 constraints.
    Probing time = 67.34 sec.
    Tried aggregator 2 times.
    MIP Presolve eliminated 4226 rows and 918 columns.
    MIP Presolve modified 2286 coefficients.
    Aggregator did 1269 substitutions.
    Reduced MIP has 51695 rows, 30843 columns, and 252844 nonzeros.
    Reduced MIP has 13564 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 69.15 sec.
    Elapsed time 10.01 sec. for 59% of probing (36 vars fixed, 1687 nz added).
    Elapsed time 20.03 sec. for 68% of probing (36 vars fixed, 3897 nz added).
    Elapsed time 30.04 sec. for 95% of probing (36 vars fixed, 4220 nz added).
    Probing fixed 36 vars, tightened 1453 bounds.
    Probing added 4186 nonzeros.
    Probing time = 30.80 sec.
    Clique merging time = 82.54 sec.
    Clique table members: 290868.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: none, using 1 thread.
    Root relaxation solution time = 30.62 sec.

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

    • 0+ 0 -4592.5659 0 ---
    0 0 -3461.1245 248 -4592.5659 -3461.1245 39061 24.64%
    0 0 -3512.8444 683 -4592.5659 Cuts: 191 42981 23.51%
    0 0 -3521.0622 637 -4592.5659 Cuts: 94 43843 23.33%
    0 0 -3523.1350 421 -4592.5659 Cuts: 75 44215 23.29%
    0 0 -3527.4801 629 -4592.5659 Cuts: 55 45340 23.19%
    0 0 -3531.1344 1095 -4592.5659 Cuts: 134 47055 23.11%
    0 0 -3533.2202 1230 -4592.5659 Cuts: 31 47954 23.07%
    0 0 -3534.6975 1709 -4592.5659 Cuts: 33 49628 23.03%
    0 0 -3534.6982 1710 -4592.5659 MIRcuts: 8 49645 23.03%
    0 0 -3535.6773 1772 -4592.5659 Cuts: 12 51119 23.01%
    0 0 -3536.0311 1840 -4592.5659 Cuts: 4 51444 23.01%
    0 0 -3536.0461 1865 -4592.5659 Cuts: 3 51520 23.01%
    Heuristic still looking.
    0 2 -3536.0461 1865 -4592.5659 -3536.0623 51520 23.00%
    Elapsed time = 855.96 sec. (tree size = 0.00 MB, solutions = 1)
    100 88 -4301.8612 132 -4592.5659 -3541.1958 92791 22.89%
    • 110+ 96 -4384.4875 -3541.1958 96404 19.23%
    • 120+ 104 -4381.0715 -3541.1958 96707 19.17%
    • 140+ 53 -4098.6415 -3545.3004 101145 13.50%
    • 170+ 70 -3806.3773 -3545.3004 109682 6.86%
    200 91 -3738.1296 238 -3806.3773 -3575.2761 123005 6.07%
    • 270+ 119 -3797.0665 -3644.9645 159116 4.01%

    GUB cover cuts applied: 2
    Clique cuts applied: 4
    Cover cuts applied: 25
    Implied bound cuts applied: 12
    Flow cuts applied: 45
    Mixed integer rounding cuts applied: 147
    Flow path cuts applied: 0
    Zero-half cuts applied: 2
    Gomory fractional cuts applied: 20
    Disjunctive cuts applied: 0
    Solution status = Optimal
    Solution value = -3797.07
    Solutin time = 1660.17
    case number: 4

    So we can see the case 4 is terminated by dropping into the EpGap I set ( 4% ), while the previous one failed. And the elapsed time, the number of nodes, the size of tree and the number of integer solutions are all larger than the previous one. If the first one is terminated by abs MIP gap, then I think the relative MIP gap should also satisfy the 4%... So would anyone tell me for what reason the first one is terminated? Many thanks.

    Jim Zhang
    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: Terminating the MIP optimization

    Posted Sun March 28, 2010 03:31 PM

    Originally posted by: SystemAdmin


    Why do you think that the first of your runs did not hit the termination criterion? In your output I don't see the necessary information to either prove or disprove this. Actually, the "Solution Status" is shown as "Optimal" in your output. Please note that CPLEX does not show a log line for each individual node of the search tree in default settings. Therefore, it could very well be that the gap dropped to below 4% after less than 100 nodes.

    If you want to see each node in the log, you need to set the MIPInterval parameter to 1.
    #CPLEXOptimizers
    #DecisionOptimization


  • 3.  Re: Terminating the MIP optimization

    Posted Sun March 28, 2010 04:01 PM

    Originally posted by: SystemAdmin


    Thank you. I missed the point of parameter setting for the # of nodes information...
    #CPLEXOptimizers
    #DecisionOptimization


Related Content