abacus::CutBuffer< BaseType, CoType > Class Template Reference

Cut buffers. More...

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

Inheritance diagram for abacus::CutBuffer< BaseType, CoType >:

Public Member Functions
	CutBuffer (Master *master, int size)
	Creates a cut buffer with capacity size.
	~CutBuffer ()
	The destructor.
int	insert (PoolSlot< BaseType, CoType > *slot, bool keepInPool)
	Adds a slot to the buffer.
int	insert (PoolSlot< BaseType, CoType > *slot, bool keepInPool, double rank)
	Adds a slot with rank to the buffer.
int	number () const
	Returns the number of buffered items.
void	remove (ArrayBuffer< int > &index)
	Removes the elements specified by index from the buffer.
int	size () const
	Returns the maximal number of items that can be buffered.
PoolSlot< BaseType, CoType > *	slot (int i)
	Returns a pointer to the i-th PoolSlot that is buffered.
int	space () const
	Returns the number of items which can still be inserted into the buffer.
Public Member Functions inherited from abacus::AbacusRoot
virtual	~AbacusRoot ()
	The destructor.

Private Member Functions
	CutBuffer (const CutBuffer< BaseType, CoType > &rhs)
void	extract (int max, ArrayBuffer< PoolSlot< BaseType, CoType > * > &newSlots)
	Takes the first max items from the buffer and clears the buffer.
const CutBuffer< BaseType, CoType > &	operator= (const CutBuffer< BaseType, CoType > &rhs)
void	sort (int threshold)
	Sorts the items according to their ranks.

Private Attributes
Array< bool >	keepInPool_
	If keepInPool_[i] is true for a buffered constraint/variables, then it is not removed from its pool although it might be discarded in extract().
Master *	master_
	A pointer to the corresponding master of the optimization.
int	n_
	The number of buffered items.
Array< PoolSlotRef< BaseType, CoType > * >	psRef_
	References to the pool slots of the buffered constraints/variables.
Array< double >	rank_
	This array stores optionally the rank of the buffered items.
bool	ranking_
	This flag is true if a rank for each buffered item is available.

Friends
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

template<class BaseType, class CoType>
class abacus::CutBuffer< BaseType, CoType >

Cut buffers.

This template class implements a buffer for constraints and variables which are generated during the cutting plane or column generation phase. There are two reasons why constraints/variables are buffered instead of being added immediately. First, the set of active constraints/variables should not be falsified during the cut/variable generation. Second, optionally a rank can be assigned to each buffered item. Then not all, but only the best items according to this rank are actually added.

Definition at line 52 of file cutbuffer.h.

Constructor & Destructor Documentation

CutBuffer() [1/2]

template<class BaseType , class CoType >

abacus::CutBuffer< BaseType, CoType >::CutBuffer ( Master *  master, int  size  )

inline

Creates a cut buffer with capacity size.

Parameters

master	A pointer to the corresponding master of the optimization.
size	The maximal number of constraints/variables which can be buffered.

Definition at line 63 of file cutbuffer.h.

~CutBuffer()

template<class BaseType , class CoType >

abacus::CutBuffer< BaseType, CoType >::~CutBuffer

(

)

The destructor.

If there are still items buffered when this object is destructed then we have to unset the locks of the buffered items. This can happen if in the feasibility test constraints are generated but for some reason (e.g., due to tailing off) the optimization of the subproblem is terminated.

CutBuffer() [2/2]

template<class BaseType , class CoType >

abacus::CutBuffer< BaseType, CoType >::CutBuffer ( const CutBuffer< BaseType, CoType > &  rhs )

private

Member Function Documentation

extract()

template<class BaseType , class CoType >

void abacus::CutBuffer< BaseType, CoType >::extract ( int  max, ArrayBuffer< PoolSlot< BaseType, CoType > * > &  newSlots  )

private

Takes the first max items from the buffer and clears the buffer.

Constraints or variables stored in slots which are not extracted are also removed from their pools if keepInPool has not been set to true at insertion time.

Parameters

max	The maximal number of extracted items.
newSlots	The extracted items are inserted into this buffer.

insert() [1/2]

template<class BaseType , class CoType >

int abacus::CutBuffer< BaseType, CoType >::insert	(	PoolSlot< BaseType, CoType > *	slot,
		bool	keepInPool
	)

Adds a slot to the buffer.

The member ranking_ has to be set to false, because since no rank is added together with this item a ranking of all items is impossible. Such that newly generated items cannot be removed immediately in a cleaning up process of the pool we set a lock which will be removed in the function extract().

