Separators. More...

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

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

Public Member Functions
	Separator (LpSolution< CoType, BaseType > *lpSolution, bool nonDuplications, int maxGen=300)
	Creates a separator.

virtual	~Separator ()
	The destructor.

ArrayBuffer< BaseType * > &	cutBuffer ()
	Returns the buffer with the generated constraints/variable.

Separator_CUTFOUND	cutFound (BaseType *cv)
	Passes a cut (constraint or variable) to the buffer.

LpSolution< CoType, BaseType > *	lpSolution ()
	The lpSolution to be separated.

int	maxGen () const
	Returns the maximal number of generated cutting planes.

double	minAbsViolation () const
	Returns the absolute value for considering a constraint/variable as violated.

void	minAbsViolation (double minAbsVio)
	Sets a new value for minAbsViolation.

int	nCollisions () const
	Returns the number of collisions in the hash table.

int	nDuplications () const
	Returns the number of duplicated constraints/variables which are discarded.

int	nGen () const
	Returns the number of generated cutting planes.

virtual void	separate ()=0
	This function has to be redefined and should implement the separation routine.

virtual bool	terminateSeparation ()
	Returns true if the separation should be terminated.

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.

Public Member Functions inherited from abacus::AbacusRoot
virtual	~AbacusRoot ()
	The destructor.

Protected Member Functions
bool	find (BaseType *cv)

Protected Attributes
LpSolution< CoType, BaseType > *	lpSol_
	The LP solution to be separated.

Master *	master_
	A pointer to the corresponding master of the optimization.

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_

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::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 66 of file separator.h.

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.

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

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