branchSymmTSP Class Reference
[Travelling salesman]

Branch & bound implementation for symmetric TSP. More...

#include <branchSymmTSP.h>

Inheritance diagram for branchSymmTSP:

Public Member Functions
	branchSymmTSP (abstractGraph &_G, TNode _root, abstractMixedGraph::TRelaxTSP method, int nCandidates) throw ()
	branchSymmTSP (branchSymmTSP &Node) throw ()
	~branchSymmTSP () throw ()
unsigned long	Size () const throw ()
unsigned long	Allocated () const throw ()
void	SetCandidateGraph (int nCandidates) throw ()
TArc	SelectVariable () throw ()
TBranchDir	DirectionConstructive (TArc i) throw (ERRange)
TBranchDir	DirectionExhaustive (TArc i) throw (ERRange)
branchNode< TArc, TFloat > *	Clone () throw ()
void	Raise (TArc i) throw (ERRange)
void	Raise (TArc a, bool) throw (ERRange)
void	Lower (TArc i) throw (ERRange)
void	Lower (TArc a, bool) throw (ERRange)
void	CheckNode (TNode) throw (ERRange)
TFloat	SolveRelaxation () throw ()
TObjectSense	ObjectSense () const throw ()
TFloat	Infeasibility () const throw ()
bool	Feasible () throw ()
TFloat	LocalSearch () throw ()
void	SaveSolution () throw ()
Data Fields
abstractGraph &	G
sparseGraph *	X
THandle	H
TNode	selected
TNode	root
abstractMixedGraph::TRelaxTSP	relaxationMethod

---

Detailed Description

Branch & bound implementation for symmetric TSP.

---

Constructor & Destructor Documentation

branchSymmTSP (  abstractGraph &  _G, TNode  _root, abstractMixedGraph::TRelaxTSP  method, int  nCandidates )  throw ()

branchSymmTSP (  branchSymmTSP &  Node  )  throw ()

~branchSymmTSP (   )  throw ()

---

Member Function Documentation

unsigned long Allocated (   )  const throw ()

Reimplemented from branchNode< TArc, TFloat >.

void CheckNode (  TNode   )  throw (ERRange)

branchNode< TArc, TFloat > * Clone (   )  throw () [virtual]

Generate a copy of this branch node. Returns: A pointer to the copy Implements branchNode< TArc, TFloat >.

branchNode< TArc, TFloat >::TBranchDir DirectionConstructive (  TArc  i  )  throw (ERRange) [virtual]

Preferred search direction before feasibility has been achieved. Implements branchNode< TArc, TFloat >.

branchNode< TArc, TFloat >::TBranchDir DirectionExhaustive (  TArc  i  )  throw (ERRange) [virtual]

Preferred search direction after feasibility has been achieved. Implements branchNode< TArc, TFloat >.

bool Feasible (   )  throw () [virtual]

Reimplemented from branchNode< TArc, TFloat >.

TFloat Infeasibility (   )  const throw () [virtual]

Symbolic value for infeasible subproblems. Implements branchNode< TArc, TFloat >.

TFloat LocalSearch (   )  throw () [virtual]

Apply a probelm dependent local search method. Returns: The (possibly improved) objective value Reimplemented from branchNode< TArc, TFloat >.

void Lower (  TArc  a, bool  )  throw (ERRange)

void Lower (  TArc  i  )  throw (ERRange) [virtual]

Lower an upper variable bound. This operation applies after solving a relaxation and duplicating the branch node. It sets an upper variable bound to the greatest integral lower bound on the current variable value. The operation may restrict further variables, namely, if it is obvoious that no solutions for the master problem are lost. Parameters: i  The index of the restricted variable Implements branchNode< TArc, TFloat >.

branchNode< TNode, TFloat >::TObjectSense ObjectSense (   )  const throw () [virtual]

Decide between maximization and minimization problems. Implements branchNode< TArc, TFloat >.

void Raise (  TArc  a, bool  )  throw (ERRange)

void Raise (  TArc  i  )  throw (ERRange) [virtual]

Raise a lower variable bound. This operation applies after solving a relaxation and duplicating the branch node. It sets a lower variable bound to the least integral upper bound on the current variable value. The operation may restrict further variables, namely, if it is obvoious that no solutions for the master problem are lost. Parameters: i  The index of the variable to be restricted Implements branchNode< TArc, TFloat >.

void SaveSolution (   )  throw () [virtual]

Copy the current solution to the original problem instance. Implements branchNode< TArc, TFloat >.

TArc SelectVariable (   )  throw () [virtual]

Selection of a variable to be restricted next. Returns: The branch variable index Implements branchNode< TArc, TFloat >.

void SetCandidateGraph (  int  nCandidates  )  throw ()

unsigned long Size (   )  const throw () [virtual]

Implements goblinRootObject.

TFloat SolveRelaxation (   )  throw () [virtual]

Solve the relaxed subproblem according. Returns: The objective value of this relaxed subproblem Implements branchNode< TArc, TFloat >.

---

Field Documentation

abstractGraph& G

THandle H

abstractMixedGraph::TRelaxTSP relaxationMethod

TNode root

TNode selected

sparseGraph* X