The Branch Exchange AlgorithmThe Branch Exchange AlgorithmThe Branch Exchange AlgorithmThe Branch Exchange AlgorithmThe Branch Exchange AlgorithmQuestions and Answers About the Branch Exchange AlgorithmQuestions and Answers About the Branch Exchange AlgorithmQuestions and Answers About the Branch Exchange AlgorithmCut saturation AlgorithmCut saturation AlgorithmCut saturation AlgorithmCut saturation AlgorithmAlmost-Saturated-CutAlmost-Saturated-CutAlmost-Saturated-CutAlmost-Saturated-CutAlmost-Saturated-CutThe Branch Exchange Algorithm•The Branch Exchange Algorithm is a heuristic algorithm, which aims at creating a 2-connected network topology, along with capacity and flow assignment, such that the overall cost is minimum.The Branch Exchange Algorithm•The heuristic idea is that we keep changing the network topology by adding new link and deleting an existing one from the current topology in each phase, until a (locally) optimum network is found.The Branch Exchange Algorithm•High Level Algorithm description:–Step 0. Create an initial 2-connected topology with m links.–Step 1. Assign link capacities and flows in the current network topology. This can be done by the combined capacity and flow assignment algorithm.The Branch Exchange Algorithm•High Level Algorithm description:–Step 2. Local transformation: Select a link that is in the network and select another one that is not in the network. Delete the first link and add the second one. But only those local transformations are acceptable that keep the network 2-connected.The Branch Exchange Algorithm•High Level Algorithm description:–Step 3. Check if the new network topology is better than the previous one, by executing Step 1 and comparing the costs. If no local transformation can improve the cost, then stop, else continue from Step 2 with a new local transformation.Questions and Answers About the Branch Exchange Algorithm•Question: Can the algorithm search through all possible network topologies?•Answer: No, since by adding a new link and deleting an existing one, the number of links always remains the same.•Question: What can be done if we do not know in advance the number of links?•Answer: We can run the algorithm with different values of m and then choose the best result.Questions and Answers About the Branch Exchange Algorithm•Question: How many local transformations have to be tried in a phase to check that no further improvement is possible by a local transformation?•Answer: The link to be deleted can be chosen in m different ways. If there are n nodes, then the link to be added can be chosen in n(n - 1)/2 - m ways, as this is the number of missing links (since n(n-1)/2 is the number of all possible links on n nodes). The two choices can be combined arbitrarily, so the number of local transformations to be tried is m(n(n - 1)/2 - m).Questions and Answers About the Branch Exchange Algorithm•Question: What is an easy way to choose an initial 2-connected network topology with m links? What is the smallest value of m for which this is possible at all?•Answer: If the network is 2-connected, then each node must have at least 2 neighbors. The minimum number of links is used if each node has exactly 2 neighbors, which occurs if the network is a simple ring that has m = n links. Thus, the minimum value of m is n. If m > n then we may create an initial 2-connected topology by taking a ring which uses n links and then adding the remaining m - n links arbitrarily.Cut saturation Algorithm•In the Branch Exchange Algorithm the local transformation is chosen by trying all possibilities. For a large network this may be very slow, since for each network topology change one has to recompute the combined capacity and flow assignment to compare the costs.Cut saturation Algorithm•The Cut Saturation Algorithm is a refinement in which the local transformation is chosen more intelligently.•High Level Algorithm description:–Step 0. Create an initial topology with initial capacity assignment.–Step 1. Solve the flow assignment task in the current network.Cut saturation Algorithm–Step 2. Find a saturated cut in the current network, i.e., a set of links whose deletion would disconnect the network and on each of these links the flow is equal to the capacity.–Step 3. Add a new link that bridges over the saturated cutset.Cut saturation Algorithm–Step 4. Find a link that is expensive and underutilized. A possible measure of this can be obtained such that for each link i we compute”where Di is the link cost, Ci is the capacity and fi is the flow on the link. (Note that (Ci – fi )/Ci is a measure of the underutilization of the link, since it is the fraction of capacity that is not used.)Remove the link for which Ei is maximum and assign its capacity to the link added in Step 3. In this way a local transformation is performed.•Almost-Saturated-Cut•Consider the Cut Saturation Algorithm. A step in this algorithm is the finding of a saturated cut in the network (or detect if none exists). This is easy to carry out, whenever there is no optimality requirement and we just want to find any saturated cut, since then we can just remove saturated links one by one until the network gets disconnected. If it does not get disconnected even after removing all saturated links, then there is no saturated cut.Almost-Saturated-Cut•Consider now a modified concept that we call almost-saturated cut. This means, we accept that at most one link in the cut may not be saturated. In other words, an almost-saturated cut is a set of links that form a cut, and if the number of links in this cut is k, then at least k-1 of them are saturated.Almost-Saturated-Cut•Propose an algorithm to find an almost-saturated cut, if one exists, or detect that none exists, if that is the case. (Keep in mind that an almost-saturated cut may exist even if there is no saturated cut!) The algorithm must be efficient in the sense that it cannot check an exponentially growing number of possibilities.•It is enough to provide an informal description of the algorithm, but you have to justify its correctness.•Hint: keep in mind that any almost-saturated cut is acceptable (if there is one at all), we do not require that it is optimal in any sense.Almost-Saturated-Cut1. Remove the saturated links one by one (in arbitrary order), and after each removal check whether the network remains connected.2. If the network
View Full Document
Unlocking...