Forms the virtual base class for all possible constraints given in pool format. More...

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

Inheritance diagram for abacus::Constraint:

Public Member Functions
	Constraint (const Constraint &rhs)
	Copy constructor.

	Constraint (Master *master)
	Initializes an empty constraint.

	Constraint (Master master, const Sub sub, CSense::SENSE sense, double rhs, bool dynamic, bool local, bool liftable)
	Initializes a constraint.

virtual	~Constraint ()

ConClass *	classification (Active< Variable, Constraint > *var=nullptr) const
	Returns a pointer to the classification of the constraint.

virtual double	coeff (const Variable *v) const =0
	Returns the coefficient of the variable v in the constraint.

virtual double	distance (double x, Active< Variable, Constraint > actVar) const
	Returns the Euclidean distance of x associated with variable set actVar to the hyperplane induced by the constraint.

virtual int	genRow (Active< Variable, Constraint > *var, Row &row) const
	Generates the row format of the constraint associated with the variable set var.

bool	liftable () const
	Checks if the constraint is liftable.

void	printRow (std::ostream &out, Active< Variable, Constraint > *var) const
	Writes the row format of the constraint associated with the variable set var to output stream out.

virtual double	rhs () const
	Returns the right hand side of the constraint.

CSense *	sense ()
	Returns a pointer to the sense of the constraint.

const CSense *	sense () const
	Returns a const pointer to the sense of the constraint.

virtual double	slack (Active< Variable, Constraint > variables, double x) const
	Computes the slack of the vector x associated with the variable set variables.

virtual bool	valid (Sub *sub) const
	Checks if the constraint is valid for the subproblem sub.

virtual bool	violated (Active< Variable, Constraint > variables, double x, double *sl=nullptr) const
	Checks if a constraint is violated by a vector x associated with a variable set.

virtual bool	violated (double slack) const
	Checks if a constraint is violated given the slack of a vector.

Public Member Functions inherited from abacus::ConVar
	ConVar (Master master, const Sub sub, bool dynamic, bool local)
	Creates an instance of type ConVar.

virtual	~ConVar ()

bool	active () const
	Checks if the constraint/variable is active in at least one active subproblem.

virtual bool	dynamic () const
	Return true if the constraint/variable is dynamic.

virtual bool	equal (const ConVar *cv) const
	Should compare if the constraint/variable is identical (in a mathematical sense) with the constraint/variable cv.

bool	global () const
	Returns true if the constraint/variable is globally valid, false otherwise.

virtual unsigned	hashKey () const
	Should provide a key for the constraint/variable that can be used to insert it into a hash table.

bool	local () const
	Returns true if the constraint/variable is only locally valid, false otherwise.

virtual const char *	name () const
	Should return the name of the constraint/variable.

virtual void	print (std::ostream &out) const
	Writes the constraint/variable to the output stream out.

virtual double	rank () const
	The function should return a rank associated with the constraint/variable.

const Sub *	sub () const
	Returns a const pointer to the subproblem associated with the constraint/variable.

void	sub (Sub *sub)
	Associates a new subproblem with the constraint/variable.

bool	expanded () const
	Returns true if the expanded format of a constraint/variable is available, false otherwise.

virtual void	expand () const
	Expands a constraint/variable.

virtual void	compress () const
	Compresses a constraint/variable.

virtual bool	deletable () const
	Returns true if the constraint/variable can be destructed.

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

Protected Member Functions
virtual ConClass *	classify (Active< Variable, Constraint > *var) const
	The default implementation returns a 0 pointer.

virtual InfeasCon::INFEAS	voidLhsViolated (double newRhs) const
	Can be called if after variable elimination the left hand side of the constraint has become void and the right hand side has been adapted to newRhs.

Protected Attributes
ConClass *	conClass_

bool	liftable_
	This member is true if also coefficients of variables which have been inactive at generation time can be computed, false otherwise.

double	rhs_
	The right hand side of the constraint.

CSense	sense_
	The sense of the constraint.

Protected Attributes inherited from abacus::ConVar
bool	dynamic_
	If this member is true then the constraint/variable can be also removed from the active formulation after it is added the first time.

bool	expanded_
	true, if expanded version of constraint/variables available.

bool	local_
	true if the constraint/variable is only locally valid

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

int	nActive_
	The number of active subproblems of which the constraint/variable belongs to the set of active constraints/variables.

int	nLocks_
	The number of locks which have been set on the constraint/variable.

int	nReferences_
	The number of references to the pool slot the constraint is stored in.

const Sub *	sub_
	A pointer to the subproblem associated with the constraint/variable.

Private Member Functions
const Constraint &	operator= (const Constraint &rhs)

Friends
class	LpSub

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

Forms the virtual base class for all possible constraints given in pool format.

Constraints are one of the central items in a linear-programming based branch-and-bound algorithm. This class forms the virtual base class for all possible constraints given in pool format and is derived from the common base class ConVar of all constraints and variables.

