Documentation

Barrier Logging

The barrier log can be divided into five sections: the presolve section, the barrier preprocessing section, the barrier progress section, the crossover progress section, and the summary section.

Presolve Section

As mentioned earlier, the first thing the Gurobi optimizer does when optimizing a model is to apply a presolve algorithm in order to simplify the model. The first section of the Gurobi log provides information on the extent to which presolve succeeds in this effort. Consider the following example output from NETLIB model dfl001:

Presolve removed 2348 rows and 3329 columns
Presolve time: 0.05s
Presolved: 3723 rows, 8901 columns, 31074 nonzeros

The example output shows that presolve was able to remove 2381 rows and 3347 columns, and it required 0.12 seconds. The final line in the presolve section shows the size of the model after presolve. This is size of the model that is passed to the barrier optimizer. Note that the solution that is computed for this model is automatically transformed into a solution for the original problem once barrier finishes (in a process often called uncrushing), but this uncrush step is transparent and produces no log output.

Barrier Preprocessing Section

The factor matrix for the linear system solved in each iteration of the barrier method can be quite large and quite expensive to compute. In order to reduce the cost of this computation, the first step of the barrier algorithm is to compute a fill-reducing reordering of the rows and columns of this matrix. This step can be quite expensive, but the cost is recouped in the reduced cost of the subsequent barrier iterations.

Once this fill-reducing reordering has been computed, the Gurobi Optimizer outputs information related to the barrier factor matrix:

Barrier statistics:
 AA' NZ     : 3.688e+04
 Factor NZ  : 8.960e+05 (roughly 12 MBytes of memory)
 Factor Ops : 4.489e+08 (less than 1 second per iteration)
 Threads    : 4

The first line indicates how many columns from the constraint matrix were treated as dense. The second line indicates how many variables in the model are free. Dense columns and free variables can sometimes lead to numerical difficulties in the barrier solver, so it is sometimes useful to know that they are present. Note that these lines are only printed when the model contains dense columns or free variables.

The next line shows the number of off-diagonal entries in the lower triangle of . A scaled version of this matrix is factored in each iteration of the barrier algorithm, so the structure of the Cholesky factor depends on the structure of .

The final two lines indicate the number of non-zero values in the factor matrix, and the number of floating-point operations required to factor it. Note that the log also provides an estimate of how much memory will be needed by the barrier algorithm, and how long each barrier iteration will require: These are rough estimates that are meant to provide a general sense of how difficult the model will be to solve. If you want to obtain an estimate of overall solution time, note that most models achieve convergence in roughly 50 iterations, but there are many exceptions. Crossover runtime is typically comparable to the cost of a few barrier iterations, but this time can vary considerably, depending on the model characteristics.

Progress Section

The third section of the Gurobi barrier output provides information on the progress of the barrier method:

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0   1.79149254e+12 -1.13818577e+09  1.48e+04 0.00e+00  2.10e+09     0s
   1   7.20689339e+11 -4.28901315e+10  5.94e+03 6.41e+06  9.48e+08     0s
   2   3.28659311e+11 -9.90094825e+10  2.50e+03 2.41e+06  4.07e+08     0s
   3   7.11842071e+10 -1.00890021e+11  2.42e+02 3.26e+05  5.64e+07     0s
   4   2.37964375e+10 -2.53121906e+10  2.12e+01 2.63e+04  7.99e+06     0s
   5   4.63460621e+09 -7.99933422e+09  4.79e-01 6.15e+03  1.44e+06     0s
   6   1.53036904e+09 -1.74378459e+09  7.41e-02 1.27e+03  3.56e+05     0s
   7   6.05175915e+08 -8.35779464e+08  2.45e-02 5.46e+02  1.55e+05     0s
   8   2.80306252e+08 -3.89069571e+08  1.03e-02 3.06e+02  7.19e+04     0s
   9   1.29713987e+08 -1.46406904e+08  3.86e-03 7.31e+01  2.95e+04     0s
  10   6.49841750e+07 -5.76724647e+07  1.58e-03 2.11e+01  1.31e+04     0s

