Thursday, June 30, 2011

Cplex polishing

For some difficult large models, the Polishing facility in Cplex can sometimes do extremely well. This is an example:

Elapsed real time = 874.90 sec. (tree size = 11.31 MB, solutions = 2)
    233   235     -158.9737  3551      621.0895     -159.3086   258914  125.65%
    234   236     -158.9448  3578      621.0895     -159.3086   258964  125.65%
    266   268     -158.9498  3578      621.0895     -159.3086   265158  125.65%
    306   308     -158.9338  3568      621.0895     -159.3086   271534  125.65%
    310   312     -158.9315  3511      621.0895     -159.3086   272354  125.65%
    312   314     -158.9489  3581      621.0895     -159.3086   272367  125.65%
    322   324     -158.9310  3574      621.0895     -159.3086   273646  125.65%
    346   348     -158.8857  3561      621.0895     -159.3086   277217  125.65%
    354   356     -158.8368  3532      621.0895     -159.3086   278697  125.65%
    370   372     -158.8741  3567      621.0895     -159.3086   281105  125.65%
Elapsed real time = 995.15 sec. (tree size = 49.71 MB, solutions = 2)

Starting condition for polishing reached (PolishAfterTime).
Starting solution polishing.

*   390+  390                          360.3876     -159.3086   285698  144.20%
*   390+  390                          231.7287     -159.3086   285698  168.75%
*   390+  390                          100.2251     -159.3086   285698  258.95%
    390   392     -158.8957  3503      100.2251     -159.3086   285698  258.95%
    391   393     -158.9880  3601      100.2251     -159.3086   286729  258.95%
    392   394     -158.9935  3613      100.2251     -159.3086   286790  258.95%
    393   395     -158.9735  3574      100.2251     -159.3086   287216  258.95%
    394   396     -158.9763  3595      100.2251     -159.3086   287247  258.95%
    395   397     -158.9980  3601      100.2251     -159.3086   287328  258.95%
    396   398     -158.9806  3600      100.2251     -159.3086   287599  258.95%
    397   399     -159.0641  3615      100.2251     -159.3086   296751  258.95%

GUB cover cuts applied:  854
Clique cuts applied:  14
Cover cuts applied:  1540
Implied bound cuts applied:  20
Flow cuts applied:  922
Mixed integer rounding cuts applied:  67
Zero-half cuts applied:  1169
Gomory fractional cuts applied:  236

Root node processing (before b&c):
  Real time             =  127.44
Parallel b&c, 8 threads:
  Real time             = 7070.70
  Sync time (average)   =  168.52
  Wait time (average)   =    0.00
                          -------
Total (root+branch&cut) = 7198.14 sec.
MIP status(107): time limit exceeded

Although the relative gap looks bad, this is in fact a very good solution. The reason for the gap problem is that we are relatively close to zero in our objective (compared to solutions found by heuristics) and the fact that we are crossing zero in the gap calculation does not help.