PDHG Logging

The Primal-Dual Hybrid Gradient (PDHG) algorithm log can be divided into four sections: the presolve section, the PDHG progress section, the crossover progress section, and the summary section. Additional information is printed when trying to run PDHG on a GPU.

Presolve Section

As for simplex and barrier, 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 pilot:

Presolve removed 321 rows and 656 columns
Presolve time: 0.01s
Presolved: 1120 rows, 2996 columns, 38698 nonzeros

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

Progress Section

The second section of the Gurobi PDHG output provides information on the progress of PDHG:

                     Objective                Residual
   Iter       Primal          Dual         Primal    Dual     Compl    Time
      0  -4.14122110e+02 -2.76067798e+05  1.34e+03 1.05e-01  2.86e+02    0s
 197116  -5.57983950e+02 -5.57680626e+02  2.85e-02 7.79e-05  3.02e-02    5s
 394516  -5.57993772e+02 -5.57813175e+02  2.22e-01 8.60e-08  4.49e-04   10s
 592316  -5.57814178e+02 -5.57812868e+02  1.02e-02 5.37e-07  7.33e-06   15s
 790416  -5.57814784e+02 -5.57812773e+02  1.02e-02 5.37e-07  5.60e-06   20s
 987916  -5.57815895e+02 -5.57803091e+02  2.36e-03 2.27e-04  1.38e-02   25s
1185116  -5.57815789e+02 -5.57776731e+02  2.36e-03 2.27e-04  2.42e-03   30s
1382516  -5.57815771e+02 -5.57750144e+02  2.36e-03 2.27e-04  1.02e-03   35s
1579916  -5.57479676e+02 -5.58060805e+02  3.75e-05 1.44e-03  2.67e-01   40s
1777316  -5.57435355e+02 -5.57585771e+02  1.37e-04 1.98e-04  9.93e-02   45s
1975016  -5.57422281e+02 -5.57517874e+02  3.36e-05 1.98e-04  1.03e-01   50s
2172416  -5.57419867e+02 -5.57486841e+02  5.39e-05 2.05e-04  5.08e-02   55s
2369916  -5.57476612e+02 -5.57464485e+02  6.85e-05 1.26e-04  3.24e-02   60s
2567616  -5.57502571e+02 -5.57460012e+02  6.78e-05 1.19e-04  2.09e-02   65s
2765116  -5.57496271e+02 -5.57483682e+02  3.68e-05 3.63e-05  3.76e-03   70s
2962816  -5.57488534e+02 -5.57481222e+02  4.12e-07 2.25e-05  3.48e-03   75s

The seven columns in each output row are similar to the output of the barrier algorithm. They show the number of PDHG iterations performed to that point, the primal and dual objective values for the current PDHG 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 PDHG convergence tolerances (controlled using the PDHGAbsTol and PDHGRelTol parameters for primal and dual infeasibility and the PDHGConvTol parameter for the complementarity violation), the solution is declared optimal and optimization is complete.

Just like the simplex and MIP optimizers, by default, PDHG produces a log line every 5 seconds. The frequency of log lines can be changed by modifying the DisplayInterval parameter.

Note

If PDHG concurrent crossover is enabled, PDHG might continue running past the point where its iterate satisfies PDHG’s termination criteria for the first time, see PDHGEarlyCrossover.

Crossover Section

The third section of the PDHG output provides information on crossover. Crossover converts the primal-dual solution produced by the PDHG algorithm to a basic solution.

By default, PDHG uses concurrent crossover (refer to PDHGEarlyCrossover). Here, a subset of the available threads is allocated to PDHG crossover as shown in the line:

Start PDHG using 12 threads with up to 4 threads for concurrent crossover

printed between the presolve and progress sections.

Should a concurrent crossover thread solve the problem while PDHG is still running, the PDHG run is interrupted and the status of the first-to-finish or ‘winning’ crossover thread is printed.

   196916  -5.57984216e+02 -5.57680671e+02  2.85e-02 7.79e-05  2.99e-02    5s
   232616  -5.57788305e+02 -5.57691499e+02  4.90e-03 7.31e-05  5.15e-03    6s
Crossover completed on thread 0 after 232616 PDHG iterations

