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 intersection-structure of the set of minimum cuts is mirrored by the cactus of a graph

Motivation

• exploit for separation procedures in the branch-and-cut 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 tree-edge to disconnect the cactus and to get minimum cuts of the graph

Details

• write to Klaus Wenger
• visit this page
• poster in German (download as doc-file)

Back Top