branchAsyTSP Class Reference
[Travelling salesman]

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

#include <branchAsyTSP.h>

Inheritance diagram for branchAsyTSP:

branchNode< TArc, TFloat > managedObject goblinRootObject

Public Member Functions

 branchAsyTSP (abstractMixedGraph &_G, TNode _root, abstractMixedGraph::TRelaxTSP method, int nCandidates) throw ()
 branchAsyTSP (branchAsyTSP &Node) throw ()
 ~branchAsyTSP () 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

abstractMixedGraphG
sparseDiGraphX
THandle H
TNode selected
TNode root
abstractMixedGraph::TRelaxTSP relaxationMethod

Detailed Description

Branch & bound implementation for asymmetric TSP.


Constructor & Destructor Documentation

branchAsyTSP abstractMixedGraph _G,
TNode  _root,
abstractMixedGraph::TRelaxTSP  method,
int  nCandidates
throw ()
 

branchAsyTSP branchAsyTSP Node  )  throw ()
 

~branchAsyTSP  )  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

abstractMixedGraph& G
 

THandle H
 

abstractMixedGraph::TRelaxTSP relaxationMethod
 

TNode root
 

TNode selected
 

sparseDiGraph* X