# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**49**> 50 51 52 53 54 55 .. 156 >> Next

r n rt

min X X .,

i=l1-1

St. X*.1 = 1 V/eN

i = l

X X*i/^1 VS.cN.

eS, i e S, xsje{0,l} Vi.jeH

Let Tspa be the asymmetric tsp composed of (6.1)-(6.5a). It is then clear that problem PDT above is a relaxation of tsp, where constraints (6.3) have been dropped.

Once more, a better bound than V(PDT) on V(tsp,) can be derived by a lagrangian relaxation of constraints (6.3), thus producing the problem:

Pdt(M

The value:

min ? ? (.,+.)- ?

i = 1 j = 1 i = 1

s.t. constraints (6.2), (6.4), and (6.5a).

V(PDT(A*)) = max[V(PDT(A))] (6.17)

is then a lower bound on V(tsp,).

For a given A, PDT(A) is essentially the problem of finding the minimum cost directed spanning tree rooted at v, of the graph G with modified costs cy. This problem can be solved by a simple polynomial bounded algorithm as shown by Edmonds (1967) and Fulkerson (1974).

The problem of solving equation (6.17) is similar to the problem of solving equation (6.16), and one of the previously mentioned techniques can be used to derive the penalties A* which are the solution to (6.17).

A few computational comments are in order here.

In the first instance, the problem of finding the directed sst of a (directed) graph is computationally more difficult than that of finding the sst of a nondirected graph, with the result that each solution of problem PDT(A) requires 4-6 times longer than the solution of an equivalent size problem PT(A) for a range of n up to about 100. Thus, the derivation of bound V(Pdx(A*)) from equation (6.17) is much more costly than the derivation of bound V(PT(A*)) from equation (6.16).

136

Nicos Christofides

Secondly, the quality of bound V(PDX(A*)although good (on average within 2% of V(tsp3)is appreciably inferior to the quality of bound V(PX(A*)) for the corresponding symmetric problem.

As a result of the above two shortcomings asymmetric tsps cannot be solved by the use of bound V(PDX(A*)) for sizes of n much above 60, as opposed to symmetric tsps which can be solved for sizes of n of up to about 100 by using bound V(PX(A*)) (Smith and Thompson, 1975).

6.2.2 Bounds from the Assignment Problem (ap)

Consider the assignment problem PA defined by expressions (6.1)(6.4). This is a relaxation of problem tsp2 where constraints (6.5a), (6.5b), or (6.5c) have been dropped. Balas and Christofides (1976) considered the introduction in a lagrangian fashion of some of the violated constraints from (6.5a) and some others from (6.5c). Let A, be the multiplier associated with the tth constraint in (6.5a) which is not satisfied. The problem then becomes:

p m(min I ZwrIx.Z +

* A\^) ^ * i=l;=l t ieS.jeS, t

[ s.t. constraints (6.2)-(6.4).

In contrast to the previously introduced relaxations PX(A) and PDX(A), the number of multipliers A, in the objective function of Pa(A) can increase exponentially, rather than linearly, with n. Thus, if h is the number of circuits formed by the ap solution, then there are 2h_1 1 possible sets S, for which constraint (6.5a) could be violated; once for cut (S S,) and once for cut (S S,), thus producing a maximum total of 2h -2 violated constraints of type (6.5a). Since h could be as high as [n/2j, the number of violated constraints is exponential in n. Balas and Christofides (1976) considered a sequential procedure for choosing the constraints to enter into the objective function by means of a lagrange multiplier, and gave an approximate noniterative method for determining these multipliers. The procedure is as follows.

Let [Cij] be the reduced cost matrix after the solution of the ap. Form the graph G0 = (N, A0) where A0 = {(i, j) | c;, = 0}. Choose any vertex ieN and form the set of vertices R(i) which can be reached from i via arcs of G0. If R(i) = N choose another vertex from N and repeat. If R(i) = N VieN stop: no more cuts will be generated. If R(i)^N then a cut Kt = (Sn S,) with St = R(i) is generated which violates (6.5a).

Once K, is identified, an initial value of the corresponding multiplier A, is computed as:

A= min [cj

(6.18)

The Travelling Salesman Problem

137

and [c;,] is updated by:

Update G0 to include the arcs for which cy has just become 0 and repeat until no more cuts can be generated. The number of cuts generated by this procedure is limited to be at the most 2(h 1).

At this stage it is no longer possible to increase V(Pa(A)) by modifying the A while keeping the modified costs c,, nonnegative. However, the ap solution for problem PA is still optimal for Pa(A) and it is possible to identify constraints of the form (6.5c) which are violated by this solution. Let the solution contain circuits <t>p, where <?>p is the set of arcs of forming that circuit. The lagrangian relaxation of the corresponding constraints (6.5c) then leads to the problem:

If the A are assumed fixed at A as mentioned earlier, the problem of maximizing V(P(A, p.)) over all p can be considered in a way similar to that used above to determine the A, that is by setting ^ to a value p which is the largest value of Pp that will leave the ap solution to problem P(A, p) unchanged. This value p is simple to derive and can be computed in much the same way that the duals are computed for the ap.

**49**> 50 51 52 53 54 55 .. 156 >> Next