Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

abacus::Separator< BaseType, CoType > Class Template Referenceabstract

Separators. More...

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

Public Member Functions

 Separator (LpSolution< CoType, BaseType > *lpSolution, bool nonDuplications, int maxGen=300)
 Creates a separator. More...
 
virtual ~Separator ()
 The destructor. More...
 
ArrayBuffer< BaseType * > & cutBuffer ()
 Returns the buffer with the generated constraints/variable. More...
 
Separator_CUTFOUND cutFound (BaseType *cv)
 Passes a cut (constraint or variable) to the buffer. More...
 
LpSolution< CoType, BaseType > * lpSolution ()
 The lpSolution to be separated. More...
 
int maxGen () const
 Returns the maximal number of generated cutting planes. More...
 
double minAbsViolation () const
 Returns the absolute value for considering a constraint/variable as violated. More...
 
void minAbsViolation (double minAbsVio)
 Sets a new value for minAbsViolation. More...
 
int nCollisions () const
 Returns the number of collisions in the hash table. More...
 
int nDuplications () const
 Returns the number of duplicated constraints/variables which are discarded. More...
 
int nGen () const
 Returns the number of generated cutting planes. More...
 
virtual void separate ()=0
 This function has to be redefined and should implement the separation routine. More...
 
virtual bool terminateSeparation ()
 Returns true if the separation should be terminated. More...
 
void watchNonDuplPool (NonDuplPool< BaseType, CoType > *pool)
 If the separator checks for duplication of cuts, the test is also done for constraints/variables that are in the pool passed as argument. More...
 

Protected Member Functions

bool find (BaseType *cv)
 

Protected Attributes

LpSolution< CoType, BaseType > * lpSol_
 The LP solution to be separated. More...
 
Mastermaster_
 A pointer to the corresponding master of the optimization. More...
 

Private Member Functions

 Separator (const Separator< BaseType, CoType > &rhs)
 
const Separator< BaseType, CoType > & operator= (const Separator< BaseType, CoType > &rhs)
 

Private Attributes

AbaHash< unsigned, BaseType * > * hash_
 
double minAbsViolation_
 
int nDuplications_
 
ArrayBuffer< BaseType * > newCons_
 
NonDuplPool< BaseType, CoType > * pool_
 
bool sendConstraints_
 

Detailed Description

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

Separators.

This abstract template class can be used to implement a separation routine. Using this class is not mandatory, because separation can be implemented directly in Sub::pricing() and Sub::separate(). However, this class facilitates encapsulation of the code and provides functions for checking for duplication of generated constraints/variables.

If constraints are generated in the separation, then the BaseType must be Constraint and the CoType must be Variable, if variables are generated in separation this is vice versa.

The user has to derive its specific separtor class in which the separation algorithm should be implemented in function separate(). If a cutting plane is found, the function cutFound should be called.

The generated constraints/variables can be obtained by the member function cutBuffer(). The return value of that function then can serve as parameter to the functions Sub::addCons() and Sub::addVars().

Definition at line 40 of file lpsolution.h.

Constructor & Destructor Documentation

◆ Separator() [1/2]

template<class BaseType , class CoType >
abacus::Separator< BaseType, CoType >::Separator ( LpSolution< CoType, BaseType > *  lpSolution,
bool  nonDuplications,
int  maxGen = 300 
)
inline

Creates a separator.

Parameters
lpSolutionThe LP solution to be separated.
maxGenThe maximal number of cutting planes which are stored.
nonDuplicationsIf this flag is set, then the same constraint/variable is stored at most once in the buffer. In this case for constraints/variables the virtual member functions name(), hashKey(), and equal() of the base class ConVar have to be defined. Using these three functions, we check in the function cutFound if a constraint or variable is already stored in the buffer.

Definition at line 80 of file separator.h.

◆ ~Separator()

template<class BaseType , class CoType >
virtual abacus::Separator< BaseType, CoType >::~Separator ( )
inlinevirtual

The destructor.

Definition at line 99 of file separator.h.

◆ Separator() [2/2]

template<class BaseType , class CoType >
abacus::Separator< BaseType, CoType >::Separator ( const Separator< BaseType, CoType > &  rhs)
private

Member Function Documentation

◆ cutBuffer()

template<class BaseType , class CoType >
ArrayBuffer<BaseType *>& abacus::Separator< BaseType, CoType >::cutBuffer ( )
inline

Returns the buffer with the generated constraints/variable.

Definition at line 129 of file separator.h.

◆ cutFound()

template<class BaseType , class CoType >
Separator_CUTFOUND abacus::Separator< BaseType, CoType >::cutFound ( BaseType *  cv)

Passes a cut (constraint or variable) to the buffer.

If the buffer is full or the cut already exists, the cut is deleted.

