A more elaborate diving class. More...

#include <BonDiver.hpp>

Inheritance diagram for Bonmin::CbcDfsDiver:

Collaboration diagram for Bonmin::CbcDfsDiver:

Public Types
enum	ComparisonModes { Enlarge, FindSolutions, CloseBound, LimitTreeSize }

Public Member Functions
	CbcDfsDiver ()
	Default constructor. More...

	CbcDfsDiver (const CbcDfsDiver &rhs)
	Copy constructor. More...

CbcDfsDiver &	operator= (const CbcDfsDiver &rhs)
	Assignment operator. More...

virtual	~CbcDfsDiver ()
	Destructor. More...

virtual CbcTree *	clone () const
	Virtual copy constructor. More...

virtual void	cleanTree (CbcModel *model, double cutoff, double &bestPossibleObjective)
	Prune the tree using an objective function cutoff. More...

virtual double	getBestPossibleObjective ()
	Get best possible objective function in the tree. More...

void	initialize (BabSetupBase &b)
	Initialize the method (get options) More...

virtual void	endSearch ()
	Don't know what this is yet? More...

void	setComparisonMode (ComparisonModes newMode)
	Changes the mode of comparison of the tree for "safety reasons" if the mode really changes we always finish the current dive and put all the node back onto the heap. More...

ComparisonModes	getComparisonMode ()
	get the mode of comparison of the tree. More...

