An Application to Network DesignConsider the following network design problem. Given N nodesand a demand of transporting data from node i to node j (i, j =1, . . . , N, i 6= j) at a speed of bijMbit/s.We can build links between any pair of nodes. The cost forunit capacity (=1 Mbit/s) on a link from node i to j is aij.Higher capacity costs proportionally more, lower capacity costsproportionally less.Set aii= 0, bii= 0 for all i so we do not have to take care ofthe case when i = j in the formulas.The goal is to design which links will be built and with howmuch capacity, so that the given demand can be satisfied andthe overall cost is minimum.Let us find an LP formulation of the problem!Let zijbe the capacity we implement on link ( i, j). This is notgiven, this is what we want to optimize. If the result is zij= 0for some link, then that link will not be built.With this notation the cost of link (i, j) is aijzij, so the objectivefunction to be minimized isZ =Xi,jaijzijTo express the constraints, let x(kl)ijbe the amount of flow onlink (i, j) that carries traffic from node k to l (not known inadvance). Then the total traffic on link (i, j) is obtained bysumming up these variables for all k, l :Xk,lx(kl)ij.Thus, the capacity constraint for link (i, j) can be expressed asXk,lx(kl)ij≤ zij.The flow conservation should hold for each piece of flow, thatis, for the flow carrying traffic between each source-destinationpair k, l. To express this concisely, let us define new constantsbyd(kl)i=bklif i = k−bklif i = l0 otherwiseThe value of d(kl)ishows whether node i is source, sink or trans-shipment node for the k → l flow.Thus, the flow conservation constraints (one for each node andfor each flow) can be written asXjx(kl)ij−Xrx(kl)ri= d(kl)i(∀i, k, l)Collecting all the pieces, the LP formulation is:min Z =Xi,jaijzijsubject toXjx(kl)ij−Xrx(kl)rj= d(kl)i(∀i, k, l)Xk,lx(kl)ij− zij≤ 0 (∀i, j)xij≥ 0 (∀i, j)zij≥ 0 (∀i, j)Comments• This task is a variant of flow problems that are often re-ferred as Multicommodity Flow because several flows arehandled simultaneously.• This model contains several major simplifications. Theymake the problem solvable via linear programming, but atthe price of distancing the model from reality. Try to listsome of these simplifications!• Having found the LP formulation, a “brute force” way tosolve it would be to apply a general purpose LP algorithm.Given that the number of variables and constraints is large,it would be very slow. Below we show that there is, how-ever, a clever way of circumventing the complexity, usingthe special features of the problem.A Fast SolutionObserve that the cheapest way of sending bijamount of flowfrom node k to l is to send it all along a path for which thesum of the link costs is minimum. If this path consists of nodesk = i1, i2, . . . , ir−1, ir= l, then the resulting piece of cost isbkl(ai1,i2+ . . . + air−1,ir)Due to the linear nature of the model, these costs simply sumup, independently of each other. This suggests the followingsimple algorithm:• Find a minimum cost path between each pair k, l of nodes,with edge weights aij. This can be done by any standardshortest path algorithm that you met in earlier courses.• Set the capacity of link (i, j) to the sum of those bklvaluesfor which (i, j) is on the min cost path found for k, l.• The optimum cost can be expressed explicitely. Let Eklbethe set of edges that are on the min cost k → l path. Then,according to the above, the optimal cost
View Full Document
Unlocking...