The seven columns in each output row show the number of barrier iterations performed to that point, the primal and dual objective values for the current barrier iterate, the magnitude of the primal and dual infeasibilities for the current iterate (computed as the infinity-norms of the primal and dual residual vectors, respectively), the magnitude of the complementarity violation of the current primal and dual iterates (the dot product of the primal solution and the dual reduced cost vector), and the amount of time expended to that point (measured using wall clock time). When the primal infeasibility, dual infeasibility, and complementarity satisfy barrier convergence tolerances (controlled using the BarConvTol parameter), the solution is declared optimal and optimization is complete.

Unlike the simplex and MIP optimizers, the barrier optimizer produces a log line for each iterate, independent of the value of the DisplayInterval parameter.

You may sometimes see a star after the iteration count in the barrier progress log:

  15   2.42800468e+03  8.54543324e+04  1.68e+02 1.02e-09  8.30e+04     0s
  16   4.05292006e+03  4.65997441e+04  1.82e+02 2.50e-01  4.25e+04     0s
  17*  4.88742259e+08  4.30781025e+10  5.17e+00 1.31e-01  2.52e-02     0s
  18*  1.21709951e+06  3.39471138e+13  8.55e-06 3.14e-06  3.14e-05     0s
  19* -1.38021972e+06  3.31580578e+16  3.42e-08 8.20e-09  3.22e-08     0s
  20*  1.25182178e+06  3.31575855e+19  6.54e-12 7.34e-09  3.22e-11     0s

This indicates that the model may be primal or dual infeasible. Note that these intermediate indications of infeasibility won't necessarily turn into an infeasibility proof, so the star may disappear in later iterations.

Crossover Section

The fourth section of the barrier log provides information on the crossover step. This section is only present when crossover is selected (as controlled through the Crossover parameter. Crossover converts the interior point solution produced by the barrier algorithm to a basic solution.

The first stage in crossover is to push variables to bounds in order to obtain a valid basic solution. By default, this is done for dual variables first, then for primal variables. Progress of this phase is tracked with this portion of the crossover log...

Crossover log...

       0 DPushes remaining with DInf 2.0627140e-06                 3s

     139 PPushes remaining with PInf 2.0382353e-03                 3s
       0 PPushes remaining with PInf 2.0382353e-03                 3s

  Push phase complete: Pinf 2.0382353e-03, Dinf 3.5643461e-06      3s

Each line indicates how many push steps remain, the amount of infeasibility in the current solution, and the elapsed barrier time.

Upon completion of the push phase, crossover has a basic solution that isn't necessarily optimal. The resulting basis is passed to simplex, and simplex completes the optimization...

Iteration    Objective       Primal Inf.    Dual Inf.      Time
    1680    1.1266350e+07   2.038235e-03   0.000000e+00      3s
    1889    1.1266393e+07   0.000000e+00   0.000000e+00      3s

The five columns in each output row of the simplex log show the number of simplex iterations performed to that point in the crossover algorithm (including the push steps), the objective value for the current basis, the magnitude of the primal infeasibility for the current basis (computed as the sum of the absolute values of all constraint and bound violations), the magnitude of the dual infeasibility (computed as the sum of the absolute values of all dual constraint violations), and the amount of time expended by the crossover algorithm to that point (measured using wall clock time). When the primal and dual infeasibilities both reach zero, the basis is optimal and optimization is complete.

Summary Section

The final section of the barrier log provides summary information. It provides a summary of the work that the barrier algorithm performed, including the iteration count and the runtime, and it provides information on outcome of the optimization. The summary for a model that is solved to optimality would look like this:

Solved in 1889 iterations and 3.10 seconds
Optimal objective  1.126639304e+07

Other termination states produce different summaries. For example, a user interrupt would produce a summary that looks like:

Stopped in 7482 iterations and 3.41 seconds
Solve interrupted

Hitting a time limit would produce a summary that looks like:

Stopped in 9221 iterations and 5.00 seconds
Time limit exceeded