ASCEND OUTPUT 1

Copyright \begin{matrix}c \\ ◯ \end{matrix}1994, 1995, 1996, 1997, 1998 David Neto This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. You may contact David Neto via email at netod@acm.org, or with greater latency at

Department of Computer Science University of Toronto 10 King’s College Rd. Toronto, Ontario M5S 3G4 Canada

Log : ascend.w, v Revision 1.28 1998/07/16 21:58:55 neto Added the LGPL notice in each file. Revision 1.27 1998/05/30 18:51:12 neto Make it stop after 1500 iterations. That’s just enough, ok? Revision 1.26 1998/05/23 19:20:17 neto Implement combination of previous two degree components. Another stopping criterion (stop when close enough to upper bound: 0.1 percent) Clean up output a bit so it is more easily digested by gnuplot Revision 1.25 1998/05/23 18:10:46 neto sqrt in the normalizer is definitely the *wrong* thing! Tightened the t parameter bound to 1e-4 Revision 1.24 1998/05/23 17:50:46 neto Now it compiles and links into lk. Revision 1.23 1998/05/23 16:22:11 neto Added necessary target len. Added access to best lambda. Think about adding convex combination of the last two lambdas. Revision 1.22 1998/05/23 15:22:50 neto normalizer should be Euclidean distance. Revision 1.21 1998/05/23 15:13:21 neto Switch to a fixed distinguished degree 2 node (number n-1). This seems ”more correct”. Also, added much explanatory documentation about Held-Karp lower bounds. This should be the only new module added to LK. Revision 1.20 1998/05/22 20:38:10 neto Fixed a 1-tree length accounting bug. Oops. Better comments, and removed pageno. Revision 1.19 1998/05/22 20:21:21 neto This might be completely switched over to the simpler non branch and buond scheme. Now I’ll read the code again... Revision 1.18 1998/05/22 18:18:53 neto Removed more stuff not appropriate to pure Held-Karp lower bounds. Revision 1.17 1998/05/22 17:59:00 neto Got rid of double-including of headers... Got rid of bbnode search tree stuff Use efficient multiple buffering of lambda vectors. Revision 1.16 1998/05/21 19:29:35 neto Fixed up standard CWEB thingies and Log stuff. Revision 1.15 1998/05/21 19:25:34 neto More restructuring and comments. Include standard CWEB goodies.

§1  ASCEND  HELD-KARP LOWER BOUNDS FOR THE TSP 3

1. Held-Karp lower bounds for the TSP. In The Traveling Salesman Problem and Minimum Spanning Trees, Operations Research, 18, pp. 1138–1162, 1970, Michael Held and Richard Karp described a lower bound for the length of the shortest tour for a given graph.

A 1-tree for graph G on n vertices is a spanning subgraph of G that has n edges. Since all tours of G span G and have as many edges as G has vertices, then all tours are 1-trees. So the weight of a minimum weight 1-tree for G is a lower bound on the length of a shortest tour of G.

Minimum 1-trees are easy to compute. Let us label the vertices of G with numbers 0 through n − 1. We may as well restrict our attention to 1-trees in which vertex n − 1 is of degree 2, since all tours of G also have this property. Then a minimum 1-tree is just a minimum spanning tree over the subgraph induced by vertices 0 through n − 2, together with the two shortest edges incident upon vertex n − 1.

2. Now, the lower bounds one gets with this simple minimum 1-tree scheme are not very good: they underestimate the optimal tour length by about a third. What to do?

Held and Karp describe how to use Lagrange multipliers in this setting. (Go back to your vector calculus text to recall what Lagrange multipliers are in general. I’ll describe them in the particular here.) Instead of computing minimum 1-trees with the basic distance function cost, compute minimum 1-trees with cost function cost_{λ}(i, j) = cost(i, j) + λ_{i} + λ_{j}, where λ is an arbitrary n-dimensional vector over the reals.

