Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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

Cut buffers. More...

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

Public Member Functions

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

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. More...
 
const CutBuffer< BaseType, CoType > & operator= (const CutBuffer< BaseType, CoType > &rhs)
 
void sort (int threshold)
 Sorts the items according to their ranks. More...
 

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(). More...
 
Mastermaster_
 A pointer to the corresponding master of the optimization. More...
 
int n_
 The number of buffered items. More...
 
Array< PoolSlotRef< BaseType, CoType > * > psRef_
 References to the pool slots of the buffered constraints/variables. More...
 
Array< double > rank_
 This array stores optionally the rank of the buffered items. More...
 
bool ranking_
 This flag is true if a rank for each buffered item is available. More...
 

Friends

class Sub
 

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 45 of file convar.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
masterA pointer to the corresponding master of the optimization.
sizeThe 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
maxThe maximal number of extracted items.
newSlotsThe 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
slotThe inserted pool slot.
keepInPoolIf 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
slotThe inserted pool slot.
keepInPoolIf 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.
rankA 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
indexThe 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
thresholdOnly 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 Function 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: