Try our new documentation site (beta).
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 2349 rows and 3378 columns Presolve time: 0.04s Presolved: 3722 rows, 8852 columns, 30908 nonzerosThe example output shows that presolve was able to remove 2349 rows and 3378 columns, and it required 0.04 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 lower 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.657e+04 Factor NZ : 8.450e+05 (roughly 12 MBytes of memory) Factor Ops : 3.944e+08 (less than 1 second per iteration) Threads : 8The First 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 next 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.
The final line shows the number of threads that will be used to perform the barrier iterations.
You may sometimes see two other lines in this section:
Dense cols : 3 Free vars : 20The first indicates how many columns from the constraint matrix were treated as dense. The second 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 useful to know when they are present.
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.47340463e+12 -1.05838204e+09 1.49e+04 2.46e+02 1.94e+09 0s
1 6.13234163e+11 -3.97417254e+10 5.97e+03 5.98e+06 8.82e+08 0s
2 2.89634303e+11 -9.20268188e+10 2.54e+03 2.24e+06 3.81e+08 0s
3 6.57753936e+10 -9.40746258e+10 2.39e+02 2.87e+05 5.17e+07 0s
4 2.44710457e+10 -2.59852944e+10 3.16e+01 3.01e+04 9.00e+06 0s
5 6.74069830e+09 -1.78169224e+10 4.01e+00 2.01e+04 3.17e+06 0s
6 1.93163205e+09 -3.10778084e+09 2.46e-01 3.13e+03 5.62e+05 0s
7 6.54973737e+08 -6.89946649e+08 4.40e-02 5.35e+02 1.47e+05 0s
8 2.44764500e+08 -3.47987016e+08 1.47e-02 4.02e+02 6.46e+04 0s
9 1.35906001e+08 -1.41063037e+08 7.16e-03 1.66e+02 3.01e+04 0s
10 9.29132721e+07 -6.69973369e+07 4.58e-03 7.60e+01 1.73e+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 0sThis 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...
1610 DPushes remaining with DInf 0.0000000e+00 1s
0 DPushes remaining with DInf 0.0000000e+00 1s
144 PPushes remaining with PInf 5.7124800e-03 1s
0 PPushes remaining with PInf 5.7124800e-03 1s
Push phase complete: Pinf 5.7124800e-03, Dinf 8.1488315e-07 1s
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
1700 1.1266352e+07 5.712480e-03 0.000000e+00 1s
1868 1.1266393e+07 0.000000e+00 0.000000e+00 1s
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 1868 iterations and 1.05 seconds Optimal objective 1.126639304e+07Other 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 interruptedHitting a time limit would produce a summary that looks like:
Stopped in 9221 iterations and 5.00 seconds Time limit exceeded