Parameters
cvA pointer to a new constraint/variable found by the separation algorithm.
Returns
ABA_SEPARATOR_CUTFOUND::Added if the cut is added to the buffer;
ABA_SEPARATOR_CUTFOUND::Duplication if the cut is already in the buffer;
ABA_SEPARATOR_CUTFOUND::Full if the buffer is full.

◆ find()

template<class BaseType , class CoType >
bool abacus::Separator< BaseType, CoType >::find ( BaseType *  cv)
protected
Parameters
cvA pointer to a constraint/variable for which it should be checked if an equivalent item is already contained in the buffer.
Returns
The function checks if a constraint/variable that is equivalent to cv according to the function ConVar::equal() is already stored in the buffer by using the hashtable.

◆ lpSolution()

template<class BaseType , class CoType >
LpSolution<CoType, BaseType>* abacus::Separator< BaseType, CoType >::lpSolution ( )
inline

The lpSolution to be separated.

Definition at line 157 of file separator.h.

◆ maxGen()

template<class BaseType , class CoType >
int abacus::Separator< BaseType, CoType >::maxGen ( ) const
inline

Returns the maximal number of generated cutting planes.

Definition at line 144 of file separator.h.

◆ minAbsViolation() [1/2]

template<class BaseType , class CoType >
double abacus::Separator< BaseType, CoType >::minAbsViolation ( ) const
inline

Returns the absolute value for considering a constraint/variable as violated.

Definition at line 148 of file separator.h.

◆ minAbsViolation() [2/2]

template<class BaseType , class CoType >
void abacus::Separator< BaseType, CoType >::minAbsViolation ( double  minAbsVio)
inline

Sets a new value for minAbsViolation.

Definition at line 152 of file separator.h.

◆ nCollisions()

template<class BaseType , class CoType >
int abacus::Separator< BaseType, CoType >::nCollisions ( ) const

Returns the number of collisions in the hash table.

◆ nDuplications()

template<class BaseType , class CoType >
int abacus::Separator< BaseType, CoType >::nDuplications ( ) const
inline

Returns the number of duplicated constraints/variables which are discarded.

Definition at line 137 of file separator.h.

◆ nGen()

template<class BaseType , class CoType >
int abacus::Separator< BaseType, CoType >::nGen ( ) const
inline

Returns the number of generated cutting planes.

Definition at line 133 of file separator.h.

◆ operator=()

template<class BaseType , class CoType >
const Separator<BaseType, CoType>& abacus::Separator< BaseType, CoType >::operator= ( const Separator< BaseType, CoType > &  rhs)
private

◆ separate()

template<class BaseType , class CoType >
virtual void abacus::Separator< BaseType, CoType >::separate ( )
pure virtual

This function has to be redefined and should implement the separation routine.

◆ terminateSeparation()

template<class BaseType , class CoType >
virtual bool abacus::Separator< BaseType, CoType >::terminateSeparation ( )
inlinevirtual

Returns true if the separation should be terminated.

In the default implementation, this is the case if maxGen constraints/variables are in the cutBuffer.

Definition at line 124 of file separator.h.

◆ watchNonDuplPool()

template<class BaseType , class CoType >
void abacus::Separator< BaseType, CoType >::watchNonDuplPool ( NonDuplPool< BaseType, CoType > *  pool)
inline

If the separator checks for duplication of cuts, the test is also done for constraints/variables that are in the pool passed as argument.

This can be useful if already cuts are generated by performing constraint pool separation of this pool.

Definition at line 168 of file separator.h.

Member Data Documentation

◆ hash_

template<class BaseType , class CoType >
AbaHash<unsigned, BaseType*>* abacus::Separator< BaseType, CoType >::hash_
private

Definition at line 190 of file separator.h.

◆ lpSol_

template<class BaseType , class CoType >
LpSolution<CoType, BaseType>* abacus::Separator< BaseType, CoType >::lpSol_
protected

The LP solution to be separated.

Definition at line 185 of file separator.h.

◆ master_

template<class BaseType , class CoType >
Master* abacus::Separator< BaseType, CoType >::master_
protected

A pointer to the corresponding master of the optimization.

Definition at line 184 of file separator.h.

◆ minAbsViolation_

template<class BaseType , class CoType >
double abacus::Separator< BaseType, CoType >::minAbsViolation_
private

Definition at line 188 of file separator.h.

◆ nDuplications_

template<class BaseType , class CoType >
int abacus::Separator< BaseType, CoType >::nDuplications_
private

Definition at line 191 of file separator.h.

◆ newCons_

template<class BaseType , class CoType >
ArrayBuffer<BaseType*> abacus::Separator< BaseType, CoType >::newCons_
private

Definition at line 189 of file separator.h.

◆ pool_

template<class BaseType , class CoType >
NonDuplPool<BaseType, CoType>* abacus::Separator< BaseType, CoType >::pool_
private

Definition at line 193 of file separator.h.

◆ sendConstraints_

template<class BaseType , class CoType >
bool abacus::Separator< BaseType, CoType >::sendConstraints_
private

Definition at line 192 of file separator.h.


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