Skip to main content

extra simplex goes wild in large LP

Ongoing
MINZHUO HUANG
  • First Comment
  • First Question

Hi everyone.  

I am working on a two-stage stochastic programming in GAMS, which is a large LP. I used default setting of gurobi other than ‘BarHomogeneous = 1’. I looked over the process of how gurobi using barrier method to solve model. And when I looked into my model, I found that after finishing the cleaned up phase in the crossover section, log file said ‘solved with barrier’, and then immediately start the extra simplex. This caused me confusion and trouble, because the objective and dual infeasibility became really wild in the section and failed to converge. And this section usually take very long time to finish (in other SP but smaller size). I would like to know what is happening, and how could I turn off the "extra simplex after uncrush" ? I tried ‘networkalg = 0’ but it didn't work. 

Thank you!

Minzhuo Huang

The log file:

Optimize a model with 5501713 rows, 5115919 columns and 16499388 nonzeros
Model fingerprint: 0xfc78c4eb
Coefficient statistics:
  Matrix range     [5e-08, 2e+02]
  Objective range  [1e+00, 2e+06]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e+00, 1e+00]
Presolve removed 2575664 rows and 2611002 columns (presolve time = 5s) ...
Presolve removed 2575675 rows and 2611002 columns
Presolve time: 9.39s
Presolved: 2926038 rows, 2504917 columns, 12701859 nonzeros

Concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...

Ordering time: 1.27s

Barrier statistics:
 Dense cols : 12
 AA' NZ     : 2.309e+07
 Factor NZ  : 6.612e+07 (roughly 3.0 GB of memory)
 Factor Ops : 1.789e+09 (less than 1 second per iteration)
 Threads    : 10

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0   6.07634825e+08  0.00000000e+00  4.06e+02 5.34e-05  3.72e+03    16s
   1   5.33902916e+08 -2.35597951e+05  3.61e+02 2.27e+04  2.85e+03    17s
   2   5.17911132e+08 -5.12910639e+05  3.51e+02 1.93e+04  2.65e+03    18s
   3   3.40715599e+08 -1.58994920e+06  2.41e+02 8.16e+03  1.61e+03    20s
   4   2.84755410e+08 -3.01396766e+06  2.02e+02 5.33e+03  1.43e+03    22s
   5   1.74808502e+08 -4.46025190e+06  1.26e+02 3.34e+03  9.65e+02    25s
   6   1.41466092e+08 -7.02462569e+06  1.03e+02 1.55e+03  7.60e+02    27s
   7   5.85954025e+07 -8.48510022e+06  4.63e+01 4.90e+02  2.59e+02    29s
   8   1.97688151e+07 -6.01376725e+06  1.83e+01 1.32e+02  6.61e+01    31s
   9   8.79637902e+06 -5.04446700e+06  9.43e+00 8.17e+01  2.88e+01    32s
  10   5.58077696e+06 -4.05584280e+06  6.51e+00 5.74e+01  1.66e+01    34s
  11   1.22197565e+06 -1.67629970e+06  2.02e+00 1.17e+01  2.72e+00    35s

........

160   8.05388012e-03  8.05386280e-03  9.63e-11 5.37e-11  3.77e-15   571s
161   8.05387259e-03  8.05386333e-03  8.68e-11 5.73e-10  2.05e-15   576s

Barrier solved model in 161 iterations and 575.79 seconds (487.24 work units)
Optimal objective 8.05387259e-03

Crossover log...
.....
Push phase complete: Pinf 8.7104201e+01, Dinf 1.4562546e+02    844s


(Cleaned up by simplex)...
Iteration    Objective       Primal Inf.    Dual Inf.      Time
 1100045    8.0515928e-03   0.000000e+00   1.456255e+02    863s
 1100858    8.0501565e-03   0.000000e+00   6.601718e+01    946s
......
 1198239    8.0543415e-03   3.578557e-04   0.000000e+00   8917s
 1198373    8.0543417e-03   0.000000e+00   0.000000e+00   8959s
 1198499    8.0543414e-03   4.939945e-05   0.000000e+00   9023s

Solved with barrier.

(extra simplex phase immediately)
 1198582    8.0543414e-03   2.246510e-02   1.115694e+13   9171s
 1200033    5.5956673e-02   1.443432e-01   6.648109e+12   9332s
 1200531    5.8764209e-02   5.057457e-02   4.732342e+11   9404s
 1201160    6.5973614e+01   4.469646e-02   2.328990e+12   9500s
...
... (Dual infeasibility and the objective function went wild during this section)

