The Cut Saturation AlgorithmIn the Branch Exchange Algorithm the local transformation is chosen bytrying all possibilities. For a large network this may be very slow, since foreach network topology change one has to recompute the combined capacityand flow assignment to compare the costs. The Cut Saturation Algorithm isa refinement in which the local transformation is chosen more intelligently.High Level Algorithm descriptionStep 0. Create an initial topology with initial capacity assignment.Step 1. Solve the flow assignment task in the current network.Step 2. Find a saturated cut in the current network, i.e., a set of links whosedeletion would disconnect the network and on each of these links theflow is equal to the capacity.Step 3. Add a new link that bridges over the saturated cutset.Step 4. Find a link that is expensive and underutilized. A possible measureof this can be obtained such that for each link i we computeEi=Di(Ci− fi)Ciwhere Diis the link cost, Ciis the capacity and fiis the flow on thelink. (Note that (Ci− fi)/Ciis a measure of the underutilization of thelink, since it is the fraction of capacity that is not used.)Remove the link for which Eiis maximum and assign its capacity to thelink added in Step 3. In this way a local transformation is performed.Step 5. Perturbations. One can improve the design by various p erturba-tions, such as chain collapsing: if a large amount of flow is going overa sequence of links from a source to a destination, then we can inserta direct link from the source to the destination (if no such direct linkexisted) and move the flow from the path to the direct link, togetherwith the capacity used by the flow.Step 6. If the current network cost is the same as in the previous iteration(within some error bound ²), then stop, else repeat from Step
View Full Document
Unlocking...