Problem 1
Download the RTD data sets ‘ils-lin318-opt-rtd.dat’ and ‘mmas-lin318-opt-rtd.dat’ from the course home page and perform the following analysis using R (http://www.r-project.org/) and/or Gnuplot (http://www.gnuplot.info/). The second column in each of the two data sets represents the CPU times measured in multiple independent runs of two different algorithms (ILS and MMAS) applied to the same instance of the Travelling Salesperson Problem.
(a) Plot the two RTD graphs and briefly discuss the differences in performance between the two algorithms seen from the RTD plots.
(b) Report the median run-time for both RTDs and analyse the statistical significance of the observed valus using an appropriate statistical test. Briefly explain your solution.
(c) Apply an appropriate statistical test to investigate whether the two empirical RTDs are different (the answer is obvious from part (a), but here you should verify this formally using the correct test). Briefly explain your solution.
(d) Discuss whether either of two RTDs shows evidence for stagnation of the respective algorithm and if so, sketch the RTD that would be obtained when using the respective algorithm with an optimal static restart strategy.
(e) Imagine you had a larger collection of TSP instances, and you wanted to compare the performance of ILS and MMAS on across the entire collection. Describe briefly and precisely how you would carry out this analysis and, considering your findings from parts (a) and (d), what you would be looking for.
With your answers, submit all Gnuplot and/or R scripts you have been using for your analysis.
Problem 2
Download the run-time data set 'tsp-scaling-1.dat' from the course home page. The first column in this file represents instance sizes (of TSP instances), the second mean run-times for the TSP algorithm Concorde on sets of those instances in CPU seconds. (When run to completion, Concorde finds provably optimal solutions to any given TSP instance.)
(a) Use various graphical representations of the scaling curve to investigate whether the scaling behaviour seen in this data is polynomial or exponential.
(b) Determine a best-fit polynomial and exponential model for a suitably chosen subset of this data and challenge your models by extrapolation.
Now, download the run-time data sets 'tsp-scaling-2.zip' from the course home page. Each file 'results-k-ttime.dat' contains run-time results for Concorde on a set of TSP instances of size k. Each line of those files contains results for one particular instance, where column 1 is the instance name and column 3 the run-time of Concorde on that instance. (You can ignore all other columns.)
(c) Plot the SCDs for two different instances sizes. What do you observe?
(d) Implement the bootstrapping technique introduced by Hoos & Stuetzle (see reading assignment for thu, 01/28) and use it to obtain percentile confidence intervals for instances sizes 1000 and 1500, based on automatically fitted exponential models on the smaller instance sizes. Determine where the observed mean run-times for sizes 1000 and 1500 lie with respect to these confidence intervals and describe what this means. Create a plot showing five of the models obtained from the bootstrapping approach as well as the mean run-times over the complete instance for each problem size.
With your answers, submit all Gnuplot and/or R scripts you have been using for your analysis, as well as all data files.