## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### Bbmc
#### 2.4.1 BBMC in Java
Referring back to Table 7 we expect a Cyprus/Fais ratio of 0.41 but empirically get 0.12 when using MCSa1 and 0.14 when using BBMC1. We expect a Cyprus/Daleview ratio of 0.50 but empirically get an average 0.26 with MCSa1 and 0.10 with BBMC1. The conversion factors in Table 7 consistently overestimate the speed of Fais and Daleview. For example, we would expect MCSa1 applied to brock200-1 on Fais to have a run time of \(19,343\times 0.41=7,930\) milliseconds on Cyprus. In fact it takes 4,777 milliseconds. If we use the derived ratio in the last row of Table 8 we get \(19,343\times 0.12=2,321\) milliseconds. As another example, consider san1000 using BBMC1 on Daleview. We would expect this to take \(54,816\times 0.50=27,408\) milliseconds on Cyprus. In fact it takes 5,927 milliseconds! If we use the conversion ratio from the last row of Table 8, we get a more accurate estimate \(54,816\times 0.10=5,481\) milliseconds. But maybe this is because we have used a C program (dfmax) to calibrate a Java program. Would we get a reliable calibration if a C program was used? [PERSON]'s Cliquer program was downloaded and compiled on our three machines and run against DIMACS benchmarks, _i.e._, the experiments in Table 8 were repeated using Cliquer and dfmax with a different, and easier, set of problems. The results are shown in Table 9 were an entry \"--\" was a run of dfmax that was terminated after 2 minutes. What we see is an actual scaling factor of 0.62 for Cliquer on Fais when dfmax predicts 0.41 and for Cliquer on Daleview 0.26 when we expect 0.50; again we see that the rescaling procedure fails. The last three columns show a dfmax calibration using problems other than the r* benchmarks and here we see an error of about 5% on Fais (expected 0.41, actual 0.39) and about 16% on Daleview (expected 0.50,

\begin{table}
\begin{tabular}{|c|c c|c c|c c|c c|c c|} \hline  & \multicolumn{5}{c|}{**MCSa1**} & \multicolumn{5}{c|}{**BSMC1**} \\
**instance** & \multicolumn{2}{c|}{**Fais**} & \multicolumn{2}{c|}{**Daleview**} & \multicolumn{2}{c|}{**Cyprus**} & \multicolumn{2}{c|}{**Fais**} & \multicolumn{2}{c|}{**Daleview**} & \multicolumn{2}{c|}{**Cyprus**} \\ \hline brock200-1 & 0.25 & (19,343) & 0.27 & (17,486) & 1.00 & (4,777) & 0.15 & (15,3



actual 0.43). Therefore, it appears that rescaling results using dfmax and the five r* benchmarks is not a safe procedure and can result in wrong conclusions being drawn regarding the relative performance of algorithms. ### Relative Algorithmic Performance on Different Machines

But is it even safe to draw conclusions on our algorithms when we base those conclusions on experiments performed on a single machine? Previously, in Table 2 we compared MCSa against BBMC on our reference machine Cyprus and concluded that BBMC was typically twice as fast as MCSa. Will that hold on Fais and on Daleview? Table 10 takes the data from Table 8 and divides the run time of MCSa by BBMC for each instance on our three machines. On Fais BBMC is rarely more than 50% faster than MCSa and on Daleview BBMC is slower than MCSa more often than not! If experiments were performed only on Daleview using only the DIMACS instances, we might draw entirely different conclusions and claim that BBMC is slower than MCSa. This change in relative algorithmic ordering has been observed on five different machines (four using the Java 1.6.0) using all of the algorithms. The -server and -client options were also tried. The -server option sometimes gave speedups of a factor of 2, sometimes a factor of 0.5, and this can also affect relative algorithmic performance. ## 5 Conclusions

We have seen that small implementation details (in MC) can result in large changes in performance. Modern programming languages with rich constructs and large libraries of utilities make it easier for the programmer to do this. We have also drifted away from the days when algorithms were presented along with their implementation code (examples here are [8, 23]) to presenting algorithms only in pseudo-code.