Travelling salesman


Data Structures
class	branchAsyTSP
	Branch & bound implementation for asymmetric TSP. More...
class	branchSymmTSP
	Branch & bound implementation for symmetric TSP. More...
Enumerations
enum	abstractMixedGraph::THeurTSP { abstractMixedGraph::TSP_HEUR_DEFAULT = -1, abstractMixedGraph::TSP_HEUR_RANDOM = 0, abstractMixedGraph::TSP_HEUR_FARTHEST = 1, abstractMixedGraph::TSP_HEUR_TREE = 2, abstractMixedGraph::TSP_HEUR_CHRISTOFIDES = 3, abstractMixedGraph::TSP_HEUR_NEAREST = 4 }
enum	abstractMixedGraph::TRelaxTSP { abstractMixedGraph::TSP_RELAX_DEFAULT = -1, abstractMixedGraph::TSP_RELAX_NULL = -2, abstractMixedGraph::TSP_RELAX_1TREE = 0, abstractMixedGraph::TSP_RELAX_FAST = 1, abstractMixedGraph::TSP_RELAX_SUBOPT = 2 }
Functions
virtual TFloat	abstractGraph::TSP_Heuristic (THeurTSP method, TNode root) throw (ERRange,ERRejected)
TFloat	abstractGraph::TSP_HeuristicChristofides (TNode r=NoNode) throw (ERRange)
bool	abstractGraph::TSP_2Exchange (TArc *pred, TFloat limit=0) throw (ERRejected)
TFloat	abstractGraph::TSP_SubOpt1Tree (TRelaxTSP method, TNode root, TFloat &bestUpper, bool branchAndBound) throw (ERRange)
TFloat	abstractGraph::TSP_BranchAndBound (TRelaxTSP method, int nCandidates, TNode root, TFloat upperBound) throw ()
TFloat	abstractMixedGraph::TSP (TNode root=NoNode) throw (ERRange,ERRejected)
TFloat	abstractMixedGraph::TSP (THeurTSP methHeur, TRelaxTSP methRelax1, TRelaxTSP methRelax2, TNode root=NoNode) throw (ERRange,ERRejected)
virtual TFloat	abstractMixedGraph::TSP_Heuristic (abstractMixedGraph::THeurTSP method, TNode root) throw (ERRange,ERRejected)
TFloat	abstractMixedGraph::TSP_HeuristicRandom () throw (ERRejected)
TFloat	abstractMixedGraph::TSP_HeuristicInsert (THeurTSP method, TNode r=NoNode) throw (ERRange,ERRejected)
TFloat	abstractMixedGraph::TSP_HeuristicTree (TNode r=NoNode) throw (ERRange,ERRejected)
TFloat	abstractMixedGraph::TSP_LocalSearch (TArc *pred) throw (ERRejected)
bool	abstractMixedGraph::TSP_NodeExchange (TArc *pred, TFloat limit=0) throw (ERRejected)
virtual TFloat	abstractMixedGraph::TSP_SubOpt1Tree (abstractMixedGraph::TRelaxTSP method, TNode root, TFloat &bestUpper, bool branchAndBound) throw (ERRange)
virtual TFloat	abstractMixedGraph::TSP_BranchAndBound (abstractMixedGraph::TRelaxTSP method, int nCandidates, TNode root, TFloat upperBound) throw (ERRejected)
TFloat	denseDiGraph::TSP_Heuristic (THeurTSP method, TNode root) throw (ERRange,ERRejected)
TFloat	denseGraph::TSP_Heuristic (THeurTSP method, TNode root) throw (ERRange,ERRejected)

Enumeration Type Documentation

enum THeurTSP [inherited]

Alternative TSP construction heuristics.

Enumerator:

TSP_HEUR_DEFAULT Apply the default method set in goblinController::methHeurTSP.

TSP_HEUR_RANDOM Apply the random starting heuristic.

TSP_HEUR_FARTHEST Apply the farthest insertion heuristic.

TSP_HEUR_TREE Apply the tree approximation method.

TSP_HEUR_CHRISTOFIDES Apply the Christofides approximation method.

TSP_HEUR_NEAREST Apply the nearest insertion heuristic.

enum TRelaxTSP [inherited]

Levels of TSP lower bounding.

Enumerator:

TSP_RELAX_DEFAULT Apply the default method set in goblinController::methRelaxTSP1 respectively goblinController::methRelaxTSP2

TSP_RELAX_NULL Do not apply any bounding procedure.

TSP_RELAX_1TREE Single one-cycle tree relaxation.

TSP_RELAX_FAST Fast subgradient optimization.

TSP_RELAX_SUBOPT Thorough subgradient optimization.

Function Documentation

TFloat TSP ( THeurTSP methHeur,

TRelaxTSP methRelax1,

TRelaxTSP methRelax2,

TNode root = NoNode

) throw (ERRange,ERRejected) [inherited]

Solve a travelling salesman instance.

Parameters:

