Solving TSPLIB Instances
The file tspSolver/src/main/Main.java contains code that will run your solver on instances from the TSPLIB database. The main method of this class begins with
public static void main(String[] args) { String[] problemNames = new String[]{"bier127","eil51","brd14051","ch130","ch150","d198", "d493","d657", "d1291","fl1400"}; String problemName = problemNames[1]; //...
Here the elements of problemNames
are files in the directory sampleData/TSPLIB/ that existing code will parse for you into a problem instance. The number in the file name refers to the number of cities in the problem. You can adjust which problem is attempted by assigning a different value to problemName
(by changing the index used to access problemNames
, or if you prefer, typing in a file name manually). Try running your solver on a few different instances (start with smaller ones).
Problem Name |
eil51 |
bier127 |
ch130 |
ch150 |
d198 |
---|---|---|---|---|---|
Run time |
0.11 |
0.77 |
1.98 |
5.09 |
17.57 |
Performance degrades pretty quickly on larger problems. On my machine, d493 took over 5000 seconds to solve, and created over 250,000 nodes in branch and bound!
Interpreting CPLEX Output
When running the solver, the output generated by CPLEX is directed is printed out to the console. A complete explanation of what all of the output means can be found in the user manual here. We will explain the output as needed to motivate improvements to our TSP solver. Here is some sample output from d493.
374553 50385 cutoff 35002.0000 34998.0000 1922800 0.01% x180185 D 374553 374551 47 375000 50465 34998.5000 66 35002.0000 34998.0000 1924163 0.01% x121871 U 375000 374999 15 375404 50195 cutoff 35002.0000 34998.0000 1925424 0.01% x230899 U 375404 375402 34 375787 49842 cutoff 35002.0000 34998.0833 1926461 0.01% x41269 U 375787 165893 23 376158 49688 35000.0000 14 35002.0000 34998.2500 1927532 0.01% x11502 U 376158 376157 49 376558 49350 cutoff 35002.0000 34998.2500 1928948 0.01% x230899 D 376558 376557 31 Elapsed time = 6732.91 sec. (12435290.54 ticks, tree = 2690.91 MB, solutions = 15) Nodefile size = 2560.74 MB (1100.24 MB after compression) 376932 49032 34998.5000 64 35002.0000 34998.3333 1930143 0.01% x102312 N 376932 161414 29 Cover cuts applied: 6 Zero-half cuts applied: 89 User cuts applied: 742 Root node processing (before b&c): Real time = 13.13 sec. (11373.68 ticks) Sequential b&c: Real time = 6735.83 sec. (12525783.50 ticks) ------------ Total (root+branch&cut) = 6748.96 sec. (12537157.18 ticks) complete! opt is: 35002.0