You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 14 Next »

The root page 15DOTs60ia13:Tutorial could not be found in space 15.S60 SSIM: Software Tools for Operations Research.

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).

Unknown macro: {chart}

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
  • No labels