Combined Capacity and Flow AssignmentIn the two previous sections we have learned how to find capacities or flows ifone of them is known and we want to dimension the other. Now we considerthe problem when none of them is given and we want to optimize bothtogether.The following information is given as input:• Network topology• Traffic matrix R. (As before, an entry Rpqthe matrix is the trafficdemand from node p to q.)• An upper limit Tmaxon the network-wide mean delay.• A cost function di(Ci) for each link, similarly to the capacity assign-ment problem. We again restrict ourselves to the linear cost with fixedcharge:di(Ci) = diCi+ di0.ObjectiveFind the link capacities C = (C1, C2, . . . , Cl) and the flow assignment f =(f1, f2, . . . , fl) such that the total costD =lXi=1di(Ci)is minimized.Constraints• The flow f is a multicommodity flow satisfying R, as in the flow as-signment problem. Again, this can be expressed by a system of linearinequalities, but now the capacities are also variables, so we may putit in the formAf + BC ≤ bwith an appropriate choice of the matrices A, B and the vector b.For simplicity, we assume that it includes the obvious constraints f ≤C, C ≥ 0 and f ≥ 0.• The network-wide mean delay cannot exceed Tmax. Using our earlierderived formula for T this can be expressed asT (f, C) =1γlXi=1fiCi− fi≤ Tmaxwhere γ =Pp,qRpq. The notation T (f, C) emphasizes that now both fand C are variables to be optimized.Thus, the optimization task is formulated as follows:min D =lXi=1di(Ci)Subject toAf + BC ≤ b1γlXi=1fiCi− fi≤ TmaxSolutionEven though the task looks complicated, there is a relatively simple iterativeprocedure to find at least a local optimum. This makes use of the fact thatfor the capacity assignment problem we already have an explicite formula forthe optimal assignment (in case of linear cost function). If the capacities areassigned according to that formula, then the resulting cost will depend on theflow variables only, as it is already optimized with respect for the capacites:D(f) =lXi=1difi+ di0+³Plj=1qdjfj´2γTmaxNow we can try to optimize D(f) with respect to f , which can be done by aheuristic iterative algorithm, as sketched below.Step 0. Find an initial feasible flow f(0).(Can be done by solving the multicommodity flow problem via linearprogramming.)Step 1. Compute link weights according tow(j)i="∂D∂fi#f =f(j)where j is the iteration index.Solve the minimum cost multicommodity flow problem (via linear pro-gramming) using the w(j)ivalues as link costs. The solution is the nextiteration f(j+1).Step 2. If D(f(j+1)) ≥ D(f(j)), then stop, f(j)is a local optimum. Other-wise set j := j + 1 and repeat from Step 1.Once the algorithm has found a (locally) optimum flow, the correspondingcapacities can be directly computed from the optimal capacity assignmentsolution:Ci=
View Full Document
Unlocking...