Definition at line 56 of file constraint.h.

Constructor & Destructor Documentation

◆ Constraint() [1/3]

abacus::Constraint::Constraint	(	Master *	master,
		const Sub *	sub,
		CSense::SENSE	sense,
		double	rhs,
		bool	dynamic,
		bool	local,
		bool	liftable
	)

inline

Initializes a constraint.

Parameters

master	A pointer to the corresponding master of the optimization.
sub	A pointer to the subproblem associated with the constraint. This can be also a 0-pointer.
sense	The sense of the constraint.
rhs	The right hand side of the constraint.
dynamic	If this parameter is true, then the constraint can be removed from the active constraint set during the cutting plane phase of the subproblem optimization.
local	If this parameter is true, then the constraint is considered to be only locally valid. In this case the paramument sub must not be 0 as each locally valid constraint is associated with a subproblem.
liftable	If this parameter is true, then a lifting procedure must be available, i.e., that the coefficients of variables which have not been active at generation time of the constraint can be computed.

Definition at line 288 of file constraint.h.

◆ Constraint() [2/3]

abacus::Constraint::Constraint ( Master * master )

inline

Initializes an empty constraint.

This constructor is, e.g., useful if parallel separation is applied. In this case the constraint can be constructed and receive later its data by message passing.

Parameters

master A pointer to the corresponding master of the optimization.

Definition at line 305 of file constraint.h.

◆ Constraint() [3/3]

abacus::Constraint::Constraint ( const Constraint & rhs )

inline

Copy constructor.

Parameters

rhs	The constraint being copied.

Definition at line 104 of file constraint.h.

◆ ~Constraint()

virtual abacus::Constraint::~Constraint ( )

inlinevirtual

Definition at line 111 of file constraint.h.

Member Function Documentation

◆ classification()

ConClass * abacus::Constraint::classification ( Active< Variable, Constraint > * var = nullptr ) const

Returns a pointer to the classification of the constraint.

If no classification is available then we try to classify the constraint. In this case var must not be a 0-pointer.

A constraint classification can only be generated if the function classify() is redefined in a derived class.

◆ classify()

virtual ConClass * abacus::Constraint::classify ( Active< Variable, Constraint > * var ) const

inlineprotectedvirtual

The default implementation returns a 0 pointer.

Definition at line 260 of file constraint.h.

◆ coeff()

virtual double abacus::Constraint::coeff ( const Variable * v ) const

pure virtual

Returns the coefficient of the variable v in the constraint.

Parameters

v	A pointer to a variable.

Returns: The coefficient of the variable v in the constraint.

Implemented in ogdf::cluster_planarity::BaseConstraint, ogdf::cluster_planarity::ChunkConnection, ogdf::cluster_planarity::ClusterKuratowskiConstraint, ogdf::cluster_planarity::CutConstraint, ogdf::cluster_planarity::MaxPlanarEdgesConstraint, ogdf::cluster_planarity::MinimalClusterConnection, ogdf::MinSteinerTreeDirectedCut< T >::EdgeConstraint, ogdf::MinSteinerTreeDirectedCut< T >::DegreeConstraint, ogdf::MinSteinerTreeDirectedCut< T >::DegreeEdgeConstraint, ogdf::MinSteinerTreeDirectedCut< T >::DirectedCutConstraint, abacus::NumCon, and abacus::RowCon.

◆ distance()

virtual double abacus::Constraint::distance	(	double *	x,
		Active< Variable, Constraint > *	actVar
	)		const

virtual

Returns the Euclidean distance of x associated with variable set actVar to the hyperplane induced by the constraint.

The distance of a point \(\overline{x}\) and a hyperplane \(a^T x = \beta\) can be computed in the following way: Let \(y\) be the intersection of the hyperplane \(a^T x = \beta\) and the line defined by \(\overline{x}\) and the vector \(a\). Then the distance \(d\) is the length of the vector \(||\overline{x} - y||\).

Parameters

x	The point for which the distance should be computed.
actVar	The variables associated with x.

Returns: The Euclidean distance of the vector x associated with the variable set actVar to the hyperplane induced by the constraint.

◆ genRow()

virtual int abacus::Constraint::genRow	(	Active< Variable, Constraint > *	var,
		Row &	row
	)		const

virtual

Generates the row format of the constraint associated with the variable set var.

This function is declared virtual since faster constraint specific implementations might be desirable.

All nonzero coefficients are added to the row format. Before we generate the coefficients we try to expand the constraint, afterwards it is compressed again.

Parameters

var	The variable set for which the row format should be computed.
row	Stores the row format after calling this function.

Returns: The number of nonzero elements in the row format row.

Reimplemented in abacus::SRowCon.

◆ liftable()

bool abacus::Constraint::liftable ( ) const

inline

Checks if the constraint is liftable.