Parameters

slot	The inserted pool slot.
keepInPool	If the flag keepInPool is true, then the item stored in the slot is not removed from the pool, even if it is discarded in extract(). Items regenerated from a pool should always have this flag set to true.

Returns

0 If the item can be inserted, 1 if the buffer is already full.

insert() [2/2]

template<class BaseType , class CoType >

int abacus::CutBuffer< BaseType, CoType >::insert	(	PoolSlot< BaseType, CoType > *	slot,
		bool	keepInPool,
		double	rank
	)

Adds a slot with rank to the buffer.

In addition to the previous version of the function insert() this version also adds a rank to the item such that all buffered items can be sorted with the function sort().

Returns

0 If the item can be inserted, 1 if the buffer is already full.

Parameters

slot	The inserted pool slot.
keepInPool	If the flag keepInPool is true, then the item stored in the slot is not removed from the pool, even if it is discarded in extract(). Items regenerated from a pool should always have this flag set to true.
rank	A rank associated with the constraint/variable.

number()

template<class BaseType , class CoType >

int abacus::CutBuffer< BaseType, CoType >::number ( ) const

inline

Returns the number of buffered items.

Definition at line 86 of file cutbuffer.h.

operator=()

template<class BaseType , class CoType >

const CutBuffer< BaseType, CoType > & abacus::CutBuffer< BaseType, CoType >::operator= ( const CutBuffer< BaseType, CoType > &  rhs )

private

remove()

template<class BaseType , class CoType >

void abacus::CutBuffer< BaseType, CoType >::remove

(

ArrayBuffer< int > &

index

)

Removes the elements specified by index from the buffer.

Parameters

index

The numbers of the elements which should be removed.

size()

template<class BaseType , class CoType >

int abacus::CutBuffer< BaseType, CoType >::size ( ) const

inline

Returns the maximal number of items that can be buffered.

Definition at line 83 of file cutbuffer.h.

slot()

template<class BaseType , class CoType >

PoolSlot< BaseType, CoType > * abacus::CutBuffer< BaseType, CoType >::slot ( int  i )

inline

Returns a pointer to the i-th PoolSlot that is buffered.

Definition at line 133 of file cutbuffer.h.

sort()

template<class BaseType , class CoType >

void abacus::CutBuffer< BaseType, CoType >::sort ( int  threshold )

private

Sorts the items according to their ranks.

Parameters

threshold

Only if more than threshold items are buffered, the sorting is performed.

space()

template<class BaseType , class CoType >

int abacus::CutBuffer< BaseType, CoType >::space ( ) const

inline

Returns the number of items which can still be inserted into the buffer.

Definition at line 89 of file cutbuffer.h.

Friends And Related Symbol Documentation

Sub

template<class BaseType , class CoType >

friend class Sub

friend

Definition at line 54 of file cutbuffer.h.

Member Data Documentation

keepInPool_

template<class BaseType , class CoType >

Array<bool> abacus::CutBuffer< BaseType, CoType >::keepInPool_

private

If keepInPool_[i] is true for a buffered constraint/variables, then it is not removed from its pool although it might be discarded in extract().

Definition at line 169 of file cutbuffer.h.

master_

template<class BaseType , class CoType >

Master* abacus::CutBuffer< BaseType, CoType >::master_

private

A pointer to the corresponding master of the optimization.

Definition at line 158 of file cutbuffer.h.

n_

template<class BaseType , class CoType >

int abacus::CutBuffer< BaseType, CoType >::n_

private

The number of buffered items.

Definition at line 159 of file cutbuffer.h.

psRef_

template<class BaseType , class CoType >

Array<PoolSlotRef<BaseType, CoType>*> abacus::CutBuffer< BaseType, CoType >::psRef_

private

References to the pool slots of the buffered constraints/variables.

Definition at line 162 of file cutbuffer.h.

rank_

template<class BaseType , class CoType >

Array<double> abacus::CutBuffer< BaseType, CoType >::rank_

private

This array stores optionally the rank of the buffered items.

Definition at line 172 of file cutbuffer.h.

ranking_

template<class BaseType , class CoType >

bool abacus::CutBuffer< BaseType, CoType >::ranking_

private

This flag is true if a rank for each buffered item is available.

As soon as an item without rank is inserted it becomes false.

Definition at line 178 of file cutbuffer.h.

---

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

• include/ogdf/lib/abacus/convar.h
• include/ogdf/lib/abacus/cutbuffer.h