#include <CeresEngine/Foundation/Constraint/ConstraintSolver.hpp>

Classes
struct	DualOptimizeGuard

struct	EditInfo
	A structure that holds information for an edit variable. More...

class	Row

struct	RowDeleter

class	Symbol

struct	Tag
	A tag that represents a symbol on the tableau. More...

Public Member Functions
	ConstraintSolver ()

	ConstraintSolver (const ConstraintSolver &)=delete

ConstraintSolver &	operator= (const ConstraintSolver &)=delete

	ConstraintSolver (ConstraintSolver &&)=delete

ConstraintSolver &	operator= (ConstraintSolver &&)=delete

	~ConstraintSolver ()

void	addConstraint (const Constraint &constraint)
	Add a constraint to the solver.

void	addConstraints (const Span< const Constraint > &constraints)

void	addConstraints (const InitializerList< Constraint > constraints)

void	removeConstraint (const Constraint &constraint)
	Remove a constraint from the solver.

void	removeConstraints (const Span< const Constraint > &constraints)

void	removeConstraints (const InitializerList< Constraint > constraints)

bool	hasConstraint (const Constraint &constraint) const
	Test whether a constraint has been added to the solver.

void	addEditVariable (const ConstraintVariable &variable, const ConstraintStrength &strength)
	Add an edit variable to the solver.

void	removeEditVariable (const ConstraintVariable &variable)
	Remove an edit variable from the solver.

bool	hasEditVariable (const ConstraintVariable &variable) const
	Test whether an edit variable has been added to the solver.

void	suggestValue (const ConstraintVariable &variable, double value)
	Suggest a value for the given edit variable.

void	updateVariables ()
	Update the values of the external solver variables.

void	reset ()
	Reset the solver to the empty starting condition.

void	solve ()
	Solves the constraint on the solver.

Private Types
template<typename K , typename V , typename C = std::less<K>, typename A = DefaultAllocator>
using	MapType = SmallFlatMap< K, V, 0, C, A >

using	SymbolID = UInt64

using	VarMap = MapType< ConstraintVariable, Symbol >

using	RowMap = MapType< Symbol, Row * >

using	ConstaintMap = MapType< Constraint, Tag >

using	EditMap = MapType< ConstraintVariable, EditInfo >

Private Member Functions
void	clearRows ()

Symbol	getVarSymbol (const ConstraintVariable &variable)
	Get the symbol for the given variable.

UPtr< Row >	createRow (const Constraint &constraint, Tag &tag)
	Create a new Row object for the given constraint.

Symbol	chooseSubject (const Row &row, const Tag &tag) const
	Choose the subject for solving for the row.

bool	addWithArtificialVariable (const Row &row)
	Add the row to the tableau using an artificial variable.

void	substitute (const Symbol &symbol, const Row &row)
	Substitute the parametric symbol with the given row.

void	optimize (const Row &objective)
	Optimize the system for the given objective function.

void	dualOptimize ()
	Optimize the system using the dual of the simplex method.

Symbol	getEnteringSymbol (const Row &objective) const
	Compute the entering variable for a pivot operation.

Symbol	getDualEnteringSymbol (const Row &row) const
	Compute the entering symbol for the dual optimize operation.

Symbol	anyPivotableSymbol (const Row &row) const
	Get the first Slack or Error symbol in the row.

RowMap::iterator	getLeavingRow (const Symbol &entering)
	Compute the row which holds the exit symbol for a pivot.

RowMap::iterator	getMarkerLeavingRow (const Symbol &marker)
	Compute the leaving row for a marker variable.

void	removeConstraintEffects (const Constraint &cn, const Tag &tag)
	Remove the effects of a constraint on the objective function.

void	removeMarkerEffects (const Symbol &marker, const ConstraintStrength &strength)
	Remove the effects of an error marker on the objective function.

bool	allDummies (const Row &row) const
	Test whether a row is composed of all dummy variables.

Private Attributes
ConstaintMap	mConstraints

RowMap	mRows

VarMap	mVariables

EditMap	mEditVariables

Vector< Symbol >	mInfeasibleRows

UPtr< Row >	mObjective

UPtr< Row >	mArtificial

SymbolID	mNextID

bool	mAutoSolve = false

Member Typedef Documentation

◆ ConstaintMap

using CeresEngine::Constraint::ConstraintSolver::ConstaintMap = MapType<Constraint, Tag>

