This readme.txt file was generated on 20220221 by Stefan Klootwijk ------------------- GENERAL INFORMATION ------------------- Title of Dataset: FRaMeS_20220221_Numerical_Analysis_of_2-OPT_for_TSP_on_RSPM Author Information Principal Investigator: Stefan Klootwijk, Mathematics of Operations Research Group (DMMP), Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, P.O. Box 217, 7500 AE Enschede, s.klootwijk@alumnus.utwente.nl Associate or Co-investigator: Bodo Manthey, Mathematics of Operations Research Group (DMMP), Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, P.O. Box 217, 7500 AE Enschede, b.manthey@utwente.nl Date of data collection: 2017-2021 This dataset contains data generated as part of Stefan Klootwijk's PhD Thesis Project (November 2021): doi:10.3990/1.9789036552493 This research was supported by NWO grant 613.001.402. ------------------------------------------------- DATA & FILE OVERVIEW & METHODOLOGICAL INFORMATION ------------------------------------------------- This dataset contains the following files: Problem instances/Database n=X, m=Y.mat Scripts for instance generation/ComputeRoutes.m Scripts for instance generation/GenerateDatabase.m Scripts for instance generation/GenerateInstance.m Scripts for problem solving/2-OPTforTSP1.ams Scripts for problem solving/OPTforTSP1.ams Data_TSP_2OPT.csv README.txt The folder 'Problem instances' contains 27 Matlab MAT-files, each one containing m=Y Random Shortest Path Metrics generated from a complete graph on n=X vertices. These files have been generated using the Matlab .m-functionscripts in the folder 'Scripts for instance generation' using MATLAB R2015b. On (a part of) these instances we solved two mixed integer linear programs using the AIMMS software and CPLEX solver (most experiments where done using AIMMS 4.30.5.814 (x64), some experiments used a later version of AIMMS): one to find the optimal solution to the traveling salesman problem ('OPTforTSP1.ams') and another one to find the worst 2-optimal solution for the traveling salesman problem ('2-OPTforTSP1.ams'). These can be found in the folder 'Scripts for problem solving'. These models are strongly based on the How-To Example "Routing: Traveling Salesman Problem" as published by AIMMS on their website. The results have been gathered in the file 'Data_TSP-2OPT.csv'. -------------------------- DATA-SPECIFIC INFORMATION -------------------------- The data included in this data set has been organised based on the size of the (complete) graph used for generating the random shortest path instances. The problem instance files are named 'Database n=X, m=Y.mat' where X denotes the number of vertices in the complete graph, and Y denotes the number of instances in the data set. Each Matlab MAT-file contains 5 variables: d and w are X x X x Y matrices containing for each instance all distances and edge weights, respectively. The variables p, edges and route contain information needed to be able to retrieve the actual shortest paths between each pair of vertices (w.r.t the edge weights). More details can be found in the Matlab functionscripts in the folder 'Scripts for instance generation'. NB: The AIMMS models only use the data that is contained in the variable w (and calculate the distances themselves). -------------------------- DATA-SPECIFIC INFORMATION -------------------------- The file Data_TSP-2OPT.csv contains 31 columns and 20006 rows. The first column indicates the contents of each row as follows: row1: Type: either 'OPT' (optimal TSP solution), 'WLO' (worst 2-optimal TSP solution), or 'ratio' (WLO/OPT) row2: n: number of vertices in the complete graph used to generate the random shortest path metrics. row3: m: number of instances used (for the given value of n). row4: Average row5: 95% Confidence Interval (lower bound) row6: 95% Confidence Interval (upper bound) rows7-20006: Instance X: the result (OPT, WLO or ratio) of instance X (empty when X > m).