methHeur A THeurTSP value specifying the applied construction heuristic

methRelax1 A TRelaxTSP value specifying the applied initial bounding procedure

methRelax2 A TRelaxTSP value specifying the applied branch&bound procedure

root A node index in the range [0,1,..,n-1] or NoNode

Returns:
The length of the constructed tour or InfFloat
This searches for a Hamiltonian cycle of minimum length, and exports the constructed tour by the predecessor labels. Depending on the general optimization level, the following operations take place:

Check if there is a tour given in advance
Check if the one-cycle tree rooted at r exists
Apply a construction heuristic by calling TSP_Heuristic()
Apply the lower bounding procedure TSP_SubOpt1Tree()
Call TSP_BranchAndBound() for an optimality proof or candiadate graph search Each of these steps preserves or improves the predecessor labels and the node potentials given in advance. By that, the solver can be called iteratively with different parameters.

TFloat TSP ( TNode root = NoNode ) throw (ERRange,ERRejected) [inherited]

Run the TSP solver with default parameters.

Parameters:

root A node index in the range [0,1,..,n-1] or NoNode

Returns:
The length of the constructed tour or InfFloat

bool TSP_2Exchange ( TArc * pred,

TFloat limit = 0

) throw (ERRejected) [protected, inherited]

Refine a given tour by a 2 arc exchange step.

Parameters:

pred An array of predecessor arcs, describing an Hamiltonian cycle

limit The treshold for the acceptable change of tour length

Return values:

true If the tour has been changed

This takes a given tour and searches for a pair of edges a1=uv, a2=xy which can be profitably replaced by the edges ux and vy. At most one replacement is done!

TFloat TSP_BranchAndBound ( abstractMixedGraph::TRelaxTSP method,

int nCandidates,

TNode root,

TFloat upperBound

) throw (ERRejected) [protected, virtual, inherited]

Complete evaluation of a travelling salesman instance.

Parameters:

method A TRelaxTSP value specifying the applied bounding procedure

nCandidates If non-negative, only a candidate graph is evaluated

root A node index in the range [0,1,..,n-1] or NoNode

upperBound The length of the best tour known in advance

Returns:
The length of the constructed tour or InfFloat
This procedure can be used for optimality proofs, but also to construct good (usually optimal) tours from candidate graphs. For the first goal, nCandidates==-1 is required, and all branch & bound control parameters have to be set such that the search is not terminated prematurely. If the subproblem buffer capacity is exeeded, it may help out to increase the efforts for lower bounding (method). It is recommended to start a complete evaluation only after the subgradient optimization has proven a duality gap in the range of 1-2%. By our experience, instances up to 100-150 nodes can be evaluated.
For the candidate graph evaluation, the following edges are selected:

All current predecessor arcs, practically defining a good tour known in advance
All current subgraph arcs, practically defining a one-cycle tree which has been computed by subgradient optimization
The arcs of 20 random locally optimal tours
The nCandidates least length arcs adjacent with each node It is recommended to run the search twice, once with nCandidates==1 and once nCandidates==5.

TFloat TSP_BranchAndBound ( TRelaxTSP method,

int nCandidates,

TNode root,

TFloat upperBound

) throw () [protected, inherited]

TFloat TSP_Heuristic ( THeurTSP method,

TNode root

) throw (ERRange,ERRejected) [protected, virtual, inherited]

Reimplemented from abstractGraph.

TFloat TSP_Heuristic ( THeurTSP method,

TNode root

) throw (ERRange,ERRejected) [protected, inherited]

TFloat TSP_Heuristic ( abstractMixedGraph::THeurTSP method,

TNode root

) throw (ERRange,ERRejected) [protected, virtual, inherited]

Compute a tour from a random Hamiltonian cycle.

Parameters:

method A THeurTSP value specifying the applied method

root A node index in the range [0,1,..,n-1] or NoNode

Returns:
The length of the constructed tour or InfFloat
This applies some construction heuristic, depending on the method value.
If the graph is neither a complete undirected graph nor a complete digraph, the construction heuristic is applied to the metric closure, and the tour is mapped back to the original graph. This might fail, however.

TFloat TSP_Heuristic ( THeurTSP method,

TNode root

) throw (ERRange,ERRejected) [protected, virtual, inherited]

Reimplemented in denseGraph.

TFloat TSP_HeuristicChristofides ( TNode r = NoNode ) throw (ERRange) [protected, inherited]

Compute a tour by the Christofides Heuristic.

Parameters:

r The tree root node or NoNode

Returns:
The length of the constructed tour
This works similar as TSP_HeuristicTree() in the sense that a spanning tree is extended to an Eulerian graph. Here, a minimum 1-matching of the nodes with odd degree in the tree are added. From the resulting graph, an arbitrary Eulerian walk is determined. This is reduced to a Hamiltonian cycle by travelling around the Eulerian walk and skipping all nodes which have already been visited.
The procedure is intended for metric undirected graphs, and then is 1/2-approximative, that is, the constructed tour is 3/2 times as long as an optimal tour in the worst case. The procedure works for all other kinds of complete graphs, but does not produce good tours in the general setting.
If no root node is specified, the procedure is repeated for all possible root nodes.
If CT.methLocal==LOCAL_OPTIMIZE, TSP_LocalSearch() is called for postprocessing.