private

◆ EditMap

using CeresEngine::Constraint::ConstraintSolver::EditMap = MapType<ConstraintVariable, EditInfo>

private

◆ MapType

template<typename K , typename V , typename C = std::less<K>, typename A = DefaultAllocator>

using CeresEngine::Constraint::ConstraintSolver::MapType = SmallFlatMap<K, V, 0, C, A>

private

◆ RowMap

using CeresEngine::Constraint::ConstraintSolver::RowMap = MapType<Symbol, Row*>

private

◆ SymbolID

using CeresEngine::Constraint::ConstraintSolver::SymbolID = UInt64

private

◆ VarMap

using CeresEngine::Constraint::ConstraintSolver::VarMap = MapType<ConstraintVariable, Symbol>

private

Constructor & Destructor Documentation

◆ ConstraintSolver() [1/3]

CeresEngine::Constraint::ConstraintSolver::ConstraintSolver ( )

inline

◆ ConstraintSolver() [2/3]

CeresEngine::Constraint::ConstraintSolver::ConstraintSolver ( const ConstraintSolver & )

delete

◆ ConstraintSolver() [3/3]

CeresEngine::Constraint::ConstraintSolver::ConstraintSolver ( ConstraintSolver && )

delete

◆ ~ConstraintSolver()

CeresEngine::Constraint::ConstraintSolver::~ConstraintSolver ( )

inline

Member Function Documentation

◆ addConstraint()

void CeresEngine::Constraint::ConstraintSolver::addConstraint ( const Constraint & constraint )

Add a constraint to the solver.

Exceptions

DuplicateConstraint	The given constraint has already been added to the solver.
UnsatisfiableConstraint	The given constraint is required and cannot be satisfied.

◆ addConstraints() [1/2]

void CeresEngine::Constraint::ConstraintSolver::addConstraints ( const InitializerList< Constraint > constraints )

inline

◆ addConstraints() [2/2]

void CeresEngine::Constraint::ConstraintSolver::addConstraints ( const Span< const Constraint > & constraints )

inline

◆ addEditVariable()

void CeresEngine::Constraint::ConstraintSolver::addEditVariable	(	const ConstraintVariable &	variable,
		const ConstraintStrength &	strength
	)

Add an edit variable to the solver.

This method should be called before the suggestValue method is used to supply a suggested value for the given edit variable.

Exceptions

DuplicateEditVariable	The given edit variable has already been added to the solver.
BadRequiredStrength	The given strength is >= required.

◆ addWithArtificialVariable()

bool CeresEngine::Constraint::ConstraintSolver::addWithArtificialVariable ( const Row & row )

private

Add the row to the tableau using an artificial variable.

This will return false if the constraint cannot be satisfied.

◆ allDummies()

bool CeresEngine::Constraint::ConstraintSolver::allDummies ( const Row & row ) const

private

Test whether a row is composed of all dummy variables.

◆ anyPivotableSymbol()

Symbol CeresEngine::Constraint::ConstraintSolver::anyPivotableSymbol ( const Row & row ) const

private

Get the first Slack or Error symbol in the row.

If no such symbol is present, and Invalid symbol will be returned.

◆ chooseSubject()

Symbol CeresEngine::Constraint::ConstraintSolver::chooseSubject	(	const Row &	row,
		const Tag &	tag
	)		const

private

Choose the subject for solving for the row.

This method will choose the best subject for using as the solve target for the row. An invalid symbol will be returned if there is no valid target.

The symbols are chosen according to the following precedence: 1) The first symbol representing an external variable. 2) A negative slack or error tag variable.

If a subject cannot be found, an invalid symbol will be returned.

◆ clearRows()

void CeresEngine::Constraint::ConstraintSolver::clearRows ( )

inlineprivate

◆ createRow()

UPtr< Row > CeresEngine::Constraint::ConstraintSolver::createRow	(	const Constraint &	constraint,
		Tag &	tag
	)

private

Create a new Row object for the given constraint.

The terms in the constraint will be converted to cells in the row. Any term in the constraint with a coefficient of zero is ignored. This method uses the getVarSymbol method to get the symbol for the variables added to the row. If the symbol for a given cell variable is basic, the cell variable will be substituted with the basic row.

The necessary slack and error variables will be added to the row. If the constant for the row is negative, the sign for the row will be inverted so the constant becomes positive.

