F ← E ; /* Initialize the set of edges that have not been used yet */
∀v ∈ *V ring*(v) ← v ; /* Assign each node to a different ring */
while F 6= /0 do /* There is still some edges that have not been used */
Choose a maximum capacity edge (u, v) ∈ F ;
i ← ring(u), j ← *ring*(v) ;
if Vi ∪Vj*is a feasible ring* **then** /* Merging the rings gives a feasible ring */
∀v ∈ Vj *ring*(v) ← i ;
F ← F\{(x, y)|*ring*(x) = i,*ring*(y) = j} ;
else F ← F\{(u, v)} ;
end end Algorithm 2: Edge-Based Heuristic u with the largest traffic with the nodes in Vi. Finally it adds u to the ring Vi disregarding the capacity constraint. The pseudo-code for this heuristic is shown on algorithm 3. The node-based heuristic is run ten times. At each run, if a feasible solution is found, the corresponding value for k is kept and the next run takes k−1 as an input. The idea behind this is to try and improve the objective at each run.

U ← V ; /* Initialize the set of nodes that have not been used yet */
for i = 1 to k do /* Assign k random nodes to the k partitions */
Choose u ∈ U,Vi ← u,U ← U\{u}
end while U 6= /0 do /* There are some unused nodes */
Choose a minimum capacity ring Vi Choose u ∈ U to maximize ∑
{v∈Vi}
duv ring(u) ← Vi,U ← U\{u} ; /* Assign u to Vi */
end Algorithm 3: Node-Based Heuristic To test these heuristics, the authors have randomly generated 160 instances1. The edge-based, and the cut-based are run first. If they have found a feasible solution and obtained a value for k, the node-based is then run with the smallest value obtained for k as input. If they have not, the node-based heuristic has for input a random value from the range [klb,|V|] where klb is the *lower bound*, described previously.

## 2.2 Mip And Branch And Cut For Idp

A special case of the IDP problem where all the edges have the same weight, is studied in [7]. This special case is called the *K-Edge-Partitioning* problem. Given a simple undirected graph G = (V,E) and a value k < |E|, we want to find a partitioning of E, {E1,E2*,...* El} such that ∀i ∈ {1,...,l},|Ei| ≤ k.

The authors present two linear-time-approximation algorithms with fixed performance guarantee.

1These instances are available at www.seas.smu.edu/~olinick/srap/GRAPHS.tar.