branchNode Class Template Reference
[Branch & bound]

Base class for branch and bound subproblems. More...

#include <branchScheme.h>

Inheritance diagram for branchNode:

managedObject goblinRootObject

Public Types

enum  TBranchDir {
  LOWER_FIRST = 0,
  RAISE_FIRST = 1
}

Public Member Functions

 branchNode (TItem nn, goblinController &thisContext, branchScheme< TItem, TObj > *=NULL) throw ()
 ~branchNode () throw ()
unsigned long Allocated () const throw ()
TObj Objective () throw ()
virtual bool Feasible () throw ()
TItem Unfixed () throw ()
virtual TItem SelectVariable ()=0 throw ()
virtual TBranchDir DirectionConstructive (TItem i)=0 throw (ERRange)
virtual TBranchDir DirectionExhaustive (TItem i)=0 throw (ERRange)
virtual branchNode< TItem,
TObj > * 		Clone ()=0 throw ()
virtual void Raise (TItem i)=0 throw (ERRange)
virtual void Lower (TItem i)=0 throw (ERRange)
virtual TObjectSense ObjectSense () const =0 throw ()
virtual TObj Infeasibility () const =0 throw ()
virtual void SaveSolution ()=0 throw ()
virtual TObj LocalSearch () throw ()

Data Fields

branchScheme< TItem, TObj > * scheme
branchNode< TItem, TObj > * succNode
TNode index
TItem depth

Protected Member Functions

virtual TObj SolveRelaxation ()=0 throw ()

Protected Attributes

TItem n
TItem unfixed
TObj objective
bool solved

Detailed Description

template<class TItem, class TObj>
class branchNode< TItem, TObj >

Base class for branch and bound subproblems.

Member Enumeration Documentation

enum TBranchDir
 

Specifier for branching directions.

Enumerator:
LOWER_FIRST  When restricting a variable, consider the lower interval first.
RAISE_FIRST  When restricting a variable, consider the upper interval first.

Constructor & Destructor Documentation

branchNode (  TItem  nn,
goblinController &  thisContext,
branchScheme< TItem, TObj > *  = NULL
)  throw ()
 

~branchNode (   )  throw ()
 

Member Function Documentation

unsigned long Allocated (   )  const throw ()
 

Reimplemented from managedObject.

Reimplemented in branchAsyTSP, branchColour, branchMaxCut, branchMIP, branchStable, and branchSymmTSP.

virtual branchNode<TItem,TObj>* Clone (   )  throw () [pure virtual]
 

Generate a copy of this branch node.

Returns:
A pointer to the copy

Implemented in branchAsyTSP, branchColour, branchMaxCut, branchMIP, branchStable, and branchSymmTSP.

virtual TBranchDir DirectionConstructive (  TItem  i  )  throw (ERRange) [pure virtual]
 

Preferred search direction before feasibility has been achieved.

Implemented in branchAsyTSP, branchColour, branchMaxCut, branchMIP, branchStable, and branchSymmTSP.

virtual TBranchDir DirectionExhaustive (  TItem  i  )  throw (ERRange) [pure virtual]
 

Preferred search direction after feasibility has been achieved.

Implemented in branchAsyTSP, branchColour, branchMaxCut, branchMIP, branchStable, and branchSymmTSP.

bool Feasible (   )  throw () [virtual]
 

Reimplemented in branchAsyTSP, branchMIP, and branchSymmTSP.

virtual TObj Infeasibility (   )  const throw () [pure virtual]
 

Symbolic value for infeasible subproblems.

Implemented in branchAsyTSP, branchColour, branchMaxCut, branchMIP, branchStable, and branchSymmTSP.

TObj LocalSearch (   )  throw () [virtual]
 

Apply a probelm dependent local search method.

Returns:
The (possibly improved) objective value

Reimplemented in branchAsyTSP, branchMaxCut, and branchSymmTSP.

virtual void Lower (  TItem  i  )  throw (ERRange) [pure 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

Implemented in branchAsyTSP, branchColour, branchMaxCut, branchMIP, branchStable, and branchSymmTSP.

TObj Objective (   )  throw ()
 

virtual TObjectSense ObjectSense (   )  const throw () [pure virtual]
 

Decide between maximization and minimization problems.

Implemented in branchAsyTSP, branchColour, branchMaxCut, branchMIP, branchStable, and branchSymmTSP.

virtual void Raise (  TItem  i  )  throw (ERRange) [pure 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

Implemented in branchAsyTSP, branchColour, branchMaxCut, branchMIP, branchStable, and branchSymmTSP.

virtual void SaveSolution (   )  throw () [pure virtual]
 

Copy the current solution to the original problem instance.

Implemented in branchAsyTSP, branchColour, branchMaxCut, branchMIP, branchStable, and branchSymmTSP.

virtual TItem SelectVariable (   )  throw () [pure virtual]
 

Selection of a variable to be restricted next.

Returns:
The branch variable index

Implemented in branchAsyTSP, branchColour, branchMaxCut, branchMIP, branchStable, and branchSymmTSP.

virtual TObj SolveRelaxation (   )  throw () [protected, pure virtual]
 

Solve the relaxed subproblem according.

Returns:
The objective value of this relaxed subproblem

Implemented in branchAsyTSP, branchColour, branchMaxCut, branchMIP, branchStable, and branchSymmTSP.

TItem Unfixed (   )  throw ()
 

Field Documentation

TItem depth
 

TNode index
 

TItem n [protected]
 

TObj objective [protected]
 

branchScheme<TItem,TObj>* scheme
 

bool solved [protected]
 

branchNode<TItem,TObj>* succNode
 

TItem unfixed [protected]