# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**136**> 137 138 139 140 141 142 .. 156 >> Next

12.2.3.2 Lower Bounds

A lower bound that can be used to limit the size of the tree search can be derived by making use of a relaxation of the integer programming formulation given in Section 12.2.2. For a node Lk = {/-}!,..., Fq, S'1,. . ., Srk} of the tree this relaxation involves ignoring constraints (12.21), (12.23), and

(12.25), thus converting the problem from a mixed to a pure integer problem.

Consider a given crude i and let I* be the last operation on crude i before level fc + 1, and I be the first operation after level k involving this crude. The subset of the set Sr_ of tanks which held crude i = k(l) at level k and which will certainly continue to hold this type of crude up to level i is denoted by A[. An upper bound on the total empty space in the set Sr,_ of tanks at level I is:

I

G= X Oh ~ i + X 9k-

heSf| h=k + l

A(h)c he 4/

364

Nicos Christofides, Aristide Mingozzi, Paolo Toth

Hence

A1=0eAir(O|G<Q} (12.31)

where Al. = S,*. The sets A( can be computed (for a given liquid i) recursively using equation (12.31).

Let Ef be an upper bound on the set of possibly empty tanks at level I. Ef can also be computed recursively as:

Ef = E*1U(A(I)-AI) (12.32)

where E* = Ek, the actual set of empty tanks corresponding to node Lk.

Using (12.31) and (12.32), it is now possible to define families (3'[, say) of weak minimal sets smaller than those defined in Section 12.2.2, and still ensure that at level I of the tree search only elements of SFk need be considered. Thus

^ = {Se^|Ss?,UA,}. (12.33)

Consider a given liquid and form a graph G; as follows. For each I > k such that A (I) = i and for each set Sr,e&'k> add a vertex 6\. In addition, add a source vertex 0+ and a sink vertex 6~. Add an arc (0^(O, flf) between any two vertices 0^(O and 6? whenever:

(i) if l(>T)e<f> then S^djSSl*

(ii) if l(>T)etp then S^|)2Sj'.

Set the cost of arc (0r(n, O'?) equal to pmV^(l). In addition add arcs, of zero cost, from 0+ to 0\ for all corresponding S\ e and arcs from 0\ to 0, of cost p,V(, for all corresponding SrteS''n where t is the last operation involving liquid i.

Constraints (12.20) and (12.22) are now satisfied by any path from 0+ to

Q~ in G,. Let the least-cost path from 0+ to 6~ in G, have cost d{(k). A

lower bound to the complete problem at node Lk of the tree is then:

lb (Lk)=tdi(k) + z(Lk). (12.34)

i = 1

In addition to constraints (12.20) and (12.22), which are considered exactly (for a given liquid i), the re-definition of the families S'' corresponds to a partial consideration of constraints (12.24).

An Improved Bound

Figure 12.8 shows the graphs G, and G2 defined above for a hypothetical example involving two liquids. Gt corresponds to liquid 1 and G2 corresponds to liquid 2. The sets S] corresponding to the vertices are also shown.

Loading Problems

Load 1 Load 2 Unload 1

365

{1,2} *3{l,2}

Figure 12.8 Example of improvement to the bound

Initially (i.e. as defined by Lk) liquid 1 is in tanks (1, 2} and liquid 2 is in tank {5}.

Let us assume that the shortest path in Gt derived during the calculation of the bound is (xu x2, x3,...) with cost Cy and the shortest path in G2 is (yi. y2* ) with cost c2. The loading and unloading operations specified by these paths are infeasible since they violate constraint (12.24) for vertices x2 and y2, i.e. tank 3 is used for loading liquid 1 at level k +1 and is also used for loading liquid 2 at level fc + 2.

Let us now suppose that a penalty p. is placed on vertices x2 and y2 by adding p to the cost of all arcs emanating from these two vertices. Let the shortest paths after the penalties are placed have costs C, (p) and C2(p). Quite clearly, constraint (12.24) requires that for any tank j at most one path can pass through a vertex 0\ for which j S{. Thus, the maximum increase in the total cost of any two feasible paths (in G, and G2) caused by the penalty is p, and hence:

Ci(p) + C2(p) p

is also a lower bound to the problem.

366

Nicos Christofid.es, Aristide Mingozzi, and Paolo Toth

In general, let Wh be a set of vertices of the graphs Gu . . ., Gn (at most one from each graph) such that it violates constraint (12.24). Let p.h be a penalty associated with Wh and C(p.) be the total cost of all shortest paths under the penalized costs. The expression

C(h)-Im* (12.35)

h

is a lower bound on Lk for all nonnegative vectors p.. Expression (12.35) can be maximized with respect to p to derive the best possible bound, in much the same way as was done for the travelling salesman problem (Christofides, 1975; Held and Karp, 1971; Held, Wolfe, and Crowder, 1974).

12.2.3.3 Dominance Tests

In Step 2 of the algorithm described in Section 12.2.3 a subfamily >k was produced by applying dominance tests. In this section we describe these dominance conditions.

Given two nodes a and b of the tree (at the same level k) which have the same parent node, node a dominates node b if:

Ek(a) = Ek(b) (12.36)

where a set A is equivalent to a set B (written as AB) if it is possible to map every / e B to an element of A, one-to-one and onto, by a function p so that

**136**> 137 138 139 140 141 142 .. 156 >> Next