Write a computer program in C++ to solve the terminal assignment problem using the optimal algorithm discussed in the chapter. The user should be able to input the matrix of terminal assignment costs and the maximum number of terminals to assign to each concentrator. The output should be an optimal assignment of terminals to concentrators.
3.2 THE TERMINAL ASSIGNMENT PROBLEM as actual terminals, PCs, or workstations at known locations. Each generves In this problem there are a number of generic "terminals." These are devices such terminal has to be interconnected to the outside world through a generic "concentrator." Depending on the type of networking being carried out, this connection is achieved by means of devices such as front-end processors, multiplexer, or ATM switches (Dorf]. Each concentrator can accommodate Let's express this problem as a mathematical program. We will define an terminal i connected to concentrator ; 0 otherwise to a given maximum number of terminals. . integer variable, Xij, as follows: 1 (3.1) Let c be the cost of connecting terminal i (i=1,2,...,N) to concentrator ilje J, where I concentrator sites have been selected). This could represent the cost of laying fiber and the cost of interface devices. Then the objective function is N min Z = {cijXij i=1 jej (3.2) There are two constraints. One indicates that each terminal is connected to exactly one concentrator. Exij = 1 i= 1, 2, ...,N jEJ (3.3) The second constraint indicates that each concentrator can accommodate at most q terminals: N Exi; 59 je J (3.4) This is, naturally, an integer linear programming problem. But it should look familiar. It is just the transportation problem of Chapter 2 with a; = 1 and b; = 9. A general-purpose linear programming algorithm could certainly be used to solve this problem. However, there are special-purpose algorithms available for its solution. One such optimal algorithm will now be described [Boor). Let the placed in a table where the ijth entry indicates the cost of a connection from be terminal i to concentrator 10 3 5 77 24 8 12 2 3 4 5 8 5 10 12 3 4 6 7 8 7 6 12 (3.5) The solution to this problem will be such that one entry in each row will be selected and not more than q entries in each column will be selected. Initially one goes through the table row by row, selecting in each row the entry having the least cost. However, if during the initial pass this means that the column constraint (say, q=2) would be violated, the row in question is skipped. For the foregoing table, this leads to: 10 (3) 5 7] (2) 4 8 12 (2) 3 4 5 8 (5) 10 12 3 4 6 7 8 7 (6) 12 (3.6) Here the selected costs are enclosed in parentheses. The next step in the algorithm is to go through each blank row in turn and select minimal cost elements in each one. Because of the column constraint, this may require changes in some of the rows where minimal cost elements were selected earlier. For instance, suppose that one is to select the "3" in the fifth row. Then the selected entry in either the second or the third row needs to be reassigned. Suppose that a different entry in the second row is selected. Then, as shown below, one of the entries in the second column could be changed to satisfy the column constraint. 2 (4) 10 3 (5) 7 8 12 (2) 3 4 5 8 (5) 10 12 (3) 4 6 7 8 7 (6) 12 10 (3) 5 7 2 (4) 8 12 (2) 3 4 5 8 5 (10) 12 (3) 4 6 7 8 7 (6) 12 (3.7) 12]L the table at the right Here the total cost of the table at the left is 25, compared to a cost of 28 for S 8 8 12 7 12 10 (2) 2 8 3 4 (3) (5) 4 7 o uo 12 (10) 12 7 (6) 12 12 8 Alternatively, the entry in the third row may be changed. Again, the necessitates a change in an entry in the second column, as follows: 7 10 (2) 4 4 5 2 (3) 4 5 10 8 5 6 7 (3) 4 6 (6) 8 7 The table at the left has a cost of 24 and the table at the right has a cost of 27. was found. For instance, suppose that 3 is selected in the fifth row. The third-ton The actual algorithm would proceed further to be sure that an optimal solution entry could then be changed to 4. The total, optimal, cost is now 23. (3) 5 7 (2) 4 8 12 2 3 (4) 5 8 (5) 10 12 (3) 4 6 7 8 7 (6) 12 Note that concentrator 4 is never utilized. This is because of the expense of connecting terminals to it compared to the cost of connecting terminals to the other concentrators. 10 (3.9) 3.2 THE TERMINAL ASSIGNMENT PROBLEM as actual terminals, PCs, or workstations at known locations. Each generves In this problem there are a number of generic "terminals." These are devices such terminal has to be interconnected to the outside world through a generic "concentrator." Depending on the type of networking being carried out, this connection is achieved by means of devices such as front-end processors, multiplexer, or ATM switches (Dorf]. Each concentrator can accommodate Let's express this problem as a mathematical program. We will define an terminal i connected to concentrator ; 0 otherwise to a given maximum number of terminals. . integer variable, Xij, as follows: 1 (3.1) Let c be the cost of connecting terminal i (i=1,2,...,N) to concentrator ilje J, where I concentrator sites have been selected). This could represent the cost of laying fiber and the cost of interface devices. Then the objective function is N min Z = {cijXij i=1 jej (3.2) There are two constraints. One indicates that each terminal is connected to exactly one concentrator. Exij = 1 i= 1, 2, ...,N jEJ (3.3) The second constraint indicates that each concentrator can accommodate at most q terminals: N Exi; 59 je J (3.4) This is, naturally, an integer linear programming problem. But it should look familiar. It is just the transportation problem of Chapter 2 with a; = 1 and b; = 9. A general-purpose linear programming algorithm could certainly be used to solve this problem. However, there are special-purpose algorithms available for its solution. One such optimal algorithm will now be described [Boor). Let the placed in a table where the ijth entry indicates the cost of a connection from be terminal i to concentrator 10 3 5 77 24 8 12 2 3 4 5 8 5 10 12 3 4 6 7 8 7 6 12 (3.5) The solution to this problem will be such that one entry in each row will be selected and not more than q entries in each column will be selected. Initially one goes through the table row by row, selecting in each row the entry having the least cost. However, if during the initial pass this means that the column constraint (say, q=2) would be violated, the row in question is skipped. For the foregoing table, this leads to: 10 (3) 5 7] (2) 4 8 12 (2) 3 4 5 8 (5) 10 12 3 4 6 7 8 7 (6) 12 (3.6) Here the selected costs are enclosed in parentheses. The next step in the algorithm is to go through each blank row in turn and select minimal cost elements in each one. Because of the column constraint, this may require changes in some of the rows where minimal cost elements were selected earlier. For instance, suppose that one is to select the "3" in the fifth row. Then the selected entry in either the second or the third row needs to be reassigned. Suppose that a different entry in the second row is selected. Then, as shown below, one of the entries in the second column could be changed to satisfy the column constraint. 2 (4) 10 3 (5) 7 8 12 (2) 3 4 5 8 (5) 10 12 (3) 4 6 7 8 7 (6) 12 10 (3) 5 7 2 (4) 8 12 (2) 3 4 5 8 5 (10) 12 (3) 4 6 7 8 7 (6) 12 (3.7) 12]L the table at the right Here the total cost of the table at the left is 25, compared to a cost of 28 for S 8 8 12 7 12 10 (2) 2 8 3 4 (3) (5) 4 7 o uo 12 (10) 12 7 (6) 12 12 8 Alternatively, the entry in the third row may be changed. Again, the necessitates a change in an entry in the second column, as follows: 7 10 (2) 4 4 5 2 (3) 4 5 10 8 5 6 7 (3) 4 6 (6) 8 7 The table at the left has a cost of 24 and the table at the right has a cost of 27. was found. For instance, suppose that 3 is selected in the fifth row. The third-ton The actual algorithm would proceed further to be sure that an optimal solution entry could then be changed to 4. The total, optimal, cost is now 23. (3) 5 7 (2) 4 8 12 2 3 (4) 5 8 (5) 10 12 (3) 4 6 7 8 7 (6) 12 Note that concentrator 4 is never utilized. This is because of the expense of connecting terminals to it compared to the cost of connecting terminals to the other concentrators. 10 (3.9)