PDHG with crossover solved model in 232616 iterations and 5.98 seconds (9.65 work units)
Optimal objective -5.57489561e+02

Iteration    Objective       Primal Inf.    Dual Inf.      Time
     421   -5.5748956e+02   0.000000e+00   0.000000e+00      6s

Solved in 421 iterations and 5.98 seconds (9.65 work units)

In the log above, crossover thread 0, started while PDHG was still running, solved the LP problem to optimality and PDHG was aborted after 232616 iterations. After general optimization statistics containing iterations, time/work spent, and the optimal objective, crossover statistics of the winning thread are printed.

These statistics are similar to the ones printed after barrier’s crossover and show iterations needed for crossover, the objective, primal and dual infeasibilities, and total optimization time. The winning crossover thread took 421 iterations and finished with objective -5.5748956e+02, its final iterate containing no primal and dual infeasibilities. Crossover finished after 5.98 seconds or 9.65 work units.

If no concurrent crossover thread solves the problem before PDHG finishes or if concurrent crossover is disabled but crossover is enabled, crossover output similar to barrier’s crossover output is emitted after the PDHG progress section.

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...

     215 DPushes remaining with DInf 0.0000000e+00               138s
       0 DPushes remaining with DInf 0.0000000e+00               138s

      45 PPushes remaining with PInf 8.3028686e-04               138s
       0 PPushes remaining with PInf 1.5488405e-06               138s

  Push phase complete: Pinf 1.5488405e-06, Dinf 9.8028841e-13    138s

Iteration    Objective       Primal Inf.    Dual Inf.      Time
     263   -5.5748973e+02   1.548840e-06   0.000000e+00    138s
Crossover time: 0.05 seconds (0.03 work units)
     264   -5.5748973e+02   0.000000e+00   0.000000e+00    138s

Each line indicates how many push steps remain, the amount of infeasibility in the current solution, and the elapsed crossover 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.

If LP symmetry was detected during model presolve, another round of crossover needs to be performed in order to uncrush the solution of the problem after symmetry removal back into the original problem space. The output is similar to the crossover plus (potentially) simplex output during the first crossover step.

Use crossover to convert LP symmetric solution to basic solution...
Crossover log...

   78601 variables added to crossover basis                      345s

     657 DPushes remaining with DInf 0.0000000e+00               346s
       0 DPushes remaining with DInf 0.0000000e+00               350s

      49 PPushes remaining with PInf 0.0000000e+00               350s
       0 PPushes remaining with PInf 2.8123455e-06               351s

  Push phase complete: Pinf 2.8123455e-06, Dinf 3.8147841e+00    351s

Iteration    Objective       Primal Inf.    Dual Inf.      Time
     891    6.1032411e+01   0.000000e+00   3.814784e+00    351s
    1330   -7.0120988e+02   9.111124e+06   0.000000e+00    361s
    1751    5.7274398e+01   1.038075e+02   0.000000e+00    369s
    2174    5.9850895e+01   2.192146e+07   0.000000e+00    375s
    2606    6.0664791e+01   2.234433e+07   0.000000e+00    380s
    3032    6.1024074e+01   5.992409e+00   0.000000e+00    387s
Crossover time: 50.24 seconds (98.31 work units)
    3309    6.1032412e+01   0.000000e+00   0.000000e+00    395s

In the above example, crossover produces a non-optimal solution after uncrushing. This is passed on to the simplex algorithm, which then proceeds to find an optimal solution of the uncrushed problem.

Summary Section

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

Solved in 90 iterations and 0.91 seconds (1.31 work units)
Optimal objective -2.581139261e+03

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

GPU-Related Output

Note

GPU support requires downloading a separate build. See Gurobi Downloads.

Whether or not PDHG is run on a GPU is controlled by PDHGGPU. If PDHG is executed on a GPU, the log line indicating whether or not concurrent crossover has been used for PDHG is modified and becomes:

Start PDHG on GPU with up to 8 threads for concurrent crossover

If PDHGGPU is set but a GPU is not detected, the logging output changes to:

GPU not found - running on CPU instead
Start PDHG using 1 threads with up to 4 threads for concurrent crossover

If an executable without GPU support is used, the log changes to:

Not a GPU build - running on CPU instead
Start PDHG using 1 threads with up to 4 threads for concurrent crossover