Data structure to store the LP solver bounds in a sorted vector to determine the active lower and upper bound for the column. More...

#include <BoundVector.h>

Public Types
using	Bounds = SortedVector<Bound>
	Sorted vector of bounds.

Public Member Functions
	BoundVector (const mpq_class &inf_l, const mpq_class &inf_u)
	Construct a new BoundVector using `inf_l` as the the lower bound and `inf_u` as the upper bound.

BoundIterator	AddBound (const Bound &bound)
	Add a new bound to the vector.

BoundIterator	AddBound (const mpq_class &value, LpColBound lp_bound, const Literal &theory_lit, const LiteralSet &explanation={})
	Add a new bound to the vector.

bool	RemoveBound (const Bound &bound)
	Remove `bound` from the vector if it is present.

bool	RemoveBound (const mpq_class &value, LpColBound lp_bound, const Literal &theory_lit, const LiteralSet &explanation={})
	Remove the bound with the given `value`, `lp_bound`, `theory_lit` and `explanation` from the vector if it is present.

void	SetLowerBound (const mpq_class &value)
	Manually set the active lower bound to `value`.

void	SetUpperBound (const mpq_class &value)
	Manually set the active upper bound to `value`.

void	SetBounds (const mpq_class &lb, const mpq_class &ub)
	Manually set the active bounds to `lb` and `ub`.

void	Clear ()
	Clear the vector and reset the active bounds.

int	n_lower_bounds () const
	Return the number of lower bounds in the vector, both strict and non-strict.

int	n_upper_bounds () const
	Return the number of upper bounds in the vector, both strict and non-strict.

BoundIterator	GetActiveBound () const
	Return a BoundIterator containing a minimal set of bounds enclosing the interval [active_lower_bound_, active_upper_bound_] as well as all the not-equal constraints in that interval.

BoundIterator	GetActiveBound (const mpq_class &value) const
	Return a BoundIterator containing a minimal set of bounds enclosing the interval [`value`, `value`] as well as all the not-equal constraints in that interval.

BoundIterator	GetActiveBounds () const
	Return a BoundIterator containing a set of bounds enclosing the interval [active_lower_bound_, active_upper_bound_] as well as all the not-equal constraints in that interval.

BoundIterator	GetActiveBounds (const mpq_class &value) const
	Return a BoundIterator containing a set of bounds enclosing the interval [`value`, `value`] as well as all the not-equal constraints in that interval.

void	GetActiveExplanation (LiteralSet &explanation) const
	Produce a LiteralSet containing all the active bounds that can be used as an explanation.

LiteralSet	GetActiveExplanation () const
	Produce a LiteralSet containing all the active bounds that can be used as an explanation.

void	GetActiveEqExplanation (LiteralSet &explanation) const
	Produce a LiteralSet containing all the active bounds that can be used as an explanation, only if the variable presents an equality active bound.

LiteralSet	GetActiveEqExplanation () const
	Produce a LiteralSet containing all the active bounds that can be used as an explanation, only if the variable presents an equality active bound.

std::pair< const mpq_class &, const mpq_class & >	GetActiveBoundsValue () const
	Return a pair containing the active lower and upper bound.

const Bounds &	bounds () const
	Get read-only access to the bounds vector of the BoundVector.

const Bounds &	nq_bounds () const
	Get read-only access to the non-equal-to bounds vector of the BoundVector.

const mpq_class &	inf_l () const
	Get read-only access to the negative lower bound of the BoundVector.

const mpq_class &	inf_u () const
	Get read-only access to the positive infinity bound of the BoundVector.

const mpq_class &	active_lower_bound () const
	Get read-only access to the active_lower_bound of the BoundVector.

const mpq_class &	active_upper_bound () const
	Get read-only access to the active_upper_bound of the BoundVector.

const mpq_class *	GetActiveEqualityBound () const
	Return the active equality bound.

BoundIterator	ViolatedBounds (const mpq_class &value, LpColBound lp_bound) const
	Check if the combination of `value` and `lp_bound` violates any of the existing bounds.

bool	ViolatedNqBounds () const
	Check if the active bounds violate any of the existing non-equality bounds.

bool	ViolatedNqBounds (const mpq_class &lb, const mpq_class &ub) const
	Check if the new combination of `lb` and `ub` violates any of the existing non-equality bounds.

bool	IsActiveEquality (const mpq_class &value) const
	Check if `value` represents an equality bound.

bool	IsLowerBound (const mpq_class &value) const
	Check if `value` represents a lower bound.

bool	IsUpperBound (const mpq_class &value) const
	Check if `value` represents an upper bound.

bool	IsLowerBounded () const
	Check if the vector has a lower bound greater than inf_l_.

bool	IsUpperBounded () const
	Check if the vector has an upper bound lower than inf_u_.

bool	IsBounded () const
	Check if the vector has an upper bound and lower bound.

Private Member Functions
Bounds::const_iterator	LowerBoundEnd () const
	Return an iterator over bounds_ after the last lower bound and to the first upper bound.

BoundIterator	GetActiveBound (const mpq_class &lb, const mpq_class &ub) const
	Return a BoundIterator containing a minimal set of bounds enclosing the interval [`lb`, `ub`] as well as all the not-equal constraints in that interval.

BoundIterator	GetActiveBounds (const mpq_class &lb, const mpq_class &ub) const
	Return a BoundIterator containing the set of bounds enclosing the interval [`lb`, `ub`] as well as all the not-equal constraints in that interval.

Private Attributes
std::size_t	n_lower_bounds_
	Number of lower bounds, both strict and non-strict.

Bounds	bounds_
	Equality and inequality bounds.

Bounds	nq_bounds_
	Non-equality bounds.

const mpq_class *	inf_l_
	Starting lower bound.

const mpq_class *	inf_u_
	Starting upper bound.

const mpq_class *	active_lower_bound_
	Active lower bound.

const mpq_class *	active_upper_bound_
	Active upper bound.

Detailed Description

Data structure to store the LP solver bounds in a sorted vector to determine the active lower and upper bound for the column.

Every time a new bound is added, it checks if it violates any of the existing bounds. If a violation is detected, it returns the iterator to the first and last violated bound. The violating bound is not added and the vector remains unchanged.

BoundVector bounds(100);
bounds.AddBound(1, LpColBound::L, x <= 1));
bounds.AddBound(1, LpColBound::SL, 1 < x));
bounds.AddBound(1, LpColBound::L, 1 <= 1));
bounds.AddBound(1, LpColBound::SL, 1 < x));
bounds.AddBound(2, LpColBound::SL, 2 < x));
bounds.AddBound(2, LpColBound::L, 2 <= x));
// No violations so far.
auto violation = bounds.AddBound(1, LpColBound::U, x <= 1);
for (; violation; ++violation) {
 std::cout << *violation << std::endl;
}
// Output:
// (1, SL, 1 < x), (1, SL, 1 < x), (2, L, 2 < x), (2, SL, 2 <= x)

Definition at line 48 of file BoundVector.h.

Constructor & Destructor Documentation

◆ BoundVector()

dlinear::BoundVector::BoundVector	(	const mpq_class &	inf_l,
		const mpq_class &	inf_u )

Construct a new BoundVector using inf_l as the the lower bound and inf_u as the upper bound.

Parameters

inf_l	lower bound
inf_u	upper bound

Definition at line 27 of file BoundVector.cpp.

Member Function Documentation

◆ active_lower_bound()

const mpq_class & dlinear::BoundVector::active_lower_bound ( ) const

inlinenodiscard

Get read-only access to the active_lower_bound of the BoundVector.

Returns: active_lower_bound of the BoundVector

Definition at line 225 of file BoundVector.h.

◆ active_upper_bound()

const mpq_class & dlinear::BoundVector::active_upper_bound ( ) const

inlinenodiscard

Get read-only access to the active_upper_bound of the BoundVector.

Returns: active_upper_bound of the BoundVector

Definition at line 227 of file BoundVector.h.

◆ AddBound() [1/2]

BoundIterator dlinear::BoundVector::AddBound ( const Bound & bound )

Add a new bound to the vector.

The bound will be sorted in the vector according to its value and type with the goal of identifying violating bounds as fast a possible.

Note: If a violation is detected, the bound will not be added. The vector will remain unchanged.

Parameters

bound bound to add

Returns: empty BoundIterator if the bound has been added successfully; BoundIterator containing all the violated bounds in the vector

See also: AddBound(const mpq_class&, LpColBound, int)

Definition at line 36 of file BoundVector.cpp.

◆ AddBound() [2/2]

BoundIterator dlinear::BoundVector::AddBound	(	const mpq_class &	value,
		LpColBound	lp_bound,
		const Literal &	theory_lit,
		const LiteralSet &	explanation = {} )

Add a new bound to the vector.

The bound will be sorted in the vector according to its value and type with the goal of identifying violating bounds as fast a possible. The idx it is ignored by the BoundVector, but can be used by the caller to identify the bound. Before adding a new bound, a check is performed to ensure it does not violate any of the existing bounds. If a violation is detected, a BoundIterator containing all the violated bounds is returned instead.

Note: If a violation is detected, the bound will not be added. The vector will remain unchanged.

Parameters

value	value of the new bound
lp_bound	type of the new bound
theory_lit	theory literal associated with the bound
explanation	set of theory literals justifying the existence of the bound

Returns: empty BoundIterator if the bound has been added successfully; BoundIterator containing all the violated bounds in the vector

Definition at line 39 of file BoundVector.cpp.

◆ bounds()

const Bounds & dlinear::BoundVector::bounds ( ) const

inlinenodiscard

Get read-only access to the bounds vector of the BoundVector.

Returns: bounds vector of the BoundVector

Definition at line 217 of file BoundVector.h.

◆ Clear()

void dlinear::BoundVector::Clear ( )

Clear the vector and reset the active bounds.

Active bounds are set to inf_l_ and inf_u_.

Definition at line 216 of file BoundVector.cpp.

◆ GetActiveBound() [1/3]

BoundIterator dlinear::BoundVector::GetActiveBound ( ) const

nodiscard

Return a BoundIterator containing a minimal set of bounds enclosing the interval [active_lower_bound_, active_upper_bound_] as well as all the not-equal constraints in that interval.

Returns: iterator over the active bounds

See also: GetActiveBounds

Definition at line 259 of file BoundVector.cpp.

◆ GetActiveBound() [2/3]

BoundIterator dlinear::BoundVector::GetActiveBound	(	const mpq_class &	lb,
		const mpq_class &	ub ) const

nodiscardprivate

Return a BoundIterator containing a minimal set of bounds enclosing the interval [lb, ub] as well as all the not-equal constraints in that interval.

Precondition: (lb == active_lower_bound_ && ub == active_upper_bound_) || lb == ub

dlinear::BoundVector::active_upper_bound_
const mpq_class * active_upper_bound_
Active upper bound.
Definition BoundVector.h:345

dlinear::BoundVector::active_lower_bound_
const mpq_class * active_lower_bound_
Active lower bound.
Definition BoundVector.h:344; lb <= ub

Parameters

lb	lower bound
ub	upper bound

Returns: iterator over the active bounds

Definition at line 261 of file BoundVector.cpp.

◆ GetActiveBound() [3/3]

BoundIterator dlinear::BoundVector::GetActiveBound ( const mpq_class & value ) const

nodiscard

Return a BoundIterator containing a minimal set of bounds enclosing the interval [value, value] as well as all the not-equal constraints in that interval.

Parameters

value value to check

Returns: iterator over the active bounds

See also: GetActiveBounds

Definition at line 260 of file BoundVector.cpp.

◆ GetActiveBounds() [1/3]

BoundIterator dlinear::BoundVector::GetActiveBounds ( ) const

nodiscard

Return a BoundIterator containing a set of bounds enclosing the interval [active_lower_bound_, active_upper_bound_] as well as all the not-equal constraints in that interval.

Note: Equality bounds will hide not matching inequality bounds.

Returns: iterator over the active bounds

See also: GetActiveBound

Definition at line 276 of file BoundVector.cpp.

◆ GetActiveBounds() [2/3]

BoundIterator dlinear::BoundVector::GetActiveBounds	(	const mpq_class &	lb,
		const mpq_class &	ub ) const

nodiscardprivate

Return a BoundIterator containing the set of bounds enclosing the interval [lb, ub] as well as all the not-equal constraints in that interval.

Note: Equality bounds will hide not matching inequality bounds.

Precondition: (lb == active_lower_bound_ && ub == active_upper_bound_) || lb == ub; lb <= ub

Parameters

lb	lower bound
ub	upper bound

Returns: iterator over the active bounds

Definition at line 280 of file BoundVector.cpp.

◆ GetActiveBounds() [3/3]

BoundIterator dlinear::BoundVector::GetActiveBounds ( const mpq_class & value ) const

nodiscard

Return a BoundIterator containing a set of bounds enclosing the interval [value, value] as well as all the not-equal constraints in that interval.

Parameters

value value to check

Note: Equality bounds will hide not matching inequality bounds.

Returns: iterator over the active bounds

See also: GetActiveBound

Definition at line 279 of file BoundVector.cpp.

◆ GetActiveBoundsValue()

std::pair< const mpq_class &, const mpq_class & > dlinear::BoundVector::GetActiveBoundsValue ( ) const

nodiscard

Return a pair containing the active lower and upper bound.

Returns: active lower and upper bound

Definition at line 331 of file BoundVector.cpp.

◆ GetActiveEqExplanation() [1/2]

LiteralSet dlinear::BoundVector::GetActiveEqExplanation ( ) const

nodiscard

Produce a LiteralSet containing all the active bounds that can be used as an explanation, only if the variable presents an equality active bound.

Returns: set of literal corresponding to the explanation

See also: GetActiveExplanation

Definition at line 318 of file BoundVector.cpp.

◆ GetActiveEqExplanation() [2/2]

void dlinear::BoundVector::GetActiveEqExplanation ( LiteralSet & explanation ) const

Produce a LiteralSet containing all the active bounds that can be used as an explanation, only if the variable presents an equality active bound.

Parameters

explanation set of literal corresponding to the explanation

See also: GetActiveExplanation

Definition at line 323 of file BoundVector.cpp.

◆ GetActiveEqualityBound()

const mpq_class * dlinear::BoundVector::GetActiveEqualityBound ( ) const

inlinenodiscard

Return the active equality bound.

An active equality bound is obtained when the active lower bound is equal to the active upper bound. If such condition is false, a nullptr is returned.

Returns: active equality bound if the active lower bound is equal to the active upper bound; nullptr if the active lower bound is not equal to the active upper bound

Definition at line 237 of file BoundVector.h.

◆ GetActiveExplanation() [1/2]

LiteralSet dlinear::BoundVector::GetActiveExplanation ( ) const

nodiscard

Produce a LiteralSet containing all the active bounds that can be used as an explanation.

Parameters

theory_bound_to_lit map between the bound id and the theory literal

Returns: set of literal corresponding to the explanation

Definition at line 307 of file BoundVector.cpp.

◆ GetActiveExplanation() [2/2]

void dlinear::BoundVector::GetActiveExplanation ( LiteralSet & explanation ) const

Produce a LiteralSet containing all the active bounds that can be used as an explanation.

Parameters

explanation set of literal corresponding to the explanation

Definition at line 312 of file BoundVector.cpp.

◆ inf_l()

const mpq_class & dlinear::BoundVector::inf_l ( ) const

inlinenodiscard

Get read-only access to the negative lower bound of the BoundVector.

Returns: negative lower bound of the BoundVector

Definition at line 221 of file BoundVector.h.

◆ inf_u()

const mpq_class & dlinear::BoundVector::inf_u ( ) const

inlinenodiscard

Get read-only access to the positive infinity bound of the BoundVector.

Returns: positive infinity bound of the BoundVector

Definition at line 223 of file BoundVector.h.

◆ IsActiveEquality()

bool dlinear::BoundVector::IsActiveEquality ( const mpq_class & value ) const

nodiscard

Check if value represents an equality bound.

Parameters

value value to check

Returns: true if value represents an equality bound; false if value does not represent an equality bound

Definition at line 224 of file BoundVector.cpp.

◆ IsBounded()

bool dlinear::BoundVector::IsBounded ( ) const

nodiscard

Check if the vector has an upper bound and lower bound.

Returns: true if the upper bound is < inf_u_ and the lower bound is > inf_l_; false if the upper bound is = inf_u_ or the lower bound is = inf_l_

See also: IsLowerBounded; IsUpperBounded

Definition at line 253 of file BoundVector.cpp.

◆ IsLowerBound()

bool dlinear::BoundVector::IsLowerBound ( const mpq_class & value ) const

nodiscard

Check if value represents a lower bound.

Parameters

value value to check

Returns: true if value represents a lower bound; false if value does not represent a lower bound

Definition at line 229 of file BoundVector.cpp.

◆ IsLowerBounded()

bool dlinear::BoundVector::IsLowerBounded ( ) const

nodiscard

Check if the vector has a lower bound greater than inf_l_.

Returns: true if the upper bound is > inf_l_; false if the upper bound is = inf_l_

Definition at line 243 of file BoundVector.cpp.

◆ IsUpperBound()

bool dlinear::BoundVector::IsUpperBound ( const mpq_class & value ) const

nodiscard

Check if value represents an upper bound.

Parameters

value value to check

Returns: true if value represents an upper bound; false if value does not represent an upper bound

Definition at line 236 of file BoundVector.cpp.

◆ IsUpperBounded()

bool dlinear::BoundVector::IsUpperBounded ( ) const

nodiscard

Check if the vector has an upper bound lower than inf_u_.

Returns: true if the upper bound is < inf_u_; false if the upper bound is = inf_u_

Definition at line 248 of file BoundVector.cpp.

◆ LowerBoundEnd()

BoundVector::Bounds::const_iterator dlinear::BoundVector::LowerBoundEnd ( ) const

nodiscardprivate

Return an iterator over bounds_ after the last lower bound and to the first upper bound.

Returns: iterator after the last lower bound and to the first upper bound

Definition at line 255 of file BoundVector.cpp.

◆ n_lower_bounds()

int dlinear::BoundVector::n_lower_bounds ( ) const

inlinenodiscard

Return the number of lower bounds in the vector, both strict and non-strict.

Returns: number of lower bounds

Definition at line 146 of file BoundVector.h.

◆ n_upper_bounds()

int dlinear::BoundVector::n_upper_bounds ( ) const

inlinenodiscard

Return the number of upper bounds in the vector, both strict and non-strict.

Returns: number of upper bounds

Definition at line 151 of file BoundVector.h.

◆ nq_bounds()

const Bounds & dlinear::BoundVector::nq_bounds ( ) const

inlinenodiscard

Get read-only access to the non-equal-to bounds vector of the BoundVector.

Returns: non-equal-to bounds vector of the BoundVector

Definition at line 219 of file BoundVector.h.

◆ RemoveBound() [1/2]

bool dlinear::BoundVector::RemoveBound ( const Bound & bound )

Remove bound from the vector if it is present.

Parameters

bound bound to remove

Returns: true if the bound has been removed; false if the bound has not been found

Definition at line 107 of file BoundVector.cpp.

◆ RemoveBound() [2/2]

bool dlinear::BoundVector::RemoveBound	(	const mpq_class &	value,
		LpColBound	lp_bound,
		const Literal &	theory_lit,
		const LiteralSet &	explanation = {} )

Remove the bound with the given value, lp_bound, theory_lit and explanation from the vector if it is present.

Parameters

value	value of the bound
lp_bound	type of the bound
theory_lit	theory literal associated with the bound
explanation	set of theory literals justifying the existence of the bound

Returns: true if the bound has been removed; false if the bound has not been found

Definition at line 103 of file BoundVector.cpp.

◆ SetBounds()