The tag will be updated with the marker and error symbols to use for tracking the movement of the constraint in the tableau.

◆ dualOptimize()

void CeresEngine::Constraint::ConstraintSolver::dualOptimize ( )

private

Optimize the system using the dual of the simplex method.

The current state of the system should be such that the objective function is optimal, but not feasible. This method will perform an iteration of the dual simplex method to make the solution both optimal and feasible.

Exceptions

InternalSolverError The system cannot be dual optimized.

◆ getDualEnteringSymbol()

Symbol CeresEngine::Constraint::ConstraintSolver::getDualEnteringSymbol ( const Row & row ) const

private

Compute the entering symbol for the dual optimize operation.

This method will return the symbol in the row which has a positive coefficient and yields the minimum ratio for its respective symbol in the objective function. The provided row must be infeasible.

If no symbol is found which meats the criteria, an invalid symbol is returned.

◆ getEnteringSymbol()

Symbol CeresEngine::Constraint::ConstraintSolver::getEnteringSymbol ( const Row & objective ) const

private

Compute the entering variable for a pivot operation.

This method will return first symbol in the objective function which is non-dummy and has a coefficient less than zero. If no symbol meets the criteria, it means the objective function is at a minimum, and an invalid symbol is returned.

◆ getLeavingRow()

RowMap::iterator CeresEngine::Constraint::ConstraintSolver::getLeavingRow ( const Symbol & entering )

private

Compute the row which holds the exit symbol for a pivot.

This method will return an iterator to the row in the row map which holds the exit symbol. If no appropriate exit symbol is found, the end() iterator will be returned. This indicates that the objective function is unbounded.

◆ getMarkerLeavingRow()

RowMap::iterator CeresEngine::Constraint::ConstraintSolver::getMarkerLeavingRow ( const Symbol & marker )

private

Compute the leaving row for a marker variable.

This method will return an iterator to the row in the row map which holds the given marker variable. The row will be chosen according to the following precedence: 1) The row with a restricted basic varible and a negative coefficient for the marker with the smallest ratio of -constant / coefficient. 2) The row with a restricted basic variable and the smallest ratio of constant / coefficient. 3) The last unrestricted row which contains the marker.

If the marker does not exist in any row, the row map end() iterator will be returned. This indicates an internal solver error since the marker should exist somewhere in the tableau.

◆ getVarSymbol()

Symbol CeresEngine::Constraint::ConstraintSolver::getVarSymbol ( const ConstraintVariable & variable )

private

Get the symbol for the given variable.

If a symbol does not exist for the variable, one will be created.

◆ hasConstraint()

bool CeresEngine::Constraint::ConstraintSolver::hasConstraint ( const Constraint & constraint ) const

inline

Test whether a constraint has been added to the solver.

◆ hasEditVariable()

bool CeresEngine::Constraint::ConstraintSolver::hasEditVariable ( const ConstraintVariable & variable ) const

inline

Test whether an edit variable has been added to the solver.

◆ operator=() [1/2]

ConstraintSolver & CeresEngine::Constraint::ConstraintSolver::operator= ( const ConstraintSolver & )

delete

◆ operator=() [2/2]

ConstraintSolver & CeresEngine::Constraint::ConstraintSolver::operator= ( ConstraintSolver && )

delete

◆ optimize()

void CeresEngine::Constraint::ConstraintSolver::optimize ( const Row & objective )

private

Optimize the system for the given objective function.

This method performs iterations of Phase 2 of the simplex method until the objective function reaches a minimum.

Exceptions

InternalSolverError The value of the objective function is unbounded.

◆ removeConstraint()

void CeresEngine::Constraint::ConstraintSolver::removeConstraint ( const Constraint & constraint )

Remove a constraint from the solver.

Exceptions

UnknownConstraint The given constraint has not been added to the solver.

◆ removeConstraintEffects()

void CeresEngine::Constraint::ConstraintSolver::removeConstraintEffects	(	const Constraint &	cn,
		const Tag &	tag
	)

private

Remove the effects of a constraint on the objective function.

◆ removeConstraints() [1/2]

void CeresEngine::Constraint::ConstraintSolver::removeConstraints ( const InitializerList< Constraint > constraints )

inline

◆ removeConstraints() [2/2]

void CeresEngine::Constraint::ConstraintSolver::removeConstraints ( const Span< const Constraint > & constraints )

inline

◆ removeEditVariable()

