# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**131**> 132 133 134 135 136 137 .. 156 >> Next

30 60 3.495 20.452 4.471 4.471t

35 50 0.040 0.058 1.072 1.919 0.410 0.576 391(1) 0.386

35 70 9.714 40.216 core limit core limit

Columns bv b\, b2, b'2, band 64 contain the results of the tree search algorithm with the corresponding bound of Section 12.1.2. Column P+b2 contains the results of an algorithm in which the lp corresponding to problem P is solved first, followed by the use of bound b2 whenever the lp solution is not integer. Column P gives information on the size of the lp tableau, the computation time, and the probability that the lp solution is integer * 3 problems solved, t 1 problem solved.

350

Nicos Christofides, Aristide Mingozzi, and Paolo Toth

Section 12.1.2. The experiments with the code were performed on randomly generated problems varying in size from 5 to 35 types of liquids (N) and from 15 to 70 tanks (M) of 5 different classes. For each value of N and M, 10 problems of that size were solved. All problems generated had a feasible loading of the liquids, and the total amount of liquid to be loaded was on average 70% of the total tank capacity.

The computational results are shown in Table 12.1. In this table, two numbers are shown for a given N and M for each column except the last. The first entry is the average solution time (CDC-7600 sec) for the 10 test problems and the second entry is the maximum solution time for these problems. From Table 12.1 it can be seen that bounds b2 and bA are quite clearly better than bounds bt, b[, b'2, and b3, and are also the ones which lead to the most stable tree search. The knapsack algorithm described in (Martello and Toth., 1977) was used for the computation of bounds bu b2, and b3, and a standard lp package (without decomposition) was used to compute bound b4. Thus, the computational times for the tree search with bound b4 can possibly be reduced quite appreciably by using a more specialized lp package. An indication of the reduction that can be achieved can be obtained from the last column of Table 12.1. For a given M and N, the first entry in this column gives the total number of variables in the lp problem corresponding to problem P', the second entry (in parentheses) gives the number of times (out of the 10 problems of size MxN) that the lp solution was naturally integer, and the third entry gives the average solution time for one lp. It may be worth noting here that the tree search wuh bound b4 almost never contained more than 10 nodes.

12.1.5 Sensitivity Results

Often it is required to know what is the maximum allowable increase of the quantity q, of liquid of type i which would leave the solution value unchanged, or to know which tanks from the set E0 could be removed and not affect this value.

Exact answers to these questions cannot be obtained from the results of the algorithm described in Section 12.1.2. In order to answer these questions exactly, it is necessary to (a) replace the definition of dominance as given by (12.4) with a much weaker condition, namely, X dominates Y if XcY; and (b) reject a node only if its bound is strictly greater than the value of the currently best answer.

With these changes all solutions of the same value will be generated as elements of the final family and sensitivity questions can be answered exactly quite simply. These changes, especially (a), are totally impractical from the computational viewpoint and approximate sensitivity results must, therefore, be derived from the (single) solution obtained by the use of the stronger conditions.

Loading Problems 351

Increase in q{

The solution S* as mentioned earlier is composed of N disjoint subsets

Ft, i = 1,.. ., N, with liquid i loaded into the set of tanks Ff. Hence q, can

be increased by

A,'=lQi-4 (12.10)

ieFT

before all tanks in Ff are filled.

Consider now another liquid i and a tank r e Ff. The amount of liquid in tank r could be as low as

I Q, (12-11)

P* r

i*F?

by filling tank r last with liquid of type k.

If for any pair of tanks t e Ff and r e Ff we have

W,*?Q,^Q,

then tanks r and r can be exchanged and an additional amount (Qr Q,) of liquid i could be accommodated.

Now form a graph G as follows:

1. For every tank t e Ff, introduce a vertex x,, t = 1,..., |Ff |.

2. For every set of tanks Ff, introduce a vertex xky k = 1,..., N 1.

3. For every tank heE0 S*, introduce a vertex xh.

Let X Xk, and Xu be the set of vertices introduced by Steps 1, 2, and 3

above, respectively. Introduce a source vertex x), and a sink vertex x":

1. Add an arc from any x, e X, to any xk e Xk whenever

c,k = max[Q, - Q, | Wr =s Qr] reft

exists and is positive and let rk be the corresponding tank. Let clk be the cost of arc (x,, x,<).

2. Add an arc from any x, e X, to any xh e Xh whenever Q > Qt and uh = v,

and let c,h = Qh-Q, be the cost of link (x,, xh).

3. Add an arc from any xh e Xh to any xk e Xk whenever

Qk = max[Qr|Qr > Qh, Wr QJ

reFv

exists. Let chk =Qk~Qh be the cost of link (xh, xk).

352

Nicos Christofides, Aristide Mingozzi, and Paolo Toth

**131**> 132 133 134 135 136 137 .. 156 >> Next