How does that help us? For a given graph, let L(λ) be the length of a shortest 1-tree using cost function cost_{λ} and let T (λ) be the length of a shortest tour using the same cost function cost_{λ}. Then for any real vector λ, we have from before that

L(λ) ≤ T (λ).

Now, since each tour is a 1-tree in which each vertex is of degree 2, we have

T (0) = T (λ) − 2 ∑_{i} λ_{i}.

Note that T (0) is just the length of a shortest tour with the original cost function. Substituting for T (λ) in the first equation, we get the inequality

L(λ) − 2 ∑_{i} λ_{i} ≤ T (0).

The Lagrange multipliers have given us an extra n degrees of freedom. The task then becomes finding a λ that makes this inequality as tight as possible. Held and Karp proved that the objective function is convex over the space of possible values for λ, and prove convergence for an iterative ascent algorithm with certain parameters.

The Held-Karp lower bound for the TSP is the 1-tree lower bound with optimal Lagrange multitpliers. Held-Karp lower bounds are very tight, often getting within 0.5% of the length of a shortest tour for the graph.

3. In a second paper, The Traveling Salesman Problem and Minimum Spanning Trees II, Mathematical Programming, 1, pp. 6–25, 1971, Held and Karp described a subgradient optimization method for optimizing the lower bound. That is the algorithm implemented here.

4  SUBGRADIENT OPTIMIZATION  ASCEND §4

4. Subgradient optimization. Held and Karp described a convenient and effective method for approximating the Held-Karp lower bound to the TSP. The algorithm is to refine the λ vector iteratively. Each iteration consists of the following steps: compute a 1-tree with the durrent λ vector, then update λ_{i} if vertex i in the 1-tree is not of degree 2. If the degree of vertex i is 1, then decrease λ_{i}. If the degree of vertex i is greater than 2, then increase λ_{i}.

This update rule has the effect of making well-connected vertices less attractive next time around, and under-connected vertices more attractive. One can think of this as “warping” the local space around each vertex. Rather cool, actually.

5. This iterative algorithm belongs to the class of optimization algorithms known as subgradient optimization. Held and Karp prove that the optimization space explored here is well-behaved (convex). As a consequence, with parameters in the right range, this iterative procedure is guaranteed to converge. (As long as the floating point arithmetic holds out, anyway…)

Of course, we need practicality too. All lower bounds computed by this procedure are valid, and are thus valid approximations to the Held-Karp lower bound. We’ll live with taking the best lower bound we find here and declaring it as “good enough”.

6. The outline of this module is as follows: #include #include

⟨ System headers 7 ⟩

⟨ Module headers 8 ⟩

⟨ Module variables 15 ⟩

⟨ Module prototypes 20 ⟩

⟨ Early module subroutines 46 ⟩

⟨ Module subroutines 19 ⟩

⟨ Subroutines 11 ⟩

7. We need some standard stuff. ⟨ System headers 7 ⟩ ≡ #include #include #include

This code is used in section 6.

8. We need lots of stuff from other header files included with LK. ⟨ Module headers 8 ⟩ ≡ #include #include #include /∗ For cost and tsp instance t. ∗/ #include #include #include

See also section 10. This code is used in section 6.

§9  ASCEND  SUBGRADIENT OPTIMIZATION 5

9. The exported interface is contained in the ascend.h header file, which has the following form. ⟨ 9 ⟩ ≡ #if ¬defined ( ) #define

⟨ Exported subroutines 14 ⟩ #endif

10. For consistency, we include our own header. ⟨ Module headers 8 ⟩ +≡ #include

11. The setup routine allocates space for the best setting of the λ vector. It also initializes n, a local copy of the number of vertices in the instance.

In case anyone asks for the Lagrange multipliers we used to find a particular lower bound, we’d better be able to tell them. That’s what best lambda is all about.

To save on scans, we use double-buffering for the λ vector, storing both a read lambda vector and a write lambda vector. ⟨ Subroutines 11 ⟩ ≡

void ascend setup(int the n)

