Decision Optimization

Decision Optimization

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

 View Only
Back to discussions
Expand all | Collapse all

Different Results in Barrier Optimizer CPLEX 9.1 & 12.1 Update

  • 1.  Different Results in Barrier Optimizer CPLEX 9.1 & 12.1 Update

    Posted Thu August 06, 2009 01:15 AM

    Originally posted by: SystemAdmin


    [RealBruce said:]

    Hi everybody,

    I request your help for a problem that occured when we moved our system from CPLEX 9.1 to 12.1: Solving a large LP-Problem with the Barrier optimizer doesn't give the same result in 12.1 as 9.1 gave before, although no parameters were changed. The two results differ in the values of the primal, dual and upper infeasibility.

    Does version 12.1 have any default parameters set differently than 9.1 which I would have to change in order to get the same results in both versions? I already tried to turn on/of the parallelisation as well as changing the EPGap tolerance and the repeating/non-repeating presolve parameter. Please find attached the screen prompts of both versions. Especially the prompt regarding compression in version 9 puzzles me, since it doesn't occur in the new version.

    Version 9.1:

    Default variable names x1, x2 ... being created.
    Default row names c1, c2 ... being created.
    Tried aggregator 1 time.
    LP Presolve eliminated 0 rows and 2995 columns.
    Aggregator did 7 substitutions.
    Reduced LP has 2225 rows, 54294 columns, and 110083 nonzeros.
    Presolve time =    1.20 sec.
    Compression time =    0.10 sec.
    Compression reduced 3.29 MB A matrix to 0.41 MB
    Looking for dense columns with more than 5 nonzeros.
    Number of nonzeros in lower triangle of A*A' = 7799
    Using Approximate Minimum Degree ordering
    Total time for automatic ordering = 0.03 sec.
    Summary statistics for Cholesky factor:
      Rows in Factor            = 2225
      Integer space required    = 5357
      Total non-zeros in factor = 17748
      Total FP ops to factor    = 187238
    L has 784 super-nodes.
    Histogram of super-node widths:
    SupWidth:      2    10    17    21
      Number:    740      1    42      1

          0.07s for iteration (0.02s, 27 Mflops for lin. solve)
    solved psafe was  2.2159090581473e+11
    bnorm was  4.9265734400000e+08
    cnorm was  1.0000000000000e+03
    Primal safe is  2.2159090581473e+11
    Dual  safe is  1.0010000000000e+03
    Efficiency ratio is 0.096
    Max number of central corrections is 0
    Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf         
      0  7.0708615e+17  -2.0185471e+18  2.15e+16  2.31e+16  7.49e+05
          0.13s for iteration (0.02s, 27 Mflops for lin. solve)
      1  2.6003287e+17  -1.4975134e+17  8.23e+14  8.83e+14  1.01e+05
          0.29s for iteration (0.03s, 18 Mflops for lin. solve)
      2  1.0353687e+16  -6.5116087e+15  1.77e+13  1.90e+13  3.37e+03
          0.28s for iteration (0.02s, 27 Mflops for lin. solve)
      3  1.0005719e+15  -2.0223860e+15  1.72e+12  1.84e+12  1.01e+03
          0.30s for iteration (0.03s, 18 Mflops for lin. solve)
      4  1.4606556e+14  -2.0431774e+14  2.51e+11  2.69e+11  9.83e+01
          0.28s for iteration (0.02s, 27 Mflops for lin. solve)
      5  2.7811223e+13  -1.7794216e+13  4.75e+10  5.09e+10  7.31e+00
          0.29s for iteration (0.02s, 27 Mflops for lin. solve)
      6  7.1360435e+12  -3.3516800e+12  1.22e+10  1.30e+10  1.23e+00
          0.31s for iteration (0.03s, 18 Mflops for lin. solve)
      7  8.6584834e+11  -7.0254090e+11  1.31e+09  1.41e+09  1.20e-08
          0.28s for iteration (0.02s, 27 Mflops for lin. solve)
      8  4.5972551e+10  -2.3555793e+10  7.08e+07  7.60e+07  3.48e-08
          0.29s for iteration (0.02s, 27 Mflops for lin. solve)
      9  6.0130148e+09  -9.7765391e+09  1.05e+07  1.13e+07  2.70e-08
          0.28s for iteration (0.02s, 27 Mflops for lin. solve)
      10  4.3967611e+09  -4.5188592e+09  7.88e+06  8.45e+06  2.01e-08
          0.31s for iteration (0.03s, 18 Mflops for lin. solve)
      11  1.8076181e+08  -1.9453993e+09  8.24e+05  8.83e+05  1.53e-08
          0.28s for iteration (0.02s, 27 Mflops for lin. solve)
      12  1.0404375e+08  -3.6519347e+08  4.12e-01  4.64e-02  6.40e-09
          0.29s for iteration (0.03s, 18 Mflops for lin. solve)
      13  9.2874959e+07  -6.9969372e+07  4.41e+01  4.02e-02  1.56e-09
          0.29s for iteration (0.02s, 27 Mflops for lin. solve)
      14  9.2676100e+07  3.3433897e+07  4.37e+01  5.49e-02  6.93e-10
          0.29s for iteration (0.02s, 27 Mflops for lin. solve)
      15  6.8754367e+07  4.8958108e+07  1.54e+01  3.47e-02  1.84e-08
          0.29s for iteration (0.02s, 27 Mflops for lin. solve)
      16  6.2118627e+07  5.2175427e+07  5.79e+00  3.75e-02  1.04e-08
          0.28s for iteration (0.02s, 27 Mflops for lin. solve)
      17  6.1739910e+07  5.2677581e+07  5.43e+00  5.51e-02  7.30e-08
          0.30s for iteration (0.02s, 27 Mflops for lin. solve)
      18  6.1021085e+07  5.3454131e+07  4.89e+00  5.55e-02  4.74e-08
          0.29s for iteration (0.03s, 18 Mflops for lin. solve)
      19  5.9929797e+07  5.5476942e+07  4.37e+00  4.49e-02  5.30e-09
          0.28s for iteration (0.02s, 27 Mflops for lin. solve)
      20  5.8431650e+07  5.6397330e+07  3.04e+00  3.25e-02  1.90e-09
          0.36s for iteration (0.03s, 18 Mflops for lin. solve)
      21  5.7929218e+07  5.6805533e+07  6.84e+00  3.80e-02  2.65e-08
          0.34s for iteration (0.03s, 18 Mflops for lin. solve)
      22  5.7593545e+07  5.7160107e+07  2.80e+00  2.64e-02  2.75e-08
          0.31s for iteration (0.02s, 27 Mflops for lin. solve)
      23  5.7426796e+07  5.7248742e+07  7.92e-01  3.42e-02  2.77e-08
          0.35s for iteration (0.02s, 27 Mflops for lin. solve)
      24  5.7352079e+07  5.7308960e+07  9.52e-02  6.48e-02  3.33e-08
          0.35s for iteration (0.03s, 18 Mflops for lin. solve)
    Refinement - orig 3.36e-02, refined 3.36e-02, target 2.28e+02, 0 iter
      25  5.7342983e+07  5.7326826e+07  4.17e-02  7.89e-02  1.36e-08
          0.31s for iteration (0.02s, 27 Mflops for lin. solve)
    Refinement - orig 4.38e-02, refined 4.38e-02, target 2.28e+02, 0 iter
      26  5.7339924e+07  5.7336368e+07  3.51e-02  4.81e-02  3.00e-09
          0.31s for iteration (0.02s, 27 Mflops for lin. solve)
    Refinement - orig 4.88e-02, refined 4.88e-02, target 2.28e+02, 0 iter
      27  5.7338969e+07  5.7338552e+07  4.10e-02  1.17e-02  5.97e-10
          0.30s for iteration (0.02s, 27 Mflops for lin. solve)
    Refinement - orig 3.70e-02, refined 3.70e-02, target 2.28e+02, 0 iter
      28  5.7338791e+07  5.7338727e+07  3.34e-02  1.25e-04  1.59e-08
          0.30s for iteration (0.02s, 27 Mflops for lin. solve)
    Refinement - orig 6.22e-01, refined 6.22e-01, target 2.28e+02, 0 iter
      29  5.7338764e+07  5.7338759e+07  8.58e-01  1.25e-04  3.33e-09
          0.32s for iteration (0.02s, 27 Mflops for lin. solve)
    Refinement - orig 3.15e-02, refined 3.15e-02, target 2.28e+02, 0 iter
      30  5.7338760e+07  5.7338759e+07  1.23e-01  6.20e-06  2.02e-08

    Version 12.1:
    Default variable names x1, x2 ... being created.
    Default row names c1, c2 ... being created.
    Tried aggregator 1 time.
    LP Presolve eliminated 0 rows and 2995 columns.
    Aggregator did 7 substitutions.
    Reduced LP has 2225 rows, 54294 columns, and 110083 nonzeros.
    Presolve time =    1.03 sec.
    Parallel mode: none, using 1 thread for barrier
    Looking for dense columns with more than 5 nonzeros.
    Number of nonzeros in lower triangle of A*A' = 7799
    Using Approximate Minimum Degree ordering
    Total time for automatic ordering = 0.02 sec.
    Summary statistics for Cholesky factor:
      Rows in Factor            = 2225
      Integer space required    = 5357
      Total non-zeros in factor = 17748
      Total FP ops to factor    = 187238
    L has 784 super-nodes.
    Histogram of super-node widths:
    SupWidth:      2    10    17    21
      Number:    740      1    42      1

          0.07s for iteration (0.02s, 27 Mflops for lin. solve)
    Max number of central corrections is 0
    Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf         
      0  7.0708615e+17  -2.0185471e+18  2.15e+16  2.31e+16  7.49e+05
          0.13s for iteration (0.02s, 27 Mflops for lin. solve)
      1  2.6003287e+17  -1.4975134e+17  8.23e+14  8.83e+14  1.01e+05
          0.26s for iteration (0.02s, 27 Mflops for lin. solve)
      2  1.0353687e+16  -6.5116087e+15  1.77e+13  1.90e+13  3.37e+03
          0.27s for iteration (0.02s, 27 Mflops for lin. solve)
      3  1.0005719e+15  -2.0223860e+15  1.72e+12  1.84e+12  1.01e+03
          0.26s for iteration (0.02s, 27 Mflops for lin. solve)
      4  1.4606556e+14  -2.0431774e+14  2.51e+11  2.69e+11  9.83e+01
          0.26s for iteration (0.02s, 27 Mflops for lin. solve)
      5  2.7811223e+13  -1.7794216e+13  4.75e+10  5.09e+10  7.31e+00
          0.27s for iteration (0.02s, 27 Mflops for lin. solve)
      6  7.1360435e+12  -3.3516800e+12  1.22e+10  1.30e+10  1.23e+00
          0.32s for iteration (0.03s, 18 Mflops for lin. solve)
      7  8.6584834e+11  -7.0254090e+11  1.31e+09  1.41e+09  1.20e-08
          0.32s for iteration (0.03s, 18 Mflops for lin. solve)
      8  4.5972551e+10  -2.3555793e+10  7.08e+07  7.60e+07  3.45e-08
          0.26s for iteration (0.02s, 27 Mflops for lin. solve)
      9  6.0130148e+09  -9.7765391e+09  1.05e+07  1.13e+07  2.69e-08
          0.28s for iteration (0.02s, 27 Mflops for lin. solve)
      10  4.3967611e+09  -4.5188592e+09  7.88e+06  8.45e+06  2.00e-08
          0.27s for iteration (0.02s, 27 Mflops for lin. solve)
      11  1.8076181e+08  -1.9453993e+09  8.24e+05  8.83e+05  1.55e-08
          0.26s for iteration (0.02s, 27 Mflops for lin. solve)
      12  1.0404374e+08  -3.6519347e+08  4.44e-01  4.63e-02  6.38e-09
          0.26s for iteration (0.02s, 27 Mflops for lin. solve)
      13  9.2873849e+07  -6.8067834e+07  4.42e+01  4.00e-02  1.54e-09
          0.27s for iteration (0.02s, 27 Mflops for lin. solve)
      14  9.2673205e+07  3.3377709e+07  4.38e+01  5.77e-02  6.87e-10
          0.26s for iteration (0.02s, 27 Mflops for lin. solve)
      15  6.8794439e+07  4.8969033e+07  1.55e+01  3.66e-02  1.84e-08
          0.27s for iteration (0.02s, 27 Mflops for lin. solve)
      16  6.2125455e+07  5.2187001e+07  5.95e+00  3.65e-02  1.04e-08
          0.26s for iteration (0.02s, 27 Mflops for lin. solve)
      17  6.1747563e+07  5.2685796e+07  5.47e+00  4.98e-02  7.28e-08
          0.28s for iteration (0.03s, 18 Mflops for lin. solve)
      18  6.1023654e+07  5.3441163e+07  4.45e+00  5.41e-02  4.78e-08
          0.26s for iteration (0.02s, 27 Mflops for lin. solve)
      19  5.9953221e+07  5.5457477e+07  4.08e+00  4.37e-02  5.09e-09
          0.26s for iteration (0.02s, 27 Mflops for lin. solve)
      20  5.8438879e+07  5.6389505e+07  4.71e+00  3.27e-02  1.85e-09
          0.27s for iteration (0.02s, 27 Mflops for lin. solve)
      21  5.7928452e+07  5.6806394e+07  4.40e+01  4.09e-02  2.59e-08
          0.26s for iteration (0.02s, 27 Mflops for lin. solve)
      22  5.7594232e+07  5.7158733e+07  2.02e+01  3.73e-02  2.77e-08
          0.27s for iteration (0.03s, 18 Mflops for lin. solve)
      23  5.7427545e+07  5.7248761e+07  6.72e+00  2.69e-02  2.73e-08
          0.26s for iteration (0.02s, 27 Mflops for lin. solve)
      24  5.7352138e+07  5.7309021e+07  4.72e-01  4.19e-02  3.32e-08
          0.28s for iteration (0.02s, 27 Mflops for lin. solve)
    Refinement - orig 3.22e-02, refined 3.22e-02, target 2.28e+02, 0 iter
      25  5.7343028e+07  5.7326841e+07  1.62e-01  9.94e-02  1.35e-08
          0.28s for iteration (0.02s, 27 Mflops for lin. solve)
    Refinement - orig 4.58e-02, refined 4.58e-02, target 2.28e+02, 0 iter
      26  5.7339944e+07  5.7336464e+07  6.51e-02  4.04e-02  2.89e-09
          0.28s for iteration (0.03s, 18 Mflops for lin. solve)
    Refinement - orig 3.08e-02, refined 3.08e-02, target 2.28e+02, 0 iter
      27  5.7338964e+07  5.7338561e+07  3.06e-02  1.55e-02  5.79e-10
          0.27s for iteration (0.02s, 27 Mflops for lin. solve)
    Refinement - orig 3.83e-02, refined 3.83e-02, target 2.28e+02, 0 iter
      28  5.7338789e+07  5.7338729e+07  3.29e-02  1.25e-04  1.58e-08
          0.28s for iteration (0.03s, 18 Mflops for lin. solve)
    Refinement - orig 2.78e-01, refined 2.78e-01, target 2.28e+02, 0 iter
      29  5.7338763e+07  5.7338759e+07  2.41e-01  1.25e-04  2.61e-09
          0.27s for iteration (0.02s, 27 Mflops for lin. solve)
    Refinement - orig 2.65e-02, refined 2.65e-02, target 2.28e+02, 0 iter
      30  5.7338760e+07  5.7338759e+07  4.83e-02  3.29e-06  1.14e-08

    Thanks for your help!
    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: Different Results in Barrier Optimizer CPLEX 9.1 & 12.1 Update

    Posted Sat August 15, 2009 10:08 PM

    Originally posted by: SystemAdmin


    [notdarkyet said:]

    It may well be that some algorithmic parameter defaults have changed. Something simlar happened to one of my problems when updating from version 8 to 9 - the problem, which was solved before was declared infeasible with 9.0. The reason was the problem was badly conditioned and some tolerance defaults had changed. Try to write out all the parameter setting in both versions and compare it.

    The EpGap and repeat presolve optons should have nothing to do with the effect in barrier, since both concern MIP problems, not LPs.

    notdarkyet
    #CPLEXOptimizers
    #DecisionOptimization


  • 3.  Re: Different Results in Barrier Optimizer CPLEX 9.1 & 12.1 Update

    Posted Mon October 05, 2009 11:50 PM

    Originally posted by: SystemAdmin


    [achterberg said:]

    The objective function values seem to be identical, both at 5.7338760e+07. Note that due to degenerace, LP solutions are usually not unique. Often, there is a whole face of the polyhedron with identical objective values.

    Of course, the central path property of the barrier algorithm should get you to the center of the optimal face. But since CPLEX 9.1 we added a lot of algorithmic improvements to the code, which means that for numerical reasons, the output could have changed.

    For example, it might be that we added some presolving reductions that would fix some of the variables to, say, zero which in your CPLEX 9.1 solution are non-zero.

    In general, you cannot expect two versions to produce the exact same solution vector for degenerate problems. You can only expect them to produce the same optimal objective value, at least if your model is stable in terms of numerics.

    #CPLEXOptimizers
    #DecisionOptimization


Related Content