abacus::OpenSub Class Reference

Maintains open subproblems. More...

#include <ogdf/lib/abacus/opensub.h>

Inheritance diagram for abacus::OpenSub:

Public Member Functions
	OpenSub (Master *master)
	Creates an empty list of open subproblems.
double	dualBound () const
	Returns the value of the dual bound for all subproblems in the list.
bool	empty () const
	Returns true if there is no subproblem in the set of open subproblems, false otherwise.
int	number () const
	Returns the current number of open subproblems contained in this set.
Public Member Functions inherited from abacus::AbacusRoot
virtual	~AbacusRoot ()
	The destructor.

Private Member Functions
	OpenSub (const OpenSub &rhs)
void	insert (Sub *sub)
	Adds a subproblem to the set of open subproblems.
const OpenSub &	operator= (const OpenSub &rhs)
void	prune ()
	Removes all elements from the set of opens subproblems.
void	remove (Sub *sub)
	Removes subproblem from the set of open subproblems.
Sub *	select ()
	Selects a subproblem according to the master's strategy and removes it from the list of open subproblems.
void	updateDualBound ()
	Updates dualBound_ according to the dual bounds of the subproblems contained in this set.

Private Attributes
double	dualBound_
	The dual bound of all open subproblems.
ogdf::List< Sub * >	list_
	The list storing the open subproblems.
Master *	master_
	A pointer to corresponding master of the optimization.

Friends
class	Master
class	Sub

Additional Inherited Members
Static Public Member Functions inherited from abacus::AbacusRoot
static bool	ascii2bool (const string &str)
	Converts the string str to a boolean value.
static bool	endsWith (const string &str, const string &end)
	Returns true if str ends with end, false otherwise.
static double	fracPart (double x)
	Returns the absolute value of the fractional part of x.
static const char *	onOff (bool value)
	Converts a boolean variable to the strings "on" and "off".

Detailed Description

Maintains open subproblems.

During a branch-and-bound algorithm a set of open subproblems has to be maintained. New subproblems are inserted in this set after a branching step, or when a subproblem becomes dormant. A subproblem is extracted from this list if it becomes the active subproblem which is optimized.

Definition at line 49 of file opensub.h.

Constructor & Destructor Documentation

OpenSub() [1/2]

abacus::OpenSub::OpenSub ( Master *  master )

inline

Creates an empty list of open subproblems.

Does not initialize the member dualBound_ since this can only be done if we know the sense of the objective function which is normally unknown when the constructor of the class Master is called which again calls this constructor.

Parameters

master

A pointer to the corresponding master of the optimization.

Definition at line 65 of file opensub.h.

OpenSub() [2/2]

abacus::OpenSub::OpenSub ( const OpenSub &  rhs )

private

Member Function Documentation

dualBound()

double abacus::OpenSub::dualBound

(

)

const

Returns the value of the dual bound for all subproblems in the list.

empty()

bool abacus::OpenSub::empty ( ) const

inline

Returns true if there is no subproblem in the set of open subproblems, false otherwise.

Definition at line 73 of file opensub.h.

insert()

void abacus::OpenSub::insert ( Sub *  sub )

private

Adds a subproblem to the set of open subproblems.

Parameters

sub	The subproblem that is inserted.

number()

int abacus::OpenSub::number ( ) const

inline

Returns the current number of open subproblems contained in this set.

Definition at line 68 of file opensub.h.

operator=()

const OpenSub & abacus::OpenSub::operator= ( const OpenSub &  rhs )

private

prune()

void abacus::OpenSub::prune ( )

inlineprivate

Removes all elements from the set of opens subproblems.

Definition at line 108 of file opensub.h.

remove()

void abacus::OpenSub::remove ( Sub *  sub )

inlineprivate

Removes subproblem from the set of open subproblems.

Parameters

sub	The subproblem that is removed.

Definition at line 102 of file opensub.h.

select()

Sub * abacus::OpenSub::select ( )

private

Selects a subproblem according to the master's strategy and removes it from the list of open subproblems.

This function scans the list of open subproblems and selects the subproblem with highest priority. Dormant subproblems are ignored if possible.

Returns

The selected subproblem. If the set of open subproblems is empty, 0 is returned.

updateDualBound()

void abacus::OpenSub::updateDualBound ( )

private

Updates dualBound_ according to the dual bounds of the subproblems contained in this set.

Friends And Related Symbol Documentation

Master

friend class Master

friend

Definition at line 52 of file opensub.h.

Sub

friend class Sub

friend

Definition at line 51 of file opensub.h.

Member Data Documentation

dualBound_

double abacus::OpenSub::dualBound_

private

The dual bound of all open subproblems.

Definition at line 117 of file opensub.h.

list_

ogdf::List<Sub*> abacus::OpenSub::list_

private

The list storing the open subproblems.

Definition at line 116 of file opensub.h.

master_

Master* abacus::OpenSub::master_

private

A pointer to corresponding master of the optimization.

Definition at line 115 of file opensub.h.

---

The documentation for this class was generated from the following file:

• include/ogdf/lib/abacus/opensub.h