{ n = the n; best lambda = new arr of (double, n); read lambda = new arr of (double, n); write lambda = new arr of (double, n); ⟨ Other allocations 16 ⟩ total iter = −1;

}

See also sections 12, 13, 24, and 25. This code is used in section 6.

12. The cleanup routine undoes the effect of the setup routine. ⟨ Subroutines 11 ⟩ +≡

void ascend cleanup(void)

{ free mem(best lambda); free mem(read lambda); free mem(write lambda); mem deduct (sizeof (double) ∗ 3 ∗ n); ⟨ Other deallocations 17 ⟩ n = 0; total iter = −1;

}

13. We give the outside world read-only access to best lambda. ⟨ Subroutines 11 ⟩ +≡

double ∗const ascend best lambda(void)

{

return best lambda; } 14. These routines need to be announced to the world. ⟨ Exported subroutines 14 ⟩ ≡

void ascend setup(int the n); void ascend cleanup(void); double ∗const ascend best lambda(void);

See also section 26. This code is used in section 9.

15. We need to declare the local state. ⟨ Module variables 15 ⟩ ≡

static int n = 0; static int total iter = −1; static double ∗best lambda = Λ, ∗read lambda = Λ, ∗write lambda = Λ;

See also sections 18, 29, and 45. This code is used in section 6.

16. We also record the degree of each vertex in the 1-tree. Value degree less 2 [i] is two less than the degree of vertex i.

We also record the previous iteration’s degree vector as degree less 2 old . ⟨ Other allocations 16 ⟩ ≡

degree less 2 = new arr of (int, n); degree less 2 old = new arr of (int, n);

See also sections 27 and 43. This code is used in section 11.

17. ⟨ Other deallocations 17 ⟩ ≡

free mem(degree less 2 ); mem deduct (sizeof (int) ∗ n); free mem(degree less 2 old ); mem deduct (sizeof (int) ∗ n);

See also sections 28 and 44. This code is used in section 12.

18. ⟨ Module variables 15 ⟩ +≡

static int ∗degree less 2 = Λ; static int ∗degree less 2 old = Λ; 19. The normalizer of a 1-tree is a measure of how far off the 1-tree is from being a tour. It is zero when the 1-tree is a tour, and grows the farther (degree-wise) the 1-tree is from a tour.

In fact, it is the square of the Euclidean distance between the degree less 2 vector and the origin. We’re trying to drive the degree less 2 vector to the origin. ⟨ Module subroutines 19 ⟩ ≡

static double normalizer (int n, int ∗degree less 2 )

{ int i; double l; for (l = 0.0, i = 0; i < n; i^{++}) {

l += degree less 2 [i] ∗ degree less 2 [i]; } return l;

}

See also sections 21, 40, and 41. This code is used in section 6.

20. We declare the normalizer function with a prototype. ⟨ Module prototypes 20 ⟩ ≡

static double normalizer (int n, int ∗degree less 2 );

See also section 22. This code is used in section 6.

21. Given a step size factor t, procedure update lambda updates λ to make each vertex either more or less attractive next time around, depending on whether that vertex is currently over-connected or underconnected.

We implement the double-buffering here too: read from read lambda, write to write lambda. ⟨ Module subroutines 19 ⟩ +≡

static void update lambda(int n, double t, int ∗degree less 2 , int ∗degree less 2 old , double

∗read lambda, double ∗write lambda)

{ int i; const double recent share = 0.75; /∗ Between 0 and 1, nearer 1. ∗/ const double ta = t ∗ recent share, tb = t ∗ (1.0 − recent share); for (i = 0; i < n; i^{++}) {

write lambda[i] = read lambda[i] + ta ∗ degree less 2 [i] + tb ∗ degree less 2 old [i]; }

}

22. We also declare update lambda. ⟨ Module prototypes 20 ⟩ +≡