...
 1269200    9.5231364e+05   0.000000e+00   2.074759e+11  13242s
 1270280    9.5215776e+05   0.000000e+00   1.368960e+13  13294s
 1271360    9.5213244e+05   0.000000e+00   1.681290e+12  13353s
......
 1299510    9.1084776e+05   0.000000e+00   1.433108e+11  16012s
Extra simplex iterations after uncrush: 100928

Stopped in 1299510 iterations and 16012.04 seconds (59089.13 work units)
Time limit reached

Related to

0

Comments

7 comments

Date Votes
  • Riley Clement
    • Gurobi Staff

    Hi Minzhuo,

    The cause of this issue you are seeing is found in this line:

    Extra simplex iterations after uncrush: 100928

    When the model goes through the presolve routine, we say that is being “crushed” to the presolve space.  The optimization then operates on the presolved model and when it is done, we need to “uncrush” solutions back to the original problem space.

    What is happening in your optimization is that the solution in the presolved space satisfies tolerances but when we uncrush it, there are large violations which then need to be cleaned up by simplex, which is where we get the “extra simplex iterations …” message from.  Typically violations after uncrush are small and simplex can clean them up quickly but this is not the case here.

    Note that your matrix range reported in the log is [5e-08, 2e+02].  The lower end is smaller than our default feasiblity tolerance, and perhaps this is part of the issue.  I would also create a presolve model and examine it's matrix coefficients - you will want the feasibility tolerance to be smaller than the low end of the matrix range.  In Python:

    with mymodel.presolve() as p:
    p.printStats()

    If using a tighter feasibility tolerance does not improve the performance then I would experiment with some of the parameters mentioned here: Solver Parameters to Manage Numerical Issues
    In particular I would first experiment with ScaleFlag (=2,3), Aggregate (=0) and NumericFocus (=1,2)

    I would also recommend reading the following section of our reference manual: Why Scaling and Geometry is Relevant

    - Riley

    0
  • MINZHUO HUANG
    • First Comment
    • First Question

    Dear Riley,

     

             Thank you so much for the reply! After following your suggestion and read the documents, I am able to solve the problem within a reasonable time period without any warning information. I would like to have a follow-up question according to the result. 

             I am doing an investment planning type two-stage SP, with objective function that minimize the total cost. I found that the final solution obtained after crossover and clean up process is very closed to the solution obtained from barrier method before crossover (gap < 0.001%). Since I am working on investment planning, I think second stage decision (system operation) is not as important as first stage decision. I am wondering if I could just obtain solution from barrier rather than the full process after crossover? Since the accuracy on second stage decision is not so important. Because it will greatly reduce my computational time (barrier for 10min, whole process for 5hr). I tried to set threads = 1 and crossover = 0, but it started using simplex instead of barrier. Is there any way to force GUROBI only use barrier and return barrier solution? Thank you!

     

    Minzhuo Huang

    0
  • Riley Clement
    • Gurobi Staff

    Hi Minzhuo,

    In your case running barrier without crossover could be a good idea.  I wouldn't touch Threads, if you don't have to - barrier parallelizes well with multiple threads - but you will need to set Method=2 in addition to Crossover=0.  By default if you set 1 thread, and leave Method at its default, then dual simplex will be used.

    - Riley

    0
  • MINZHUO HUANG
    • First Comment
    • First Question

    Dear Riley,

             Just an update from the previous question. I already found the way to only use barrier method, which can be done by setting ‘Method = 2’. But I would still like to hear opinion from you about the barrier solution. Please do share some insights on barrier solution and basis solution in a two-stage SP problem. Thank you!

    Minzhuo Huang

    0
  • MINZHUO HUANG
    • First Comment
    • First Question

    Dear Riley,

             Thank you for your instant update, much appreciated. Looks like you foresee my response. Thank you for your help, have a nice day!

    Minzhuo Huang

    0
  • Riley Clement
    • Gurobi Staff

    Thanks Minzhuo, you too.

    I'll add a slight addition to my response - we lean on crossover to help improve the accuracy.  If you don't run crossover then barrier will work a little bit harder to improve the accuracy itself.

    - Riley

    0
  • MINZHUO HUANG
    Edited
    • First Comment
    • First Question

    Hi Riley,

         Thanks for the add-on, it's very helpful. Which cause me raising another question on this: I do understand the limit of barrier method. Is it possible to improve the accuracy by changing parameters like ‘Numericfoucs’ and ‘BarConvTol’ ? For example, if I try to set ‘BarConvTol = 1e-11’ and ‘Numericfocus = 3’, will this help? I know it will take longer time and more barrier iterations, but I believe it will still much faster than a complete process includes crossover. Thank you!

    Minzhuo Huang

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post