# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

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

If the well-known continuous solution is used instead of the exact one for the above knapsack problems, corresponding bounds b[, b'2 and b'3 are derived. We should note here that bj is also the optimum solution to the continuous problem corresponding to problem p, and that b3 = b3.

In the proposed tree search procedure, the computation of the families ^ of minimal sets for each liquid i is required at the beginning of the search. Numbering sequentially all the minimal sets of from 1 to plr those of :3s, from Pi +1 to p2 etc., the loading problem can be reformulated as:

(p')

mm z

= 1^

s.t. Xdx^l / = 1,... ,M

? xr = l k = 0,. .. ,N-1

r= Pk + 1

(12.8)

(12.9)

^?{0,1}

r = l,...,pN

\

Loading Problems

347

where tr= 1 if tank j is an element of the rth minimal set and 0 otherwise, K = Yit'rVi and p0 = 0.

The linear programming solution of the continuous problem corresponding to p' is a valid lower bound. We should note here that although the number of variables in p' can be very large, the problem has a very pronounced structure. In particular, if (as in real problems) the tanks are not all different but are divided into C classes with all tanks within a class being identical, problem p' contains C rows of type (12.8) (coupling constraints) and N totally decoupled rows of type (12.9), all with coefficients 1. Obviously lp decomposition is a very suitable means of solving p'. Because of this structure the solution of the linear program corresponding to p' is quite often integer, in contrast to the continuous version of problem p.

None of the lower bounds bu b2. b3, and b4 described above dominate one another. However, b4 dominates b[ and b,.

In the depth-first search the nodes emanating from a given node are ordered in ascending order of the total value of the tanks used. The nodes are then considered for forward branching in the above order.

12.1.3 Example

Consider seven types of liquid in quantities of 40, 60, 70, 80, 80, 90, and 100 respectively. There are 14 tanks available of the following sizes: 4 tanks of size 20, 4 tanks of 50, and 6 tanks of 60. We want to solve the loading problem with objective (i), i.e. all u, = 1.

We will use the nomenclature (abc) to mean the set containing a tanks of capacity 20, b tanks of capacity 50, and c tanks of capacity 60. The families i = 1,.. ., 7, can be immediately enumerated as:

y,= {(200), (010), (001)}

= {(300), (110), (020), (001)}

93 = {(400), (110), (020), (101), (011), (002)}

^4 = &s = {(400), (210), (020), (011), (101), (002)}

&6 = {(210), (011), (020), (201), (002)}

9n ={(020), (310), (201), (011), (002)}.

From these families problem p' can be formulated with 35 variables, 3 constraints of type (12.8) and 7 constraints of type (12.9). The solution of p'

as a linear program is integer, and is therefore the solution to the whole

problem. Therefore, in order to illustrate the tree search algorithm we will not use bound o4 and only use bound bj. At the root of the tree (shown in Figure 12.4), bj = 10.

348 Nicos Christofides, Aristide Mingozzi, and Paolo Toth

In Figure 12.4 the minimal set corresponding to the branching is shown next to the branching. The lower bounds are shown next to the nodes, and the order in which the nodes are generated is shown by the numbering of the nodes. Dominated nodes are not shown.

At level 1 three nodes are generated corresponding to the elements of 3FX. One of these nodes (corresponding to set (001)) is dominated and is not shown. Using the branching rule mentioned earlier, branching continues

Loading Problems

349

from node 1, etc. Of the 20 nodes shown in Figure 12.4, 7 have been rejected because of the bound, and 30 others not shown in Figure 12.4 have been rejected by the dominance tests. In the case of node 9, although the node itself is not dominated by another node at level 4, all nodes emanating from it are dominated at level 5 and hence 9 is rejected by the dominance tests. In the example, the dominance tests are applied prior to the calculation of the bound.

12.1.4 Computational Results

A computer code was developed to test the efficiency of the proposed algorithm and evaluate the effectiveness of the various bounds described in

Table 12.1 Computational performance of the tree search with various bounds

N M b i bi b2 b2 b3 b4 P' + b, P'

5 15 0.021 0.044 0.045 0.069 0.043 0.065 0.059 0.080 0.059 0.080 0.238 0.427 0.075 0.114 117(3] 0.042

10 20 0.119 0.161 0.123 0.191 0.052 0.135 0.151 0.238 0.146 0.234 0.232 0.939 0.059 0.100 114(7) 0.049

15 30 5.876 47.847 7.903 65.026 0.202 0.615 10.166 78.185 5.198 30.064 1.812 5.089 0.185 0.382 188(4) 0.091

20 30 0.901 1.667* 0.691 1.306* 0.025 0.049 0.761 1.421* 0.614 2.263 0.116 0.129 0.116 0.129 184(10) 0.116

20 40 0.112 0.376 1.968 8.151 0.275 0.453 325(5) 0.180

25 40 0.038 0.093 0.751 1.688 0.380 0.613 315(5) 0.361

30 40 0.025 0.029 0.380 0.942 0.294 0.379 294(7) 0.281

30 50 0.071 0.204 0.898 2.649 0.409 0.513 380(5) 0.367

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