I.e., if the coefficients of variables inactive at generation time of the constraint can be computed later.

Returns: true If the constraint can be lifted, false otherwise.

Definition at line 140 of file constraint.h.

◆ operator=()

const Constraint & abacus::Constraint::operator= ( const Constraint & rhs )

private

◆ printRow()

void abacus::Constraint::printRow	(	std::ostream &	out,
		Active< Variable, Constraint > *	var
	)		const

Writes the row format of the constraint associated with the variable set var to output stream out.

Parameters

out	The output stream.
var	The variables for which the row format should be written.

◆ rhs()

virtual double abacus::Constraint::rhs ( ) const

inlinevirtual

Returns the right hand side of the constraint.

Definition at line 130 of file constraint.h.

◆ sense() [1/2]

CSense * abacus::Constraint::sense ( )

inline

Returns a pointer to the sense of the constraint.

Definition at line 115 of file constraint.h.

◆ sense() [2/2]

const CSense * abacus::Constraint::sense ( ) const

inline

Returns a const pointer to the sense of the constraint.

Definition at line 118 of file constraint.h.

◆ slack()

virtual double abacus::Constraint::slack	(	Active< Variable, Constraint > *	variables,
		double *	x
	)		const

virtual

Computes the slack of the vector x associated with the variable set variables.

Parameters

variables	The variable set associated with the vector x.
x	The values of the variables.

Returns: The slack induced by the vector x.

Reimplemented in abacus::SRowCon.

◆ valid()

bool abacus::Constraint::valid ( Sub * sub ) const

inlinevirtual

Checks if the constraint is valid for the subproblem sub.

Per default, this is the case if the constraint is globally valid, or the subproblem associated with the constraint is an ancestor of the subproblem sub in the enumeration tree.

Parameters

sub	The subproblem for which the validity is checked.

Returns: true If the constraint is valid for the subproblem sub, false otherwise.

Definition at line 309 of file constraint.h.

◆ violated() [1/2]

virtual bool abacus::Constraint::violated	(	Active< Variable, Constraint > *	variables,
		double *	x,
		double *	sl = `nullptr`
	)		const

virtual

Checks if a constraint is violated by a vector x associated with a variable set.

Parameters

variables	The variables associated with the vector x.
x	The vector for which the violation is checked.
sl	If sl is nonzero, then *sl will store the value of the violation, i.e., the slack.

Returns: true If the constraint is violated, false otherwise.

◆ violated() [2/2]

virtual bool abacus::Constraint::violated ( double slack ) const

virtual

Checks if a constraint is violated given the slack of a vector.

Parameters

slack The slack of a vector.

Returns: true if the constraint is an equation and the slack is nonzero.; true if the constraint is a \(\le\)-inequality and the slack is negative.; true if the constraint is a \(\ge\)-inequality and the slack is positive.; false otherwise.

◆ voidLhsViolated()

virtual InfeasCon::INFEAS abacus::Constraint::voidLhsViolated ( double newRhs ) const

protectedvirtual

Can be called if after variable elimination the left hand side of the constraint has become void and the right hand side has been adapted to newRhs.

Then this function checks if the constraint is violated.

Parameters

newRhs The right hand side of the constraint after the elimination of the variables.

Returns: TooLarge or TooSmall if the newRhs violates the sense of the constraint, i.e, it is < / > / != 0 and the sense of the constraint is >= / <= / =,; Feasible otherwise.

Friends And Related Symbol Documentation

◆ LpSub

friend class LpSub

friend

Definition at line 58 of file constraint.h.

Member Data Documentation

◆ conClass_

ConClass* abacus::Constraint::conClass_

mutableprotected

Definition at line 269 of file constraint.h.

◆ liftable_

bool abacus::Constraint::liftable_

protected

This member is true if also coefficients of variables which have been inactive at generation time can be computed, false otherwise.

Definition at line 275 of file constraint.h.

◆ rhs_

double abacus::Constraint::rhs_

protected

The right hand side of the constraint.

Definition at line 267 of file constraint.h.

◆ sense_

CSense abacus::Constraint::sense_

protected

The sense of the constraint.

Definition at line 265 of file constraint.h.

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

include/ogdf/lib/abacus/constraint.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ Constraint() [1/3]

◆ Constraint() [2/3]

◆ Constraint() [3/3]

◆ ~Constraint()

Member Function Documentation

◆ classification()

◆ classify()

◆ coeff()

◆ distance()

◆ genRow()

◆ liftable()

◆ operator=()

◆ printRow()

◆ rhs()

◆ sense() [1/2]

◆ sense() [2/2]

◆ slack()

◆ valid()

◆ violated() [1/2]

◆ violated() [2/2]

◆ voidLhsViolated()

Friends And Related Symbol Documentation

◆ LpSub

Member Data Documentation

◆ conClass_

◆ liftable_

◆ rhs_

◆ sense_

Open
Graph Drawing
Framework