The Branch Exchange AlgorithmThe Branch Exchange Algorithm is a heuristic algorithm, which aims atcreating a 2-connected network topology, along with capacity and flow as-signment, such that the overall cost is minimum. The heuristic idea is thatwe keep changing the network topology by adding new link and deletingan existing one from the current topology in each phase, until a (locally)optimum network is found.High Level Algorithm descriptionStep 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 algo-rithm.Step 2. Local transformation: Select a link that is in the network and selectanother one that is not in the network. Delete the first link and addthe second one. But only those local transformations are acceptablethat keep the network 2-connected.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 transformationcan improve the cost, then stop, else continue from Step 2 with a newlocal transformation.Questions and Answers About the Branch Exchange Algorithm• Question: Can the algorithm search through all possible network topolo-gies?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 numberof links?Answer: We can run the algorithm with different values of m and thenchoose the best result.• Question: How many local transformations have to be tried in a phaseto check that no further improvement is possible by a local transfor-mation?Answer: The link to be deleted can be chosen in m different ways. Ifthere 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)/2is the number of all possible links on n nodes). The two choices canbe combined arbitrarily, so the number of local transformations to betried is m(n(n − 1)/2 − m).• Question: What is an easy way to choose an initial 2-connected networktopology with m links? What is the smallest value of m for which thisis possible at all?Answer: If the network is 2-connected, then each node must have atleast 2 neighbors. The minimum number of links is used if each nodehas exactly 2 neighbors, which occurs if the network is a simple ring thathas m = n links. Thus, the minimum value of m is n. If m > n thenwe may create an initial 2-connected topology by taking a ring whichuses n links and then adding the remaining m − n links
View Full Document
Unlocking...