static void update lambda(int n, double t, int ∗degree less 2 , int ∗degree less 2 old , double ∗read lambda, double ∗write lambda); 23. Once we’ve used degree less 2 for updating, we rotate it with degree less 2 old . ⟨ Rotate the degree vectors 23 ⟩ ≡

{ int ∗t = degree less 2 ; degree less 2 = degree less 2 old ; degree less 2 old = t;

}

This code is used in section 24.

24. Here we come to the core of this module: procedure ascend alpha beta. It performs the subgradient ascension, modifying the λ vector as we go.

Value upper bound len is the value of an upper bound on the tour length. It is used as a parameter in the step size.

Its return value is the length of the best lower bound discovered. It takes three arguments. The first is n, the number of vertices in the graph. The second and third are

parameters controlling the convergence of the ascent. The update rule used is

λ_{i}^{(k+1)} = λ_{i}^{(k)} + α · β^{k} · (0.75 · (deg^{(k)}(i) − 2) + 0.25 · (deg^{(k−1)}(i) − 2)) /ρ.

Here ρ is a scaling factor, namely the normalizer based on the current degree vector. The step size begins with a multiplier of α and decays each iteration by a factor of β. Also, we use some short term memory in the degrees: we use a combination of the last two degree vectors. ⟨ Subroutines 11 ⟩ +≡

length t ascend alpha beta(const int n, double upper bound len, double alpha, double beta) {

extern int verbose; int i, best iter , iter = −1, new is best ; double t, norm, best lower bound = 0.0, onetree len;

errorif (  ,  ␣     ␣      ␣           ␣

  ␣        ␣  ␣  ␣  ␣          ␣     ␣      ␣␣      ␣   ␣   ␣     ␣  ␣  );

errorif (n < 3,  ␣    ␣ ␣  , n);
errorif (beta ≥ 1.0,  ␣       ␣ ␣  , beta);
errorif (beta ≤ 0,  ␣       ␣  ␣  , beta);

for (i = 0; i < n; i^{++}) degree less 2 old [i] = read lambda[i] = 0.0; best lower bound = 0.0; while (1) {

total iter^{++}, iter^{++}; ⟨ Compute a new onetree and its length onetree len 30 ⟩ ⟨ Compute degree less 2 from onetree 48 ⟩ new is best = (onetree len > best lower bound ); norm = normalizer (n, degree less 2 ); ⟨ Update best lower bound 36 ⟩ ⟨ break if we’re close enough to upper bound len 37 ⟩ ⟨ break if we found a tour 31 ⟩ ⟨ break if we’ve run too many iterations 34 ⟩ t = alpha ∗ (upper bound len − onetree len)/norm; ⟨ Verbose: print new 1-tree weight 49 ⟩ ⟨ break if t is too small 35 ⟩ ⟨ break if the best 1-tree length is old 33 ⟩ update lambda(n, t, degree less 2 , degree less 2 old , read lambda, write lambda); alpha ∗= beta; /∗ See Held Karp, 1971, Lemma 3 ∗/ ⟨ Verbose: show 1-tree and flush 50 ⟩ ⟨ Permute the λ vectors 38 ⟩ ⟨ Rotate the degree vectors 23 ⟩

} return best lower bound ;

} 25. The step size parameters can either be dictated by theory as given by Held and Karp, or by practice, as given by Held and Karp or any other researcher who has implemented this algorithm…

As I come back to this code after about 3 years, I’ll leave this pretty much well alone. Except I will say that a larger α produces larger steps, and often overshooting if you have a bad upper bounding length. The scaler β should be less than 1; the closer it is to 1, the slower the convergence, and the slower the run.

Apparently, it is wise to have different rules depending on whether you already have a good upper bound on the length of the optimal tour.

Here are some good defaults for a slow but accurate ascent. Call ascend instead of ascend alpha beta in order to get these values. ⟨ Subroutines 11 ⟩ +≡

length t ascend (const int n, double upper bound len)

{

return ascend alpha beta(n, upper bound len, 1.5, 0.995); }

