# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**52**> 53 54 55 56 57 58 .. 156 >> Next

The basic method described above has been adapted in a number of different ways.

Miliotis (1976) suggested and tested an algorithm in which integrality is first achievedeither by branching on fractional variables or by introducing Gomory cuts from the constraints in group (ii) aboveand then adding constraints of type 6.5a from group (i).

Grotschel (1977) considered the simultaneous inclusion of some constraints from (i) and some constraints from (ii). For any (in general fractional) solution x to the lp, violated constraints of type 6.5b from group (i)

The Travelling Salesman Problem

143

were identified visually by plotting the solution on a map. (Obviously this is only possible when the tsp is a symmetric andalmostEuclidean problem.) Constraints from group (ii) were chosen to be facets of the tsp polytope and, in particular, were chosen from a class of constraints known as the comb inequalities (Chvatal, 1973; Grotschel and Padberg, 1974). These inequalities (which are only defined on nondirected graphs) are similar to the inequalities introduced by Edmonds (1965) for the linear characterization of the matching polytope. They eliminate fractional vertices of the tsp polytope but may introduce other fractional vertices from their intersections with the constraints of type 6.5b. Once more these constraints from group (ii) were chosen visually.

Christofides and Whitlock (1978) considered the inclusion, first of constraints of type 6.5b from group (i), and only when all constraints of type 6.5b are satisfied then imposed constraints from group (ii) by branching. For a fractional solution x, a corresponding graph Gx was defined, and by using the Gomory-Hu algorithm (Christofides, 1975) for determining maximum flows between every pair of vertices of Gx, a number of violated constraints of type 6.5a were identified, or it was shown that all such constraints were satisfied. Thus, the generation of the constraints to be added is automatic.

Christofides and Whitlock also considered the a priori reduction in the size of the lps to be solved, by calculating initially bound B^ of Section

6.2.2 and making use of the resulting reduced costs cl( at the end of the bound calculation procedure to eliminate variables x,, from the lp formulation before the lps are solved.

In general, LP-based methods are successful and at least competitive with pure branch and bound procedures for solving symmetric tsps, although at least two of the procedures described above can also be described as lps embedded in branch and bound schemes. Symmetric problems of up to at least 100 cities can be solved by LP-based algorithms without human intervention in subjective decision making. LP-based methods are not competitive with branch and bound methods for asymmetric tsps.

6.4 Heuristic Procedures for the tsp

The tsp is an NP-complete problem (Garey, Graham, and Johnson, 1976) and all the methods previously described for its solution have a rate of growth of the computation time which is exponential in n (the number of cities in the tsp). There are several approximation algorithms whose rate of growth of the computation time is a low order polynomial in n and which have been experimentally observed to perform well. In this section we summarize some of these procedures, and restrict our attention to symmetric tsps with cost matrices that satisfy the triangle inequality.

144

Nicos Christofides

6.4.1 The Nearest Neighbour Rule (nnr)

With this procedure, one starts with an arbitrary vertex and proceeds to form a path by joining the vertex just added to its nearest neighbouring vertex which is not yet on the path, until all vertices are visited, in which case the two end vertices of the hamiltonian path are joined to form the tsp solution.

Rosenkrantz, Steams, and Lewis (1974) have shown that:

^^riognl+1) (6.25)

where V(nnr) is the value obtained by nnr, V(tsp) is the value of the optimal solution to the tsp and [x"| is the smallest integer greater than or equal to x.

For 15, it is also shown in Rosencrantz, Stearns, and Lewis (1974) that:

^^>Klog(n + l) + 4/3) (6.26)

V(tsp)

and noted that the cause of the worst-case bound on V(nnr) (given by (6.26)) being logarithmically increasing with n is neither the fact that the last

added arc in nnr is too long, nor that the starting vertex is chosen arbitrarily.

The nnr requies 0(n2) operations to apply.

6.4.2 The Nearest Insertion Rule (nir)

In this procedure are starts with a circuit <f> passing through a subset of the set of vertices and adds sequentially into vertices not already in <t> until <t> becomes hamiltonian. The vertex (x say) to be added next at some stage can be chosen to be that vertex (not in <t>) nearest to any vertex already in <J>; having chosen x, it is inserted in that position of <t> which causes the least additional cost. The circuit <t> can be initialized to be a self-loop on an arbitrarily chosen vertex.

It is shown in Rosencrantz, Stearns, and Lewis (1974) that:

**52**> 53 54 55 56 57 58 .. 156 >> Next