Wrong algo of dual simplex
Answered
Hi team, I'm using GUROBI to solve a large-size MPS file which is roughly about 60G. This problem contains
26423572 rows, 265646022 columns, 962620739 nonzeros
I tried with three methods, which are respectively: barrier, dual simplex, and primal simplex.
Both barrier and primal simplex gives us the similar optimal value:
Optimal objective -1.550697119e+02
However, dual simplex gives the objective value of
Optimal objective -1.467550711e+02
This is too off from the true opt value, meaning that the dual simplex method has something wrong. In fact, in the last few iterations, the output log file of dual simplex reports significantly positive Dual Inf. value, which is contradictory to the fact.
May I ask why the dual simplex method gives the wrong solution?
Thanks!
-
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 -
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 -
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.
Comments
3 comments