# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**134**> 135 136 137 138 139 140 .. 156 >> Next

Similarly, if (e the set of tanks totally emptied at operation I must be a weak maximal set as defined by (12.17) with

and q = q,.

Based on the above, we will now use conditions (12.16) and (12.17) to construct for each level (operation) t a family 3;l of sets that are possible candidates for containing the amount a, of liquid A(l) after operation I. In other words, conditions (12.16) and (12.17) are used to reduce the number of possible states of the system at each stage. The families are constructed as follows.

Assuming SFwlt} is known, and starting with SFt = 0 then for every S' i) generate the family Sf of all the sets S satisfying condition (12.16) if le<(> (or satisfying condition (12.17) if I e vb). Form the family = {S U S' | S e if (e <l>, or the family U = {S' - S | S e ?f} if leijt. Update 3'l=9'lLiaU and continue until all S'e&v(l) have been considered.

The above procedure is initialized by setting = F0.

Formulation

Let x[= 1 if the rth weak minimal set S' e is used to hold the quantity at of liquid A(l) at stage I, and 0 otherwise, and let y{ be the quantity of liquid A(l) held in tank j after the (th operation. Also let tjr(l)= 1 if j e S' and 0 otherwise, and /3i = 1-

The problem can now be stated as:

N 0i

min z = X Pi X V'jxf

(12.19)

l-l r=l

?t

S t. X x'i= 1

1 = 1,...,N

(12.20)

r = l

m

X(y|-yl<!))=&?[ I = 1,. . . , N

(12.21)

J=1

358

Nicos Christofides, Aristide Mingozzi, and raolo Toth

(12.22)

8(yi-yU)&0 / = 1.m; 1 = 1.n (12.23)

X X VM*'))-<,(()+Xv(Ox;5:51 7 = 1--- m; I = 1,..., n

i = l r=1

(12.24)

(12.25)

where S = +1 if lecf) and 1 if I e i//, and where

V[= X/V(0-

We must also take for initialization (3_j = 1, yLt = y0, f^ ( i) = 1 if / e F|, and 0 otherwise. (Note that since (3_, = 1, r can only take the value 1, and

Equation (12.20) says that only one S' must be chosen from each family S'i at stage I. Equation 12.21 says that the total increase (decrease) of the levels of tanks holding liquid A(l) is equal to the amount loaded (unloaded) at stage I. Conditions (12.22) and (12.23) are the continuity conditions: (12.22) for the tanks used and (12.23) for the amounts of liquid in these tanks. Condition (12.24) says that a tank can be used at most once for any liquid at any one time (i.e. it is the no-mixing requirement). Condition

(12.25) is the capacity constraint on the tanks used at stage !. (Note also that this condition sets to zero the level of liquid in any tank not used at stage I.)

In this section we describe a depth-first tree search algorithm for the solution of the problem. A branching of this tree at level k represents a set of tanks S' e3:k chosen for holding the quantity ak of liquid A (fc) after operation k.

A node of the tree at level k is represented by an ordered list L = (S'-",..., Sr->, Sr>,..., Srk) where S'-? = Fo(the initial set of tanks containing liquid i) and S' e , S'* e 3Fk. Thus, the initial conditions are now

introduced by assuming one loading operation (numbered i) for each liquid i and this loading is into the set of tanks F0 which can also be considered as the only element of a family S'-,. With this numbering all the tanks 7 = 1,..., m can be considered to be initially empty.

12.2.3 The Algorithm

Loading Problems

359

A set S'1- in L is then taken to mean that the liquid involved in the hth operation is held in the set S'* of tanks after the operation is complete. In the algorithm we will occasionally treat L as an (unordered) set, the meaning being obvious from the context.

The algorithm is initially described in a skeleton form, and parts (bounds, feasibility tests, etc.) of the algorithm are described in greater detail in the following sections.

The method proceeds as follows:

Step 1 (Initialization) Compute 3Fk for each k = 1,. .., N. Set L =

(S'-1,..., S'-1). Set z* (the cost of the best answer so far) = > and k = 1.

Step 2 (Dominance tests) Define the modified family &k as:

fk={Se S'J S satisfies conditions (12.26) and (12.27) below}

SO U S''1- = 0 (12.26)

i # k (k)

(constraint (12.24) satisfied) and:

if fce<f> (12.27a)

if keif. ScSr* (12.27b)

(constraint (12.22) satisfied).

Remove from every element dominated by another element of >k (see Section 12.2.3.3). Let /3k = \3'k\ and set rk =0.

Step 3 (Forward branching) Set rk=rk + l. Choose the set S'- e and form L = L U SV

Step 4 (Feasibility test) If k e ip, test that it is feasible to reach the state represented by L from the initial state, i.e. that variables y{ (I = 1,..., fc; 7 = 1,..., m) satisfying constraints (12.21), (12.23), and (12.25) can be found (see section 12.2.3.1).

If state L is infeasible, backtrack. If not, go to Step 5. Note that if k e <f>,

any choice of Sk leads to a state for which constraints (12.21), (12.23), and

(12.25) are always satisfied.

Step 5 (Lower bound) Calculate a lower bound lb(L) as mentioned in Section 12.2.3.2.

If lb(L)2s z* backtrack, otherwise:

If k < N, set k = k +1 and go to Step 2.

If k = N, then if z(L)<z* set z* = z(L).

**134**> 135 136 137 138 139 140 .. 156 >> Next