2-Edge-Connectivity Augmentation Problem (E1-2AUG)
On-line compendium to the article:
Bang-Jensen, J.; Chiarandini, M. & Morling, P. A Computational
Investigation of Heuristic Algorithms for 2-Edge-Connectivity
AugmentationNetworks vol. 55, no. 4, pp. 299-325.
[DOI]
Preliminary version available at The Danish Mathematical Society, DMF-2007-07-005,
2007. [Article]
[Slides]
A program in C++ to verify the correctness of the solutions to the problem [v2ec.tgz]. The same program can be easily modified to output
the cuts needed to derive the set covering formulation of the E1-2AUG problem.
Instances and Solutions
A suffix "pre" in the name indicates that instances are
preprocessed and hence consist of a spanning tree + a set of augmenting
edges. Parallel edges may be present only between edges in the
augmenting set and those in the spanning tree.
Instances with uniform weights (to download all the instances use 'wget -r -l1 -nd --no-parent -A.gz' +
link)
Instances A3, B1, B6, D3, D5, M1, N1, N2,
R1, R2, E1, E2, E3 and their solutions in our format. [ljubic.ins.zip, ljubic.aug.zip].
Instances derived from TSPLIB. An
instance of E1-2AUG is derived from a TSP instance either by maintaining
the complete graph or by selecting a percentage of nearest neighbors for
each vertex. The spanning tree is the minimum spanning tree derived from
the complete graph and it is maintained the same also when the graph is
reduced to a percentage of nearest neighbors in the graph. The instances
considered are lin318m0, lin318m10, pa561m0, pa561m10, pcb442m0,
pcb442m10, pr226m0, pr226m15, pr439m0, pr439m10. Except the
pa561m0 and pa561m10, they are all Euclidean instances. [tsplib.ins.zip, tsplib.aug.zip]
Gallery
Euclidean instance. Black edges are tree edges and red edges are augmenting edges.
Small World
instance: sw-20-10-1-6. Red dashed edges are augmenting edges, bold edges
are tree edges, blue dashed edges are edges selected for augmentation in
an optimal solution:
Tree and cycle instance. Black edges are tree edges and red edges are augmenting edges.