branchScheme Class Template Reference
[Branch & bound]

Implementation of a universal branch and bound strategy. More...

#include <branchScheme.h>

Inheritance diagram for branchScheme:

Public Types
enum	TSearchLevel {   SEARCH_FEASIBLE = 0,   SEARCH_CONSTRUCT = 1,   SEARCH_EXHAUSTIVE = 2 }
enum	TSearchState {   INITIAL_DFS = 0,   CONSTRUCT_BFS = 1,   CONSTRUCT_DFS = 2,   EXHAUSTIVE_BFS = 3,   EXHAUSTIVE_DFS = 4 }
Public Member Functions
	branchScheme (branchNode< TItem, TObj > *, TObj, TModule module, TSearchLevel=SEARCH_EXHAUSTIVE) throw ()
	~branchScheme () throw ()
TSearchState	SearchState () throw ()
unsigned long	Size () const throw ()
unsigned long	Allocated () const throw ()
Data Fields
moduleGuard	M
unsigned long	nActive
unsigned long	maxActive
unsigned long	nIterations
unsigned long	nDFS
unsigned long	depth
bool	feasible
TSearchLevel	level
TFloat	sign
TObj	savedObjective
TObj	bestBound
Protected Member Functions
void	Optimize () throw ()
bool	Inspect (branchNode< TItem, TObj > *) throw ()
branchNode< TItem, TObj > *	SelectActiveNode () throw ()
void	QueueExploredNode (branchNode< TItem, TObj > *) throw ()
void	StripQueue () throw ()

---

Detailed Description

template<class TItem, class TObj>
class branchScheme< TItem, TObj >

Implementation of a universal branch and bound strategy.

---

Member Enumeration Documentation

enum TSearchLevel

The intended result of applying a branch scheme. Enumerator: SEARCH_FEASIBLE  Only a single feasible solution is produced. SEARCH_CONSTRUCT  Start with some depth first search steps to obtain good solutions. SEARCH_EXHAUSTIVE  Pure best first search since a good solution is already known.

enum TSearchState

The currently applied search strategy. Enumerator: INITIAL_DFS  Apply depth first search during the first iterations. CONSTRUCT_BFS  Apply best first search in waves. CONSTRUCT_DFS  Apply depth first search in waves. EXHAUSTIVE_BFS  Apply best first search when memory is running low. EXHAUSTIVE_DFS  Apply depth first search when memory is almost exhausted.

---

Constructor & Destructor Documentation

branchScheme (  branchNode< TItem, TObj > *  , TObj  , TModule  module, TSearchLevel  = SEARCH_EXHAUSTIVE )  throw ()

~branchScheme (   )  throw ()

---

Member Function Documentation

unsigned long Allocated (   )  const throw ()

Reimplemented from managedObject.

bool Inspect (  branchNode< TItem, TObj > *   )  throw () [protected]

void Optimize (   )  throw () [protected]

void QueueExploredNode (  branchNode< TItem, TObj > *   )  throw () [protected]

branchScheme< TItem, TObj >::TSearchState SearchState (   )  throw ()

Query the current search state.

branchNode< TItem, TObj > * SelectActiveNode (   )  throw () [protected]

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

Implements goblinRootObject.

void StripQueue (   )  throw () [protected]

---

Field Documentation

TObj bestBound

unsigned long depth

Bound on the number of non-zeros (only a copy).

bool feasible

Flag indicating if problem feasibility has been reached yet.

TSearchLevel level

moduleGuard M

unsigned long maxActive

Maximum number of queued subproblems.

unsigned long nActive

Number of queued subproblems.

unsigned long nDFS

Number of dfs steps since the last bfs or improvement.

unsigned long nIterations

Total number of evaluated subproblems.

TObj savedObjective

TFloat sign

Object sense imported from the root node.