sub-optimal termination

[Jennifer Gossels]

I'm solving a continuous LP, and with certain inputs Barrier reports "Sub-optimal termination."  Yet, Gurobi does find the optimal objective in these cases; the answer I get with this LP is always the same as what I get with other, equivalent formulations that don't report sub-optimal termination.  What does this message mean?  Following is the relevant log output.

Optimize a model with 23099 rows, 548573 columns and 2192858 nonzeros

Coefficient statistics:

  Matrix range    [2e-04, 1e+00]

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

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

  RHS range       [8e-07, 5e+02]

Concurrent LP optimizer: dual simplex and barrier

Showing barrier log only...

Presolve removed 1242 rows and 10615 columns

Presolve time: 1.50s

Presolved: 21857 rows, 537958 columns, 2103291 nonzeros

Ordering time: 6.57s

Barrier statistics:

 Dense cols : 1

 AA' NZ     : 1.843e+06

 Factor NZ  : 2.969e+07 (roughly 500 MBytes of memory)

 Factor Ops : 7.254e+10 (roughly 1 second per iteration)

 Threads    : 3

                  Objective                Residual

Iter       Primal          Dual         Primal    Dual     Compl     Time

   0   1.60151779e+02 -1.12577172e+02  1.76e+06 0.00e+00  1.60e+01    12s

   1   1.59144206e+02 -4.78585854e+01  3.87e+05 6.41e-02  3.60e+00    15s

   2   6.34506202e+01  5.32133356e+00  3.67e+04 3.00e-02  2.89e-01    18s

   3   5.79323533e+01  3.10933311e+01  6.43e+03 1.28e-02  6.85e-02    21s

   4   2.82225641e+01  2.04876233e+01  7.15e+02 3.50e-03  7.81e-03    24s

   5   8.89883408e+00  7.05890811e+00  1.50e+02 8.37e-04  6.58e-04    27s

   6   3.04848612e+00  2.50641405e+00  4.71e+01 2.66e-04  9.45e-05    31s

   7   1.84498098e+00  1.48912142e+00  2.67e+01 1.47e-04  3.69e-05    34s

   8   8.54635789e-01  6.13746748e-01  1.15e+01 5.67e-05  8.48e-06    37s

   9   5.85971440e-01  3.43273308e-01  7.69e+00 3.06e-05  4.10e-06    41s

  10   5.01746791e-01  3.21610172e-01  5.82e+00 2.32e-05  2.83e-06    44s

  11   4.68983340e-01  3.18913755e-01  4.82e+00 2.10e-05  2.45e-06    47s

  12   4.06034376e-01  3.51896388e-01  6.69e-01 8.34e-06  8.43e-07    50s

  13   3.90893690e-01  3.81505421e-01  1.85e-02 1.05e-06  1.08e-07    53s

  14   3.90200109e-01  3.87740946e-01  2.09e-03 2.91e-07  2.96e-08    56s

  15   3.90127226e-01  3.90026849e-01  4.03e-04 1.04e-08  1.08e-09    59s

  16   3.90126420e-01  3.90028778e-01  3.87e-04 1.01e-08  1.05e-09    62s

  17   3.90126419e-01  3.90104533e-01  3.87e-04 3.76e-10  7.94e-11    65s

  18   3.90126419e-01  3.90104531e-01  3.87e-04 3.76e-10  1.37e-10    68s

  19   3.90126419e-01  3.90104530e-01  3.87e-04 3.76e-10  1.75e-10    72s

  20   3.90126419e-01  3.90104531e-01  3.87e-04 3.76e-10  1.90e-10    75s

  21   3.90126419e-01  3.90104531e-01  3.87e-04 3.76e-10  2.64e-10    78s

  22   3.90126419e-01  3.90104530e-01  3.87e-04 3.76e-10  2.74e-10    81s

  23   3.90126419e-01  3.90104528e-01  3.87e-04 3.76e-10  2.81e-10    84s

  24   3.90126419e-01  3.90104557e-01  3.87e-04 3.72e-10  6.92e-10    88s

  25   3.90126419e-01  3.90104424e-01  3.87e-04 3.69e-10  7.16e-10    91s

  26   3.90126419e-01  3.90104424e-01  3.87e-04 3.69e-10  7.30e-10    94s

  27   3.90126419e-01  3.90103767e-01  3.87e-04 3.75e-10  6.92e-10    97s

