Skip to main content

Wrong algo of dual simplex

Answered

Comments

3 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Could you please share the first ~20 lines of the log file which hold the coefficient statistics? Maybe your model is numerically sensitive, cf. Guidelines for Numerical Issues.

    0
  • LUYANG ZHANG
    First Question
    First Comment

    Hi Jaromil, thanks for replying. Here is the log info for barrier:

    Read MPS format model from file /project/large_scale_lp/MPS/1_day_out_SellerID1000_500.mps

    Reading time = 483.99 seconds

    : 26423572 rows, 265646022 columns, 962620739 nonzeros

    Changed value of parameter OptimalityTol to 0.0001

       Prev: 1e-06  Min: 1e-09  Max: 0.01  Default: 1e-06

    Changed value of parameter Method to 2

       Prev: -1  Min: -1  Max: 5  Default: -1

    Gurobi Optimizer version 9.0.3 build v9.0.3rc0 (linux64)

    Optimize a model with 26423572 rows, 265646022 columns and 962620739 nonzeros

    Model fingerprint: 0xe1378249

    Coefficient statistics:

      Matrix range     [2e-10, 2e+03]

      Objective range  [4e-17, 3e+00]

      Bounds range     [1e+00, 1e+00]

      RHS range        [3e-08, 6e+03]

    Warning: Model contains large matrix coefficient range

             Consider reformulating model or setting NumericFocus parameter

             to avoid numerical issues.

    Presolve removed 9 rows and 0 columns (presolve time = 24s) ...

    Presolve removed 20595 rows and 62763 columns (presolve time = 28s) ...

    Presolve removed 26082 rows and 67891 columns (presolve time = 63s) ...

    Presolve removed 26082 rows and 67908 columns (presolve time = 220s) ...

    Presolve removed 26082 rows and 67908 columns (presolve time = 576s) ...

    Presolve removed 42055 rows and 256166 columns (presolve time = 597s) ...

    Presolve removed 42055 rows and 256275 columns (presolve time = 625s) ...

    Presolve removed 42065 rows and 256276 columns (presolve time = 644s) ...

    Presolve removed 42065 rows and 256276 columns (presolve time = 655s) ...

    Presolve removed 42065 rows and 256276 columns (presolve time = 676s) ...

    Presolve removed 42065 rows and 256276 columns

    Presolve time: 681.33s

    Presolved: 26381507 rows, 265389746 columns, 961748159 nonzeros

     

    Elapsed ordering time = 5s

    Ordering time: 6.04s

     

    Barrier statistics:

    AA' NZ     : 3.624e+08

    Factor NZ  : 5.595e+08 (roughly 120.0 GBytes of memory)

    Factor Ops : 4.015e+11 (roughly 20 seconds per iteration)

    Threads    : 32

     

                      Objective                Residual

    Iter   Primal          Dual         Primal    Dual     Compl     Time

       0  -8.17974432e+05 -2.05040416e+02  1.64e+07 2.06e+00  4.62e+02  1119s

       1  -7.20979764e+05 -8.04044232e+06  1.44e+07 1.86e+00  4.07e+02  1620s

       2  -4.49836662e+05 -1.59304200e+07  8.83e+06 1.59e+00  2.49e+02  2828s

       3  -2.83720800e+05 -2.78088326e+07  5.51e+06 9.32e-01  1.59e+02  3289s

       4  -6.94724322e+04 -4.53485124e+07  1.32e+06 3.75e-14  3.92e+01  4516s

       5  -6.76518299e+03 -4.45540673e+07  1.25e+05 6.36e-14  3.85e+00  5956s

       6  -3.12039816e+03 -4.10408913e+07  5.56e+04 5.44e-14  1.78e+00  6959s

       7  -1.53877388e+03 -3.59250007e+07  2.54e+04 4.20e-14  8.76e-01  7922s

       8  -9.92771621e+02 -3.20684495e+07  1.49e+04 3.49e-14  5.58e-01  8745s

       9  -8.97602930e+02 -2.73753893e+07  1.31e+04 2.60e-14  4.91e-01  8971s

      10  -3.72940930e+02 -2.17360424e+07  3.00e+03 1.71e-14  1.91e-01  9299s

      11  -1.70442021e+02 -1.46894535e+07  6.78e+01 1.00e-14  6.58e-02  10096s

      12  -1.42573875e+02 -8.95055730e+06  8.46e+00 4.25e-15  3.69e-02  11084s

      13  -1.21216856e+02 -5.93698612e+06  4.60e+00 7.30e-15  1.99e-02  12148s

      14  -1.10226046e+02 -4.28915884e+06  2.37e+00 3.96e-15  1.16e-02  13561s

      15  -1.09266408e+02 -3.52386746e+06  2.13e+00 4.40e-15  9.35e-03  14516s

      16  -1.07805439e+02 -2.88767198e+06  1.75e+00 4.62e-15  7.34e-03  15749s

      17  -1.07052091e+02 -2.31250790e+06  1.53e+00 4.72e-15  5.73e-03  16808s

      18  -1.05829946e+02 -1.88114625e+06  1.03e+00 7.55e-15  4.28e-03  17996s

      19  -1.05922756e+02 -1.14632236e+06  7.37e-01 8.69e-15  2.49e-03  19238s

      20  -1.06790257e+02 -6.69930764e+05  3.01e-01 7.15e-15  1.31e-03  21748s

    Also, if the model is numerically sensitive, may I ask why both barrier and primal simplex works successfully in solving this model but dual simplex fails?

    Thanks!

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Also, if the model is numerically sensitive, may I ask why both barrier and primal simplex works successfully in solving this model but dual simplex fails?

    Given the ranges of your coefficients and bounds which have more than 10 orders of magnitude difference, it is very likely that any algorithm can take a certain path based solely on numerical error. This can then easily lead to very different results, depending on the algorithm used. Moreover, you loosen the OptimalityTol parameter which adds additional play room for the Simplex algorithm.

    You should definitely try to rescale and/or reformulate your model in order to improve its numerical properties. Our Guidelines for Numerical Issues are a great start in doing so. If for whatever reason, you cannot rescale of reformulate your model, you could alternatively try experimenting with the NumericFocus and Quad parameters to improve numerical stability of the algorithms.

    Best regards, 
    Jaromił

    0

Please sign in to leave a comment.