Sifting Logging

Sifting will sometimes be used within the dual simplex method, either as a result of an automatic choice by the Gurobi Optimizer or because the user selected it through the Sifting parameter. The sifting log consists of three sections: the presolve section, the sifting progress section, and the summary section. The first and last are identical to those for simplex, so we’ll only discuss the middle section here.

Sifting Progress Section

As we mentioned, output for sifting and dual simplex are indistinguishable until the progress section begins. For sifting, the progress section begins with a clear indication that sifting has been selected:

Starting sifting (using dual simplex for sub-problems)...

The sifting algorithm performs a number of major iterations, where each iteration solves a smaller LP sub-problem. It uses the result to update the current primal and dual solution. The sifting log prints one line per major iteration, with information on the current primal and dual objective values:

Iter     Pivots    Primal Obj      Dual Obj        Time
   0          0     infinity      2.0000000e+01     11s
   1       4662   1.5220652e+03   2.7034420e+02     12s
   2       8917   1.3127217e+03   4.6530259e+02     13s
   3      16601   1.1651147e+03   6.4767742e+02     17s
   4      30060   1.0881514e+03   7.8842688e+02     29s
   5      45169   1.0618879e+03   8.8656855e+02     46s
   6      59566   1.0549766e+03   9.5404159e+02     64s
   7      73614   1.0540577e+03   1.0172213e+03     82s

The first column in the log gives the major iteration number. The second shows the total number of simplex iterations performed in solving the sifting sub-problems. The third and fourth columns show the primal and dual objective values for the current solution. The final column shows elapsed runtime.

The completion of sifting is indicated with the following message:

Sifting complete

The basis computed by sifting is then handed back to dual simplex, and the log from that point forward comes from the dual simplex algorithm.