Heap access and maintenance methods.
virtual CbcNode *	top () const
	Return top node (next node to process.*/. More...

virtual void	push (CbcNode *x)
	Add node to the heap. More...

virtual void	pop ()
	Remove the top node of the heap. More...

virtual CbcNode *	bestNode (double cutoff)
	Remove the best node from the heap and return it. More...

vector methods
virtual bool	empty ()
	Test if empty. More...

virtual int	size ()
	Give size of the tree. More...

Static Public Member Functions
static void	registerOptions (Ipopt::SmartPtr< Bonmin::RegisteredOptions > roptions)
	Register the options of the method. More...

Protected Attributes
int	treeCleaning_
	Flag to say that we are currently cleaning the tree and should work only on the heap. More...

std::list< CbcNode * >	dive_
	List of the nodes in the current dive. More...

int	diveListSize_
	Record dive list size for constant time access. More...

int	divingBoardDepth_
	Depth of the node from which diving was started (we call this node the diving board). More...

double	cutoff_
	Last reported cutoff. More...

int	nBacktracks_
	number of backtracks done in current dive. More...

Parameters of the method.
int	maxDepthBFS_
	Maximum depth until which we'll do a bredth-first-search. More...

int	maxDiveBacktracks_
	Maximum number of backtrack in one dive. More...

int	maxDiveDepth_
	Maximum depth to go from divingBoard. More...

ComparisonModes	mode_
	Current mode of the diving strategy. More...

Private Member Functions
void	pushDiveOntoHeap (double cutoff)
	Pushes onto heap all the nodes with objective value > cutoff. More...

Detailed Description

A more elaborate diving class.

First there are several modes which can be commanded by the Comparison class below. In particular can command to dive to find solutions, to try to close the bound as possible or to limit the size of the tree.

The diving goes into the tree doing depth-first search until one of the following happens:

A prescibed maxDiveBacktrack_ number of backtracking are performed.
The guessed objective value of the current node is worst than the best incumbent.
The depth of the dive is bigger than maxDiveDepth_

In the first case all the nodes are put on the tree and the next node on top will be the top of the heap, in the two latter case we just put the node on the tree and backtrack in the list of depth-first search nodes.

Bug:: This won't work in a non-convex problem where objective does not decrease down branches.

Definition at line 199 of file BonDiver.hpp.

Member Enumeration Documentation

enum Bonmin::CbcDfsDiver::ComparisonModes

Enumerator
Enlarge	At the very beginning we might want to enlarge the tree just a bit.
FindSolutions
CloseBound
LimitTreeSize

Definition at line 202 of file BonDiver.hpp.

Constructor & Destructor Documentation

Bonmin::CbcDfsDiver::CbcDfsDiver ( )

Default constructor.

Definition at line 450 of file BonDiver.cpp.

Bonmin::CbcDfsDiver::CbcDfsDiver ( const CbcDfsDiver & rhs )

Copy constructor.

Definition at line 464 of file BonDiver.cpp.

Bonmin::CbcDfsDiver::~CbcDfsDiver ( )

virtual

Destructor.

Definition at line 497 of file BonDiver.cpp.

Member Function Documentation

CbcDfsDiver & Bonmin::CbcDfsDiver::operator= ( const CbcDfsDiver & rhs )

Assignment operator.

Definition at line 478 of file BonDiver.cpp.

CbcTree * Bonmin::CbcDfsDiver::clone ( ) const

virtual

Virtual copy constructor.

copy constructor.

Definition at line 502 of file BonDiver.cpp.

CbcNode * Bonmin::CbcDfsDiver::top ( ) const

virtual

Return top node (next node to process.*/.

Definition at line 509 of file BonDiver.cpp.

void Bonmin::CbcDfsDiver::push ( CbcNode * x )

virtual

Add node to the heap.

Definition at line 527 of file BonDiver.cpp.

void Bonmin::CbcDfsDiver::pop ( )

virtual

Remove the top node of the heap.

Definition at line 549 of file BonDiver.cpp.

CbcNode * Bonmin::CbcDfsDiver::bestNode ( double cutoff )

virtual

Remove the best node from the heap and return it.

Definition at line 568 of file BonDiver.cpp.

bool Bonmin::CbcDfsDiver::empty ( )

virtual

Test if empty.

Definition at line 688 of file BonDiver.cpp.

virtual int Bonmin::CbcDfsDiver::size ( )

inlinevirtual

Give size of the tree.

Definition at line 240 of file BonDiver.hpp.

void Bonmin::CbcDfsDiver::cleanTree	(	CbcModel *	model,
		double	cutoff,
		double &	bestPossibleObjective
	)

virtual

Prune the tree using an objective function cutoff.

Prune the tree using an objective function cutoff if nextOnBranch_ exists we push it on the heap and call CbcTree function.

This routine removes all nodes with objective worst than the specified cutoff value. It also sets bestPossibleObjective to best of all on tree before deleting.

Bug:: This won't work in a non-convex problem where objective does not decrease down branches.

Definition at line 697 of file BonDiver.cpp.

double Bonmin::CbcDfsDiver::getBestPossibleObjective ( )

virtual

Get best possible objective function in the tree.

Definition at line 711 of file BonDiver.cpp.

void Bonmin::CbcDfsDiver::registerOptions ( Ipopt::SmartPtr< Bonmin::RegisteredOptions > roptions )

static

Register the options of the method.

Definition at line 729 of file BonDiver.cpp.

void Bonmin::CbcDfsDiver::initialize ( BabSetupBase & b )

Initialize the method (get options)

Definition at line 750 of file BonDiver.cpp.

virtual void Bonmin::CbcDfsDiver::endSearch ( )

inlinevirtual

Don't know what this is yet?

Definition at line 267 of file BonDiver.hpp.

void Bonmin::CbcDfsDiver::setComparisonMode ( ComparisonModes newMode )

Changes the mode of comparison of the tree for "safety reasons" if the mode really changes we always finish the current dive and put all the node back onto the heap.

Definition at line 760 of file BonDiver.cpp.

ComparisonModes Bonmin::CbcDfsDiver::getComparisonMode ( )

inline

get the mode of comparison of the tree.

Definition at line 274 of file BonDiver.hpp.

void Bonmin::CbcDfsDiver::pushDiveOntoHeap ( double cutoff )

private

Pushes onto heap all the nodes with objective value > cutoff.

Definition at line 675 of file BonDiver.cpp.

Member Data Documentation

int Bonmin::CbcDfsDiver::treeCleaning_

protected

Flag to say that we are currently cleaning the tree and should work only on the heap.

Definition at line 281 of file BonDiver.hpp.

std::list<CbcNode *> Bonmin::CbcDfsDiver::dive_

protected

List of the nodes in the current dive.

Definition at line 283 of file BonDiver.hpp.

int Bonmin::CbcDfsDiver::diveListSize_

protected

Record dive list size for constant time access.

Definition at line 285 of file BonDiver.hpp.

int Bonmin::CbcDfsDiver::divingBoardDepth_

protected

Depth of the node from which diving was started (we call this node the diving board).

Definition at line 287 of file BonDiver.hpp.

double Bonmin::CbcDfsDiver::cutoff_

protected

Last reported cutoff.

Definition at line 289 of file BonDiver.hpp.

int Bonmin::CbcDfsDiver::nBacktracks_

protected

number of backtracks done in current dive.

Definition at line 291 of file BonDiver.hpp.

int Bonmin::CbcDfsDiver::maxDepthBFS_

protected

Maximum depth until which we'll do a bredth-first-search.

Definition at line 295 of file BonDiver.hpp.

int Bonmin::CbcDfsDiver::maxDiveBacktracks_

protected

Maximum number of backtrack in one dive.

Definition at line 297 of file BonDiver.hpp.

int Bonmin::CbcDfsDiver::maxDiveDepth_

protected

Maximum depth to go from divingBoard.

Definition at line 299 of file BonDiver.hpp.

ComparisonModes Bonmin::CbcDfsDiver::mode_

protected

Current mode of the diving strategy.

Definition at line 301 of file BonDiver.hpp.

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

/tmp/OS-2.10.2/Bonmin/src/CbcBonmin/BonDiver.hpp
/tmp/OS-2.10.2/Bonmin/src/CbcBonmin/BonDiver.cpp

Public Types

Public Member Functions

Static Public Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation