LKH 3.0.6 ignores TIME_LIMIT-parameter

[thoklei]

Hi, I realize that you only mirror Helsgaun's LKH here, but maybe you do now how to get around the issue I'm experiencing: I thought I could set a maximum time limit on the execution time of the program by starting it with a TIME_LIMIT-parameter, but it doesn't seem to make any difference: LKH runs way longer than the specified time limit on the (not that large) instance I'm trying to solve.

This is my .par-file:

PROBLEM_FILE = brd14051.tsp RUNS = 1 TIME_LIMIT = 60 TRACE_LEVEL = 3

The problem is a known literature instance (not written by me, but downloaded from here: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/), so I doubt that anything is wrong with it, and I'm also experiencing this issue with other instances of similar size. This is what brd14051.tsp looks like:

NAME : brd14051 COMMENT : BR Deutschland in den Grenzen von 1989 (Bachem/Wottawa) TYPE : TSP DIMENSION : 14051 EDGE_WEIGHT_TYPE : EUC_2D NODE_COORD_SECTION 1 2918 6528 2 2925 6597 3 2926 6609 4 2927 6312 ...

I can solve this instance with Concorde in about 12 seconds and get to a score of 470.202, but LKH just doesn't stop, the longest I have left it running for is about 15 minutes. It keeps giving me output like:

... T = 1600, Period = 7025, P = 1243, W = 393135.4, Norm = 15936 T = 1600, Period = 7025, P = 1244, W = 392214.0, Norm = 15904 T = 1600, Period = 7025, P = 1245, W = 394036.2, Norm = 15846 T = 1600, Period = 7025, P = 1246, W = 393741.0, Norm = 15684 T = 1600, Period = 7025, P = 1247, W = 393099.4, Norm = 16008 T = 1600, Period = 7025, P = 1248, W = 394319.6, Norm = 15716 T = 1600, Period = 7025, P = 1249, W = 394055.8, Norm = 16000 T = 1600, Period = 7025, P = 1250, W = 393827.0, Norm = 15808 ...

Do you know how I can force LKH to terminate after x seconds and give me the best solution it has found so far? Thank you very much in advance!

[cerebis]

The documentation doesn't make it clear, but what you're seeing is subgradient optimisation. Which comes after the initial tour determination. If you disable that, you will get much faster execution, but obviously less optimal results.

SUBGRADIENT = NO

From the header

/* 
 * The Ascent function computes a lower bound on the optimal tour length 
 * using subgradient optimization. The function also transforms the original 
 * problem into a problem in which the Alpha-values reflect the likelihood 
 * of edges being optimal.
 *
 * The function attempts to find penalties (Pi-values) that maximizes the 
 * lower bound L(T(Pi)) - 2*PiSum, where L(T(Pi)) denotes the length of the 
 * minimum spanning 1-tree computed from the transformed distances, and PiSum 
 * denotes the sum of Pi-values. If C(i,j) denotes the length of an edge 
 * (i,j), then the transformed distance D(i,j) of an edge is 
 * C(i,j) + Pi(i) + Pi(j).
 *
 * The Minimum1TreeCost function is used to compute the cost of a minimum 
 * 1-tree.The Generatecandidates function is called in order to generate 
 * candidate sets. Minimum 1-trees are then computed in the corresponding 
 * sparse graph.         
 */

[cerebis]

Running your parameter file on that example data, without setting a seed, I get a score for 476649 with a 60s time limit.

[thoklei]

Thank you very much! I had thought that the time-limit-parameter referred to the total execution time of the whole program, but it apparently only "starts counting the seconds" once the initial period is over. I will close this issue now, as my question is completely answered :)