26. ⟨ Exported subroutines 14 ⟩ +≡

length t ascend (const int n, double upper bound len);

length t ascend alpha beta(const int n, double upper bound len, double alpha, double beta);

27. We need an array of n edges to hold the 1-tree. ⟨ Other allocations 16 ⟩ +≡

onetree = new arr of (decluster edge t, n);

28. ⟨ Other deallocations 17 ⟩ +≡

free mem(onetree);

mem deduct (n ∗ sizeof (decluster edge t));

29. ⟨ Module variables 15 ⟩ +≡

static decluster edge t ∗onetree = Λ;

30. The 1-tree length we compute must be discounted by 2 · ∑ λ_{i} in order for it to be comparable to tour lengths. ⟨ Compute a new onetree and its length onetree len 30 ⟩ ≡

{ const double len = compute onetree(onetree); double lambda 2 = 0.0; int i; for (lambda 2 = 0.0, i = 0; i < n; i^{++}) lambda 2 += 2 ∗ read lambda[i]; onetree len = len − lambda 2 ;

}

This code is used in section 24.

31. If by some miracle we find a tour, then we stop right away and return that result. But since we don’t trust floating point numbers, we recompute the tour length first. ⟨ break if we found a tour 31 ⟩ ≡

if (norm ≡ 0.0) { ⟨ Verbose: found a tour 51 ⟩ for (onetree len = 0.0, i = 0; i < n; i^{++}) onetree len += onetree[i].cost ; best lower bound = onetree len; /∗ just in case imprecision screwed up best lower bound ∗/ ⟨ Verbose: show tour graphically 52 ⟩ break;

}

This code is used in section 24.

32. If we get within a specified percentage, say 0.1% of the upper bound, then let’s declare victory.

33. In Held-Karp lower bounds, don’t activate this code. ⟨ break if the best 1-tree length is old 33 ⟩ ≡ #if 0

if (is random dist matrix ) {

if (iter > 1000 ∧ iter − best iter > 5 ∧ iter − best iter < 8) { if (verbose ≥ 75) printf ( ␣␣ ␣ ␣ ␣ ␣␣ ␣ ␣ ); break;

} } else {

if (iter > 1000 ∧ iter − best iter > 5) { if (verbose ≥ 75) printf ( ␣␣ ␣ ␣ ␣ ␣␣ ␣ ␣ ); break;

} }

#endif

This code is used in section 24.

34. I want the Held-Karp lower bounds to be as good as possible, so we don’t want to activate this code. But sometimes we run too long. So we keep this as a safey. ⟨ break if we’ve run too many iterations 34 ⟩ ≡

if (iter > 1500) { if (verbose ≥ 75) printf ( ␣␣ ␣ ␣ ␣ ); break;

}

This code is used in section 24.

35. The step size should not get too small, or we won’t make progress. ⟨ break if t is too small 35 ⟩ ≡

if (t < 1 · 10^{−2}) { if (verbose ≥ 75) printf ( ␣␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ); break;

}

This code is used in section 24.

36. We also remember when the best iteration happened so we can later tell if has been a long time ago. ⟨ Update best lower bound 36 ⟩ ≡

if (new is best ) { best lower bound = onetree len; best iter = iter ;

}

This code is used in section 24.

37. Within a tenth of a percent is close enough for me! ⟨ break if we’re close enough to upper bound len 37 ⟩ ≡

if (new is best ) { double err = (upper bound len − onetree len)/upper bound len; if (err < 0.001) { if (verbose ≥ 75)

printf ( ␣␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ , err ∗ 100); break;

} }

This code is used in section 24.

38. The update scheme for the λ vector is as follows, with B representing best lambda, R representing read lambda (the λ vector used to construct the current 1-tree) and W representing write lambda, the new λ used for the next round. If we get a new best value, then we preserve best lambda with the assignment (B, R, W) := (B, W, R). If we don’t get a new best value, then we save read lambda in best lambda with the assignment (B, R, W) := (R, W, B). In both cases, the write lambda gets moved to read lambda for the next round. ⟨ Permute the λ vectors 38 ⟩ ≡