void CeresEngine::Constraint::ConstraintSolver::removeEditVariable ( const ConstraintVariable & variable )

Remove an edit variable from the solver.

Exceptions

UnknownEditVariable The given edit variable has not been added to the solver.

◆ removeMarkerEffects()

void CeresEngine::Constraint::ConstraintSolver::removeMarkerEffects	(	const Symbol &	marker,
		const ConstraintStrength &	strength
	)

private

Remove the effects of an error marker on the objective function.

◆ reset()

void CeresEngine::Constraint::ConstraintSolver::reset ( )

Reset the solver to the empty starting condition.

This method resets the internal solver state to the empty starting condition, as if no constraints or edit variables have been added.

This can be faster than deleting the solver and creating a new one when the entire system must change, since it can avoid unecessary heap (de)allocations.

◆ solve()

void CeresEngine::Constraint::ConstraintSolver::solve ( )

Solves the constraint on the solver.

◆ substitute()

void CeresEngine::Constraint::ConstraintSolver::substitute	(	const Symbol &	symbol,
		const Row &	row
	)

private

Substitute the parametric symbol with the given row.

This method will substitute all instances of the parametric symbol in the tableau and the objective function with the given row.

◆ suggestValue()

void CeresEngine::Constraint::ConstraintSolver::suggestValue	(	const ConstraintVariable &	variable,
		double	value
	)

Suggest a value for the given edit variable.

This method should be used after an edit variable as been added to the solver in order to suggest the value for that variable.

Exceptions

UnknownEditVariable The given edit variable has not been added to the solver.

◆ updateVariables()

void CeresEngine::Constraint::ConstraintSolver::updateVariables ( )

Update the values of the external solver variables.

Member Data Documentation

◆ mArtificial

UPtr<Row> CeresEngine::Constraint::ConstraintSolver::mArtificial

private

◆ mAutoSolve

bool CeresEngine::Constraint::ConstraintSolver::mAutoSolve = false

private

◆ mConstraints

ConstaintMap CeresEngine::Constraint::ConstraintSolver::mConstraints

private

◆ mEditVariables

EditMap CeresEngine::Constraint::ConstraintSolver::mEditVariables

private

◆ mInfeasibleRows

Vector<Symbol> CeresEngine::Constraint::ConstraintSolver::mInfeasibleRows

private

◆ mNextID

SymbolID CeresEngine::Constraint::ConstraintSolver::mNextID

private

◆ mObjective

UPtr<Row> CeresEngine::Constraint::ConstraintSolver::mObjective

private

◆ mRows

RowMap CeresEngine::Constraint::ConstraintSolver::mRows

private

◆ mVariables

VarMap CeresEngine::Constraint::ConstraintSolver::mVariables

private

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

/Users/Rogiel/Developer/CeresEngine/Engine/Sources/CeresEngine/Foundation/Constraint/ConstraintSolver.hpp

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Member Typedef Documentation

◆ ConstaintMap

◆ EditMap

◆ MapType

◆ RowMap

◆ SymbolID

◆ VarMap

Constructor & Destructor Documentation

◆ ConstraintSolver() [1/3]

◆ ConstraintSolver() [2/3]

◆ ConstraintSolver() [3/3]

◆ ~ConstraintSolver()

Member Function Documentation

◆ addConstraint()

◆ addConstraints() [1/2]

◆ addConstraints() [2/2]

◆ addEditVariable()

◆ addWithArtificialVariable()

◆ allDummies()

◆ anyPivotableSymbol()

◆ chooseSubject()

◆ clearRows()

◆ createRow()

◆ dualOptimize()

◆ getDualEnteringSymbol()

◆ getEnteringSymbol()

◆ getLeavingRow()

◆ getMarkerLeavingRow()

◆ getVarSymbol()

◆ hasConstraint()

◆ hasEditVariable()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ optimize()

◆ removeConstraint()

◆ removeConstraintEffects()

◆ removeConstraints() [1/2]

◆ removeConstraints() [2/2]

◆ removeEditVariable()

◆ removeMarkerEffects()

◆ reset()

◆ solve()

◆ substitute()

◆ suggestValue()

◆ updateVariables()

Member Data Documentation

◆ mArtificial

◆ mAutoSolve

◆ mConstraints

◆ mEditVariables

◆ mInfeasibleRows

◆ mNextID

◆ mObjective

◆ mRows

◆ mVariables