TFloat TSP_HeuristicInsert ( THeurTSP method,

TNode r = NoNode

) throw (ERRange,ERRejected) [protected, inherited]

Compute a tour by farthest insertion.

Parameters:

method Either TSP_HEUR_FARTHEST or TSP_HEUR_NEAREST

r The node on the initial subtour or NoNode

Returns:
The length of the constructed tour
This starts with a single node as the initial subtour, and successively inserts the node which is most far away from the current subtour, between two nodes where it causes the least change of subtour length.
The procedure does not strictly require a complete graph. But at every stage, at least one node feasible for insertion must exist. And this is in particular false for bigraphs.
If no root node is specified, the procedure is repeated for all possible root nodes.
If CT.methLocal==LOCAL_OPTIMIZE, TSP_LocalSearch() is called for postprocessing.

TFloat TSP_HeuristicRandom ( ) throw (ERRejected) [protected, inherited]

Compute a tour from a random Hamiltonian cycle.
This sets a random premutation of the node set and then calls TSP_LocalSearch() for postprocessing. When using this procedure, it is reasonable to call it several times.

TFloat TSP_HeuristicTree ( TNode r = NoNode ) throw (ERRange,ERRejected) [protected, inherited]

Compute a tour from a minimum one-cycle tree.

Parameters:

r The tree root node or NoNode

Returns:
The length of the constructed tour
This starts with a minimum one-cycle tree. By duplicating the predecessor edges, an Eulerian walk is given. This walk is reduced to a Hamiltonian cycle as follows: The unique predecessor cycle serves as the initial subtour (including r). One tracks back from every leave node x until the current subtour is reached (say at a node y). Let z denote the successor of y on the current subtour. Then the travelled yx-path plus the arc xz is added to the subtour in replace of the arc yz.
The procedure is intended for metric undirected graphs, and then is 1-approximative, that is, the constructed tour is twice as long as an optimal tour in the worst case. The procedure works for all other kinds of complete graphs or digraphs, but does not produce good tours in the general setting.
If no root node is specified, the procedure is repeated for all possible root nodes.
If CT.methLocal==LOCAL_OPTIMIZE, TSP_LocalSearch() is called for postprocessing.

TFloat TSP_LocalSearch ( TArc * pred ) throw (ERRejected) [protected, inherited]

Refine a given tour by local optimization.

Parameters:

pred An array of predecessor arcs, describing an Hamiltonian cycle

Returns:
The length of the final tour
This takes a given tour and applies the procedures TSP_NodeExchange() and TSP_2Exchange() until no further improvement is achieved.

bool TSP_NodeExchange ( TArc * pred,

TFloat limit = 0

) throw (ERRejected) [protected, inherited]

Refine a given tour by a node exchange step.

Parameters:

pred An array of predecessor arcs, describing an Hamiltonian cycle

limit The treshold for the acceptable change of tour length

Return values:

true If the tour has been changed

This takes a given tour and searches for a node x can be profitably removed from the tour and reinserted at another place. At most one node is shifted!

TFloat TSP_SubOpt1Tree ( abstractMixedGraph::TRelaxTSP method,

TNode root,

TFloat & bestUpper,

bool branchAndBound

) throw (ERRange) [protected, virtual, inherited]

Lower bounding procedure for the travelling salesman problem.

Parameters:

method A TRelaxTSP value specifying the applied bounding procedure

root A node index in the range [0,1,..,n-1] or NoNode

bestUpper The length of the constructed tour or InfFloat

branchAndBound True, if the procedure is called for branch & bound subproblems

Returns:
The maximal observed reduced length of a one-cycle tree
This dtermines minimum one-cycle trees again and again. The found trees are used as follows: (1) For computing heuristic tours as in TSP_HeuristicTree() (2) As lower bounds on the minimum tour length (3) To adjust the potentials of nodes with "wrong" degree. (There are some minor differences betwwen the directed and the undirected setting) In the (rare) happy case, the one-cycle tree becomes a Hamiltonian cycle after several iterations which is an optimal tour then. In the regular case, for method==TSP_RELAX_FAST, duality gaps in the range of 1-2% result. Some instance, however, require method==TSP_RELAX_SUBOPT for convergence.
The final one-cycle tree is exported by the subgraph multiplicities, the best tour is exported by the predecessor labels. The according node potentials are also exported.

TFloat TSP_SubOpt1Tree ( TRelaxTSP method,

TNode root,

TFloat & bestUpper,

bool branchAndBound

) throw (ERRange) [protected, inherited]

Travelling salesman

Data Structures

Enumerations

Functions

Enumeration Type Documentation

Function Documentation