{ double ∗b = best lambda, ∗r = read lambda, ∗w = write lambda; if (new is best ) { best lambda = b; read lambda = w; write lambda = r;

} else {

best lambda = r; read lambda = w; write lambda = b;

} }

This code is used in section 24.

§39  ASCEND  COMPUTING 1-TREES 13

39. Computing 1-trees. A 1-tree on a graph with n vertices is a spanning subgraph with n edges. (Note that a 1-tree is not a tree.) All tours are 1-trees, so the heaviest tour is at least as heavy as the shortest 1-tree.

We will compute minimum 1-trees by computing an n − 2 edge minimum spanning tree over the subgraph induced by the first n − 1 vertices, then add the two shortest edges to the last vertex, the vertex labeled n − 1.

40. Now, module DECLUSTER already has machinery for computing minimum spanning trees. Let’s take advantage of it here.

For one thing, that means we have to use the data structures defined there. In particular, we require onetree to be an array of n edges, each stored as a decluster edge t value.

We also require the Lagrange multiplier λ vector to be stored in read lambda.

We return the length of the 1-tree under the given cost function. We don’t discount by ∑_{i} λ_{i} like one should before comparing to a tour length. ⟨ Module subroutines 19 ⟩ +≡

static length t compute onetree(decluster edge t ∗onetree)

{ length t len; ⟨ Compute a MST over the first n − 1 vertices 42 ⟩ ⟨ Now add the two shortest edges from vertex n − 1 47 ⟩ return len;

}

41. ⟨ Module subroutines 19 ⟩ +≡

static length t compute onetree(decluster edge t ∗onetree);

42. Note that although onetree points to an array of n edges, we only tell the MST routine about the first n − 2 of them. ⟨ Compute a MST over the first n − 1 vertices 42 ⟩ ≡

{ decluster tree t T; T .n = n − 2; T .edge = onetree; len = decluster mst custom(&T , work from, work dist , custom cost );

}

This code is used in section 40.

43. The custom MST routine requires two length n − 1 buffers: one of int values and another of double values. We prefer to do the allocation only once, not every time we compute a MST. ⟨ Other allocations 16 ⟩ +≡

work from = new arr of (int, n − 1);

work dist = new arr of (double, n − 1);

44. ⟨ Other deallocations 17 ⟩ +≡

free mem(work from);

free mem(work dist );

mem deduct ((n − 1) ∗ (sizeof (int) + sizeof (double)));

14  COMPUTING 1-TREES  ASCEND §45

45. ⟨ Module variables 15 ⟩ +≡

static int ∗work from = Λ; static double ∗work dist = Λ;

46. The custom cost function is just the ordinary cost function, but with Lagrange multipliers. ⟨ Early module subroutines 46 ⟩ ≡

static length t custom cost (int i, int j) {

return cost (i, j) + read lambda[i] + read lambda[j]; }

This code is used in section 6.

47. To add the two shortest edges we first need to find them. Array short to holds the two cities to which vertex n − 1 is closest, with the closest in position 0. Array short dist holds the distances to those cities. ⟨ Now add the two shortest edges from vertex n − 1 47 ⟩ ≡

{ const int v = n − 1; int i, short to[2]; length t short dist [2] = { , }; for (i = 0; i < v; i^{++}) {

const length t di = custom cost (v, i); if (di < short dist [0]) {

short to[1] = short to[0]; short dist [1] = short dist [0]; short to[0] = i; short dist [0] = di ;

}

else if (di < short dist [1]) { short to[1] = i; short dist [1] = di ;

} } onetree[n − 2].city [0] = v; onetree[n − 2].city [1] = short to[0]; onetree[n − 2].cost = short dist [0]; onetree[n − 1].city [0] = v; onetree[n − 1].city [1] = short to[1]; onetree[n − 1].cost = short dist [1]; len += short dist [0] + short dist [1];

}

