The CACTUS project
Cactus
 a cactus is a graph in which every edge is contained in at
most one cycle
 cacti are perfectly suited to store the set of global minimum cuts
of a weighted graph compactly
 the inclusion and intersectionstructure of the set of minimum
cuts is mirrored by the cactus of a graph
Motivation
 exploit for separation procedures in the branchandcut
approach to the TSP, CVRP, and similar problems
 observation that properties of TSP support graphs carrying LP solutions
can speed up cactus construction significantly
 cactus construction is an essential part in our TSPSIR project
(here)
Contribution
 cactus construction algorithm based on a completely new algorithmic
idea to construct the cactus of a TSP support graph
 preliminary experiments show that the new algorithm will be 10 to
100 times faster in practice than benchmark algorithms
 memory requirement for construction reduced from GBytes
to MBytes for relevant graph sizes compared to other algorithms
Example
 on the left is a TSP support graph with minimum cut value 2
 the corresponding cactus on the right side stores the set of
all global minimum cuts and mirrors its structure
 remove two edges of a cycle or remove one bold treeedge to disconnect
the cactus and to get minimum cuts of the graph
Details
