in black and white
Main menu
Share a book About us Home
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics

Combinatorial Optimization - Cristofides N.

Cristofides N. Combinatorial Optimization - Wiley publishing , 2012. - 212 p.
Download (direct link): сombinatorialoptimi2012.pdf
Previous << 1 .. 125 126 127 128 129 130 < 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.
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)
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
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
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
exists. Let chk =Qk~Qh be the cost of link (xh, xk).
Nicos Christofides, Aristide Mingozzi, and Paolo Toth
Previous << 1 .. 125 126 127 128 129 130 < 131 > 132 133 134 135 136 137 .. 156 >> Next