This code is used in section 40.

48. Computing degrees is pretty simple, requiring one pass over the onetree array. ⟨ Compute degree less 2 from onetree 48 ⟩ ≡

{ int i; for (i = 0; i < n; i^{++}) degree less 2 [i] = −2; for (i = 0; i < n − 1; i^{++}) {

degree less 2 [onetree[i].city [0]]^{++}; degree less 2 [onetree[i].city [1]]^{++};

} }

This code is used in section 24.

16  VERBOSE  ASCEND §49

49. Verbose. ⟨ Verbose: print new 1-tree weight 49 ⟩ ≡

if (verbose ≥ 100) {

printf ( ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ , total iter , onetree len,

iter , t, alpha); fflush(stdout );

}

This code is used in section 24.

50. ⟨ Verbose: show 1-tree and flush 50 ⟩ ≡ #if 0

if (total iter ≡ 0 ∧ verbose ≥ 100)

show onetree(debug ps , ␣ ␣ ␣ , n, Λ, edge); else if (verbose ≥ 500) show onetree(debug ps , Λ, n, Λ, edge); if (verbose) fflush(stdout );

#endif

This code is used in section 24.

51. ⟨ Verbose: found a tour 51 ⟩ ≡ #if 0

if (verbose ≥ 50)

printf ( ␣␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ , total iter , (float)

(onetree len));

#endif

This code is used in section 31.

52. ⟨ Verbose: show tour graphically 52 ⟩ ≡ #if 0

if (verbose ≥ 100) { char s[100]; sprintf (s, ␣ ␣ , (float) onetree len); show onetree(debug ps , s, n, Λ, edge);

} #endif

This code is used in section 31.

§53  ASCEND  INDEX 17

53. Index.

: \underline{9}. alpha: \underline{24}, \underline{26}, 49. ascend : \underline{25}, \underline{26}. ascend alpha beta: \underline{24}, 25, \underline{26}. ascend best lambda: \underline{13}, \underline{14}. ascend cleanup: \underline{12}, \underline{14}. ascend setup: \underline{11}, \underline{14}. b: \underline{38}. best iter : \underline{24}, 33, 36. best lambda: 11, 12, 13, \underline{15}, 38. best lower bound : \underline{24}, 31, 36. beta: \underline{24}, \underline{26}. city : 47, 48. compute onetree: 30, \underline{40}, \underline{41}. cool: 4. cost : 8, 31, 46, 47. custom cost : 42, \underline{46}, 47. debug ps : 50, 52. decluster mst custom: 42. degree less 2 : 16, 17, \underline{18}, \underline{19}, \underline{20}, \underline{21}, \underline{22}, 23, 24, 48. degree less 2 old : 16, 17, \underline{18}, \underline{21}, \underline{22}, 23, 24. di : \underline{47}. easter eggs: 53. edge: 42, 50, 52. err : \underline{37}. errorif : 24. fflush: 49, 50. free mem: 12, 17, 28, 44. Held, Michael: 1, 3, 4. i: \underline{19}, \underline{21}, \underline{24}, \underline{30}, \underline{46}, \underline{47}, \underline{48}. : 47. is random dist matrix : 33. iter : \underline{24}, 33, 34, 36, 49. j: \underline{46}. Karp, Richard: 1, 3, 4. l: \underline{19}. lambda 2 : \underline{30}. len: \underline{30}, \underline{40}, 42, 47. : 24. mem deduct : 12, 17, 28, 44. n: \underline{15}, \underline{19}, \underline{20}, \underline{21}, \underline{22}, \underline{24}, \underline{25}, \underline{26}. new arr of : 11, 16, 27, 43. new is best : \underline{24}, 36, 37, 38. norm: \underline{24}, 31. normalizer : \underline{19}, \underline{20}, 24. onetree: 27, 28, \underline{29}, 30, 31, \underline{40}, \underline{41}, 42, 47, 48. onetree len: \underline{24}, 30, 31, 36, 37, 49, 51, 52. printf : 33, 34, 35, 37, 49, 51. r: \underline{38}. read lambda: 11, 12, \underline{15}, \underline{21}, \underline{22}, 24, 30, 38, 40, 46. recent share: \underline{21}. s: \underline{52}. short dist : \underline{47}. short to: \underline{47}. show onetree: 50, 52. sprintf : 52. stdout : 49, 50. T: \underline{42}. t: \underline{21}, \underline{22}, \underline{23}, \underline{24}. ta: \underline{21}. tb: \underline{21}. the n: \underline{11}, \underline{14}. total iter : 11, 12, \underline{15}, 24, 49, 50, 51. update lambda: \underline{21}, \underline{22}, 24. upper bound len: \underline{24}, \underline{25}, \underline{26}, 37. v: \underline{47}. verbose: \underline{24}, 33, 34, 35, 37, 49, 50, 51, 52. w: \underline{38}. warping local space: 4. work dist : 42, 43, 44, \underline{45}. work from: 42, 43, 44, \underline{45}. write lambda: 11, 12, \underline{15}, \underline{21}, \underline{22}, 24, 38.