void dlinear::BoundVector::SetBounds	(	const mpq_class &	lb,
		const mpq_class &	ub )

Manually set the active bounds to lb and ub.

The active bounds will be set to lb and ub only if lb is greater than the active lower bound and ub is less than the active upper bound respectively.

Parameters

lb	new lower bound
ub	new upper bound

Exceptions

std::runtime_error if after setting the bounds, the lower bound is greater than the upper bound

Definition at line 347 of file BoundVector.cpp.

◆ SetLowerBound()

void dlinear::BoundVector::SetLowerBound ( const mpq_class & value )

Manually set the active lower bound to value.

The method won't have any effect if value is less than the active lower bound.

Parameters

value value of the new lower bound

Exceptions

std::runtime_error if the value is greater than the active upper bound

Definition at line 335 of file BoundVector.cpp.

◆ SetUpperBound()

void dlinear::BoundVector::SetUpperBound ( const mpq_class & value )

Manually set the active upper bound to value.

The method won't have any effect if value is greater than the active upper bound.

Parameters

value value of the new upper bound

Exceptions

std::runtime_error if the value is less than the active lower bound

Definition at line 341 of file BoundVector.cpp.

◆ ViolatedBounds()

BoundIterator dlinear::BoundVector::ViolatedBounds	(	const mpq_class &	value,
		LpColBound	lp_bound ) const

nodiscard

Check if the combination of value and lp_bound violates any of the existing bounds.

If that is the case, a non-empty BoundIterator containing all the violated bounds is returned.

Parameters

value	value of the bound
lp_bound	type of the bound

Returns: empty BoundIterator if the bound does not violate any of the existing bounds; BoundIterator containing all the violated existing bounds

Definition at line 147 of file BoundVector.cpp.

◆ ViolatedNqBounds() [1/2]

bool dlinear::BoundVector::ViolatedNqBounds ( ) const

nodiscard

Check if the active bounds violate any of the existing non-equality bounds.

Returns: true if the active bounds violate any of the existing non-equality bounds; false if no violation is detected

Definition at line 196 of file BoundVector.cpp.

◆ ViolatedNqBounds() [2/2]

bool dlinear::BoundVector::ViolatedNqBounds	(	const mpq_class &	lb,
		const mpq_class &	ub ) const

nodiscard

Check if the new combination of lb and ub violates any of the existing non-equality bounds.

Parameters

lb	lower bound
ub	upper bound

Returns: true if the new combination of lb and ub violates any of the existing non-equality bounds; false if no violation is detected

Definition at line 206 of file BoundVector.cpp.

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

dlinear/solver/BoundVector.h
dlinear/solver/BoundVector.cpp

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ BoundVector()

Member Function Documentation

◆ active_lower_bound()

◆ active_upper_bound()

◆ AddBound() [1/2]

◆ AddBound() [2/2]

◆ bounds()

◆ Clear()

◆ GetActiveBound() [1/3]

◆ GetActiveBound() [2/3]

◆ GetActiveBound() [3/3]

◆ GetActiveBounds() [1/3]

◆ GetActiveBounds() [2/3]

◆ GetActiveBounds() [3/3]

◆ GetActiveBoundsValue()

◆ GetActiveEqExplanation() [1/2]

◆ GetActiveEqExplanation() [2/2]

◆ GetActiveEqualityBound()

◆ GetActiveExplanation() [1/2]

◆ GetActiveExplanation() [2/2]

◆ inf_l()

◆ inf_u()

◆ IsActiveEquality()

◆ IsBounded()

◆ IsLowerBound()

◆ IsLowerBounded()

◆ IsUpperBound()

◆ IsUpperBounded()

◆ LowerBoundEnd()

◆ n_lower_bounds()

◆ n_upper_bounds()

◆ nq_bounds()

◆ RemoveBound() [1/2]

◆ RemoveBound() [2/2]

◆ SetBounds()

◆ SetLowerBound()

◆ SetUpperBound()

◆ ViolatedBounds()

◆ ViolatedNqBounds() [1/2]

◆ ViolatedNqBounds() [2/2]