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...

Master *	master_
	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

lpSolution	The LP solution to be separated.
maxGen	The maximal number of cutting planes which are stored.
nonDuplications	If 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

cv	A 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

cv	A 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:

include/ogdf/lib/abacus/lpsolution.h
include/ogdf/lib/abacus/separator.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

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

Constructor & Destructor Documentation

◆ Separator() [1/2]

◆ ~Separator()

◆ Separator() [2/2]

Member Function Documentation

◆ cutBuffer()

◆ cutFound()

◆ find()

◆ lpSolution()

◆ maxGen()

◆ minAbsViolation() [1/2]

◆ minAbsViolation() [2/2]

◆ nCollisions()

◆ nDuplications()

◆ nGen()

◆ operator=()

◆ separate()

◆ terminateSeparation()

◆ watchNonDuplPool()

Member Data Documentation

◆ hash_

◆ lpSol_

◆ master_

◆ minAbsViolation_

◆ nDuplications_

◆ newCons_

◆ pool_

◆ sendConstraints_

Open
Graph Drawing
Framework

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