⟨ Compute a MST over the first n − 1 vertices 42 ⟩ Used in section 40. ⟨ Compute a new onetree and its length onetree len 30 ⟩ Used in section 24.

⟨ Compute degree less 2 from onetree 48 ⟩ Used in section 24.

⟨ Early module subroutines 46 ⟩ Used in section 6. ⟨ Exported subroutines 14, 26 ⟩ Used in section 9.

⟨ Module headers 8, 10 ⟩ Used in section 6. ⟨ Module prototypes 20, 22 ⟩ Used in section 6. ⟨ Module subroutines 19, 21, 40, 41 ⟩ Used in section 6. ⟨ Module variables 15, 18, 29, 45 ⟩ Used in section 6.

⟨ Now add the two shortest edges from vertex n − 1 47 ⟩ Used in section 40.

⟨ Other allocations 16, 27, 43 ⟩ Used in section 11. ⟨ Other deallocations 17, 28, 44 ⟩ Used in section 12.

⟨ Permute the λ vectors 38 ⟩ Used in section 24. ⟨ Rotate the degree vectors 23 ⟩ Used in section 24.

⟨ Subroutines 11, 12, 13, 24, 25 ⟩ Used in section 6. ⟨ System headers 7 ⟩ Used in section 6. ⟨ Update best lower bound 36 ⟩ Used in section 24.

⟨ Verbose: found a tour 51 ⟩ Used in section 31. ⟨ Verbose: print new 1-tree weight 49 ⟩ Used in section 24. ⟨ Verbose: show 1-tree and flush 50 ⟩ Used in section 24. ⟨ Verbose: show tour graphically 52 ⟩ Used in section 31. ⟨ 9 ⟩

⟨ break if t is too small 35 ⟩ Used in section 24.

⟨ break if the best 1-tree length is old 33 ⟩ Used in section 24.

⟨ break if we found a tour 31 ⟩ Used in section 24.

⟨ break if we’re close enough to upper bound len 37 ⟩ Used in section 24. ⟨ break if we’ve run too many iterations 34 ⟩ Used in section 24.

July 23, 1998 at 12:14

ASCEND

Section Page

Held-Karp lower bounds for the TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 3 Subgradient optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 Computing 1-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 13 Verbose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 16 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 17

Copyright \begin{matrix}c \\ ◯ \end{matrix}1994, 1995, 1996, 1997, 1998 David Neto This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. You may contact David Neto via email at netod@acm.org, or with greater latency at Department of Computer Science, University of Toronto, 10 King’s College Rd., Toronto, Ontario, M5S 3G4, Canada This work was funded in part by the Natural Sciences and Engineering Research Council of Canada, and by the Department of Computer Science at the University of Toronto.