Branch and bound output

 Top  Previous  Next

When the model secur.gms was solved with an earlier version of CPLEX it yielded output like the following

 

        Nodes                                         Cuts/

   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap

      0     0   2.2303e+007    24                 2.2303e+007        0

    100    93   2.2303e+007     1                 2.2303e+007       53

    200   193   2.2303e+007     1                 2.2303e+007       53

*   280+  266   2.2303e+007     0   2.2303e+007   2.2303e+007       53    0.00%

    300   270   2.2303e+007     1   2.2303e+007   2.2303e+007       53    0.00%

*   390    65   2.2303e+007     0   2.2303e+007   2.2303e+007      104    0.00%

Fixing integer variables, and solving final LP..

MIP Solution  :     22303062.100023    (104 iterations, 391 nodes)

Final LP      :     22303062.100023    (0 iterations)

Best integer solution possible :    22303113.765793

Absolute gap          :            51.6658

Relative gap          :       2.31653e-006

 

This output will differ across solvers but generally contains the same types of information showing the branch and bound approach in action.  Namely the columns by label are

•Node is number of branch and bound problems examined so far.
•Nodes left is number of problems created during the branching process that are yet to be examined.
•IInf tells number of integer variables with non-integer solution levels.
•Objective gives the current objective function value.
•Best node gives the current lower bound on the solution.  Similarly the column
•Best integer gives the incumbent solution.  Note the last solution in that column is not necessarily global best.
•Gap gives max percentage difference from theoretical optimum.

Here we see, no solution is found for a while (indicated by blank entry in Best Integer until iteration 280), then one found and another.  This shows the common phenomena that MIP solves usually end with a gap between the solution found and the best possible.  This is controlled by iteration limits, resource limits, solver options, and model attributes like optcr/optca.