Pierre Lemaire

Heuristics for SONET network design (aka. k-Edge Partitioning)

This page provides the programs, tools and tests that go along:

• Approximation Algorithms for the Design of SONET Networks.
  Nadia Brauner, Yves Crama, Gerd Finke, Pierre Lemaire, and Christelle Wynants.
  RAIRO Operations Research, 37(4):235--247, 2003.

(If you find this software useful, please cite this article.)

The heuristics consist in several approximation algorithms, greedy algorithms and a tabu search to design SONET networks (that is: to split a demand graph into subgraphs of a given capacity). They are implemented in C++ and are available in a .tgz file with their commented Makefile.

Additional tools, implemented in C, are also provided in a separated .tgz file. One tool permits to generate instances of several different kinds, whereas the other one computes stats for the instances. All the performed tests were done using these tools. The main tests are described by scripts (bash) that create the instances and solve them. Those scripts are available in a .tgz file.

Note: All these pieces of software are released under the GNU General Public License.