(Solved): Suppose nodes d, e and t of the ExaByte problem represent computers in a secure environment. If no d ...

Suppose nodes d, e and t of the ExaByte problem represent computers in a secure environment. If no data is allowed to leave this secure environment, what will the new data transfer model be? Solve this new model and compare ???????the optimal solution to the optimal solution to the original model.

???????

4.9 ExaByte Networking This example illustrates how linear programming can answer questions about paths on weighted graphs. Often such problems are difficult to model efficiently. The utility of box constraints is emphasized. The ExaByte company specializes in rapid data transfer systems. They are considering using the existing computer network shown in Figure $$4.3$$ for daily operations. Each network node (labeled with blue lower case roman letters) is connected to two or more other nodes. Each connection is indicated by a red line. The red numbers indicate the maximum operating transfer rate (bandwidth) for each connection. ExaByte would like to know the maximum transfer rate achievable between starting node $$s$$ and target node $$t$$, and what routing should data take within the network. Data does not need to take a single path; it can be divided and routed among any combination of paths. Figure 4.3: Representation of a 7-node computer network. Roman letters indicate computers, red lines indicate hardwired connections, and red numbers indicate maximum data transfer rates (bandwidths) along each connection. Solution. We will assume that there is no data storage at any node, so that data only passes through the intermediate nodes $$a,b,c,d$$ and $$e$$. Also, data can travel either direction along any connection. The maximum possible transfer rate out of the starting node is $$32+13+9=54$$. The maximum possible transfer rate into the target node is $$43+8=51$$. So, whatever the optimal transfer rate is, it will not be larger than 51 . It remains to be seen whether or not the network can support an overall transfer rate of 51 . We choose decision variables which measure the data transfer rate used along each network connection. Let $$x_{ij}=(\text{ utilized transfer rate from node }i\text{ to node }j),$$ where $$i$$ and $$j$$ are taken from the node set $$\{s,a,b,c,d,e,t\}$$. In particular, we have the 10 decision variables $$x={\left[\begin{array}{llllllllll}{x}_{sa}& x_{sb}& x_{sc}& x_{ab}& x_{ad}& x_{be}& x_{cd}& x_{ce}& x_{dt}& x_{et}\end{array}\right]}^T.$$ Each decision variable can take on positive or negative values with the meaning: $$\begin{array}{l}{x}_{ij}>0?\text{ data is moving from }i\text{ to }j,\\ x_{ij}<0?\text{ data is moving from }j\text{ to }i.\end{array}$$ The objective is to maximize the transfer rate from node $$s$$ to node $$t$$. But as we have already seen, this can be measured by maximizing the transfer rate either out of node $$s$$ or into node $$t$$. If we choose the latter, we have $$z=x_{dt}+x_{et}.$$ Flow along each connection is limited by the connection bandwidth. For example, the connection between node $$a$$ and node $$b$$ has a bandwidth of 12 , so we have the constraints $$?12?x_{ab}?12.$$ Since we need not consider data transfer into the starting node we have $$0?x_{sa}?32$$ And, since we need not consider data transfer out of the target node we have $$0?x_{dt}?43$$ Taken all together, we have the box constraints on bandwidth $$\begin{array}{rl}0& ?x_{sa}?32\\ 0& ?x_{sb}?13\\ 0& ?x_{sc}?9\\ ?12& ?x_{ab}?12\\ ?10& ?x_{ad}?10\\ ?28& ?x_{be}?28\\ ?41& ?x_{cd}?41\\ ?35& ?x_{ce}?35\\ 0& ?x_{dt}?43\\ 0& ?x_{et}?8\end{array}$$ We also must consider that no data storage can occur at intermediate nodes. This means, for example, that the total data rate into node a must be equal to the total data rate out of node $$a$$. This is represented by the constraint $$\begin{array}{rl}(\text{ data rate into node }a)& =(\text{ data rate out of node }a)\\ x_{sa}& =x_{ab}+x_{ad}.\end{array}$$ This constraint holds whether or not the individual variable values are positive or negative. The constraints for the other intermediate nodes are similarly constructed. We have no sign restrictions on the decision variables, rather we have the box constraints found earlier. The reader should verify that the appropriate LP for answering ExaByte's questions is: where $$\begin{array}{rl}{x}^T& =\left[\begin{array}{llllllllll}{x}_{sa}& x_{sb}& x_{sc}& x_{ab}& x_{ad}& x_{be}& x_{cd}& x_{ce}& x_{dt}& x_{et}\end{array}\right]\\ c^T& =\left[\begin{array}{llllllllll}0& 0& 0& 0& 0& 0& 0& 0& 1& 1\end{array}\right]\\ {?}^T& =\left[\begin{array}{llllllllll}0& 0& 0& ?12& ?10& ?28& ?41& ?35& 0& 0\end{array}\right]\\ u^T& =\left[\begin{array}{llllllllll}32& 13& 9& 12& 10& 28& 41& 35& 43& 8\end{array}\right]\\ A& =\left[\begin{array}{cccccccccc}+1& 0& 0& ?1& ?1& 0& 0& 0& 0& 0\\ 0& +1& 0& +1& 0& ?1& 0& 0& 0& 0\\ 0& 0& +1& 0& 0& 0& ?1& ?1& 0& 0\\ 0& 0& 0& 0& +1& 0& +1& 0& ?1& 0\\ 0& 0& 0& 0& 0& +1& 0& +1& 0& ?1\end{array}\right]\\ b^T& =\left[\begin{array}{lllll}0& 0& 0& 0& 0\end{array}\right]\end{array}$$ The optimal solution is $$\begin{array}{c}{x}^{?}={\left[\begin{array}{llllllllll}22& 13& 9& 12& 10& 25& 33& ?24& 43& 1\end{array}\right]}^T\\ z^{?}=44.\end{array}$$ The network path is shown in Figure 4.4. The maximum transfer rate is 44. Notice that $$x_{ce}<0$$ so data moves from node $$e$$ to node $$c$$, while $$x_{ad}>0$$ so data moves from node $$a$$ to node $$d$$. Figure 4.4: Solution of the ExaByte computer network problem with transfer rates along each connection indicated by arrows for direction and numerical values for transfer rates. Remark 21. If the bounds on every variable are captured using bound constraints $$??x?u$$, then one should always use the lower and upper bound inputs provided by OCtave /Matlab functions. Placing such constraints in the A matrix for inequality constraints $$Ax?b$$ is very inefficient for solvers and it is also an inefficient way to express these simple constraints.