Barrier performed 27 iterations in 97.20 seconds

Sub-optimal termination - objective 3.90126419e-01

Crossover log...

    5515 DPushes remaining with DInf 0.0000000e+00                97s

       0 DPushes remaining with DInf 0.0000000e+00                97s

  501441 PPushes remaining with PInf 1.3421493e-02                98s

  398314 PPushes remaining with PInf 0.0000000e+00               100s

  288276 PPushes remaining with PInf 0.0000000e+00               105s

  226179 PPushes remaining with PInf 0.0000000e+00               110s

  171531 PPushes remaining with PInf 0.0000000e+00               115s

  124111 PPushes remaining with PInf 0.0000000e+00               120s

   75530 PPushes remaining with PInf 0.0000000e+00               125s

   22708 PPushes remaining with PInf 0.0000000e+00               130s

       0 PPushes remaining with PInf 0.0000000e+00               132s

  Push phase complete: Pinf 0.0000000e+00, Dinf 0.0000000e+00    132s

Iteration    Objective       Primal Inf.    Dual Inf.      Time

  506959    3.9010748e-01   0.000000e+00   0.000000e+00    132s

  506959    3.9010748e-01   0.000000e+00   0.000000e+00    132s

Solved with barrier

Solved in 506959 iterations and 131.82 seconds

Optimal objective 3.901074850e01

[Sonja Mars]

Hi,

> Sub-optimal termination

This message means that the Barrier algorithm had difficulties in converging and satisfying the tolerances. This often indicates numerical issues. However, Gurobi tries to solve you problem and in this case the crossover part of the algorithm starts with this sup-optimal solution and in the end Gurobi can solve your problem to optimality.

You might want to consider a different method (http://www.gurobi.com/documentation/6.5/refman/method.html#parameter:Method) for solving your LP, as Barrier is known to be not as robust as Simplex when it come to numerics.

Best regards,
Sonja

-----------------------------------------------------------------
Dr. Sonja Mars
Gurobi Optimization
ma...@gurobi.de
-----------------------------------------------------------------
Gurobi Optimizer 6.5 — State-of-the-art performance and best-in-class support
for your most important problems. Learn more at www.gurobi.com.

[Jennifer Gossels]

I'm using Concurrent, and apparently Barrier is faster than Simplex.  Are you saying that Barrier might "beat" Simplex but actually not find the optimal solution, and therefore I'd be better off forcing Gurobi to use Simplex?  Ultimately, Gurobi reports the model's status as OPTIMAL; would we ever get this status if it's not actually optimal?

Thanks,

Jennifer

[Sonja Mars]

Hi,

> I'm using Concurrent, and apparently Barrier is faster than Simplex. Are you saying that Barrier might "beat" Simplex but actually not find the optimal solution, and therefore I'd be better off forcing Gurobi to use Simplex?

No. Please note our Barrier algorithm consists of two parts: Barrier itself and Crossover, what I can see from the log is that Barrier itselfs runs into trouble, this is the reason why crossover has to do extra work to get things right again (this could slow down things). The solution you obtain in the end is optimal. What I am saying is, if Barrier runs into trouble, and you should be careful, your model might have numerical issues and a second look at the model to improve numerics might be a good idea.

[Jennifer Gossels]

Do you have suggestions for how I might improve numerics?  All the documentation I've read suggests that numerical issues are the result of too wide a range of coefficients.  Nothing in the Coefficient statistics section of the log looks problematic; I get the same numbers in that section for models that end up reporting Sub-optimal termination as I get for models that don't.  Can numerical issues also be caused by too wide a range of variable values in the optimal solution?

[Sonja Mars]

There are various reasons for numeric issues. Wide range of matrix coefficients can be one thing causing them and you are correct, your model does not look too bad. It is really hard to tell, why Barrier got into trouble.

Sonja

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.