Thursday, August 19, 2010

Cplex new version

In some cases a new version of a solver can perform worse on some models. Here is a particular unfortunate example, where Cplex 12.1 finds several very good solutions in the initial heuristics, but Cplex 12.2 just fails to find any integer solutions within the allotted time: 

ILOG CPLEX       Nov  1, 2009 23.3.3 WEX 13908.15043 WEI x86_64/MS Windows
Cplex 12.1.0, GAMS Link 34
Cplex licensed for 1 use of parallel lp, qp, mip and barrier.

Cplex MIP uses 1 of 4 parallel threads. Change default with option THREADS.
Reading data...
Starting Cplex.…

Root relaxation solution time =  102.77 sec.

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap

      0     0    15053.5468   150                  15053.5468   151633        
*     0+    0                       150008.6529    15053.5468   151633   89.96%
      0     0    15065.0166   146   150008.6529     Cuts: 479   158521   89.96%
*     0+    0                        15387.9888    15065.0166   158521    2.10%
      0     0    15065.1974   152    15387.9888 Flowcuts: 146   159618    2.10%
      0     0    15065.2096   146    15387.9888      Cuts: 70   159894    2.10%
      0     0    15065.2104   146    15387.9888   Flowcuts: 9   159952    2.10%
*     0+    0                        15175.4264    15065.2104   159952    0.73%

Flow cuts applied:  472
Mixed integer rounding cuts applied:  4
Gomory fractional cuts applied:  7
MIP status(102): integer optimal, tolerance

 

IBM ILOG CPLEX   Jul  4, 2010 23.5.1 WEX 18414.18495 WEI x86_64/MS Windows
Cplex 12.2.0.0, GAMS Link 34
GAMS/Cplex licensed for continuous and discrete problems.

Cplex MIP uses 1 of 4 parallel threads. Change default with option THREADS.
Reading data...
Starting Cplex...

Root relaxation solution time =  107.14 sec.

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap

      0     0    15053.5468   111                  15053.5468   120941        
      0     0    15066.3609   105                   Cuts: 787   126925        
      0     0    15067.4221    99                     Cuts: 7   127524        
      0     0    15067.4512   100                     Cuts: 8   127557        
      0     0    15067.4512   100                  MIRcuts: 2   127559        
Heuristic still looking.
Heuristic still looking.
      0     2    15067.4512   100                  15067.4561   127559        
Elapsed real time = 237.15 sec. (tree size =  0.00 MB, solutions = 0)
      1     3    15072.3309    97                  15067.4561   131486        
      2     4    15068.7687    75                  15068.8163   134032        
      3     5    15069.6752    84                  15068.8163   134657        
      4     6    15071.3502    88                  15069.6828   135922        
      5     7    15072.3709    75                  15069.6828   136786        
      6     8    15086.2295    77                  15069.6828   145563        
      7     9    15072.9117    71                  15069.6828   146885        
      8    10    15073.9185    79                  15069.6828   148355        
      9    11    15081.7555    70                  15069.6828   154282        
     12    14    15074.6296    72                  15069.6828   154696        
Elapsed real time = 314.54 sec. (tree size =  2.27 MB, solutions = 0)
     13    15    15088.4559    66                  15069.6828   159070        

MIP status(108): time limit exceeded, no integer solution
CPLEX Error  1217: No solution exists.
Resource limit exceeded, no integer solution found.

Such behavior is always difficult to explain to a customer. The argument that on average a new version tends to do better is of little consolation.

PS. The time limit was very tight on this model: 400 seconds (extremely tight considering the LP takes 100 seconds). This was no problem with previous versions of Cplex as the initial heuristic always found solutions very quickly. These solutions were so good they already obeyed the requested gap of 0.8%. Cplex 12.2 finds the solution relatively quickly in the B&B after about 500 seconds on my machine with 1 thread (the client on his machine obtained no solution in 600 seconds with 2 threads and some other solver options; I assume a little bit more time may help here).

PS2. All my runs were with default settings (except 1 thread, gap=0.8%, time limit=400 seconds).

3 comments:

  1. I have struggled with many of such customer arguments. But I think it's an unreasonable demand, that performance should not degrade on any model. It is simply completely impossible. I know cplex takes benchmarking very seriously. I have been to an benchmark talk by Tobias Achterberg from cplex, they have a *huge* collection of customer test models, that must take ages to run.

    ReplyDelete
  2. Is the time limit for the second run the same as the total solution time for the first run? It seems 12.2 got a slightly tighter lower bound than 12.1 did, but that's not very meaningful if it took longer to do.

    Presumably you kept any non-default parameter values the same across both runs. I wonder if any defaults changed in 12.2?

    ReplyDelete
  3. I agree with Bo; if you come up with an improvement that works on 95% of your customer models, you will hear primarily from those 5% of customers who don't see any improvement (or perhaps see a decline) in performance. But, you still should go ahead and implement the feature.
    For MIPs, the growth in heuristics has a tendency to increase the performance variability. In the log files above, all the feasible solutions came from heuristics.

    One useful test to distinguish cases of performance variability from cases where one version really does better involves solving the root algorithm differently. By solving the initial relaxation with primal simplex or barrier method, you typically get a different starting basis, different cuts, and different heuristic behavior. So, for the model above, if you see consistent results even after changing the root node LP solve in this way, that suggests that 12.1 really does better on this model. On the other hand, if you see wild variations in performance by doing this, that suggests that the model has a lot of performance variability, and that care must be taken drawing conclusions from a single comparison.

    In general, when I see a log like the one above, I would recommend increasing CPLEX's heuristic frequency parameter, to something like 5 nodes. Increased heuristic application will tend to reduce any variability associated with heuristics. Also, any settings that can tighten the root node (e.g. more aggressive probing and cuts) might yield more consistent results by reducing the number of integer infeasibilities.

    If you are welling to send us the model (klotz at us dot ibm dot com), we'll see what we can do with 12.2.

    ReplyDelete