operations_research::sat::BinaryRelationRepository Class Reference

Detailed Description

A repository of all the enforced linear constraints of size 1 or 2, and of all the non-enforced linear constraints of size 2.

Todo

(user): This is not always needed, find a way to clean this once we don't need it.

Definition at line 516 of file precedences.h.

#include <precedences.h>

Public Member Functions
int	size () const
const Relation &	relation (int index) const
	The returned relation is guaranteed to only have positive variables.
absl::Span< const int >	IndicesOfRelationsEnforcedBy (LiteralIndex lit) const
absl::Span< const int >	IndicesOfRelationsContaining (IntegerVariable var) const
absl::Span< const int >	IndicesOfRelationsBetween (IntegerVariable var1, IntegerVariable var2) const
void	Add (Literal lit, LinearTerm a, LinearTerm b, IntegerValue lhs, IntegerValue rhs)
void	AddPartialRelation (Literal lit, IntegerVariable a, IntegerVariable b)
void	Build ()
bool	PropagateLocalBounds (const IntegerTrail &integer_trail, Literal lit, const absl::flat_hash_map< IntegerVariable, IntegerValue > &input, absl::flat_hash_map< IntegerVariable, IntegerValue > *output) const

Member Function Documentation

Add()

void operations_research::sat::BinaryRelationRepository::Add	(	Literal	lit,
		LinearTerm	a,
		LinearTerm	b,
		IntegerValue	lhs,
		IntegerValue	rhs )

Adds a conditional relation lit => a + b \in [lhs, rhs] (one of the terms can be zero), or an always true binary relation a + b \in [lhs, rhs] (both terms must be non-zero).

We shall only consider positive variable here.

Definition at line 1152 of file precedences.cc.

AddPartialRelation()

void operations_research::sat::BinaryRelationRepository::AddPartialRelation	(	Literal	lit,
		IntegerVariable	a,
		IntegerVariable	b )

Adds a partial conditional relation between two variables, with unspecified coefficients and bounds.

Definition at line 1185 of file precedences.cc.

Build()

void operations_research::sat::BinaryRelationRepository::Build

(

)

Builds the literal to relations mapping. This should be called once all the relations have been added.

Definition at line 1194 of file precedences.cc.

IndicesOfRelationsBetween()

absl::Span< const int > operations_research::sat::BinaryRelationRepository::IndicesOfRelationsBetween ( IntegerVariable var1, IntegerVariable var2 ) const

inline

Returns the indices of the non-enforced relations that contain the given (positive) variables.

Definition at line 540 of file precedences.h.

IndicesOfRelationsContaining()

absl::Span< const int > operations_research::sat::BinaryRelationRepository::IndicesOfRelationsContaining ( IntegerVariable var ) const

inline

Returns the indices of the non-enforced relations that contain the given (positive) variable.

Definition at line 532 of file precedences.h.

IndicesOfRelationsEnforcedBy()

absl::Span< const int > operations_research::sat::BinaryRelationRepository::IndicesOfRelationsEnforcedBy ( LiteralIndex lit ) const

inline

Returns the indices of the relations that are enforced by the given literal.

Definition at line 525 of file precedences.h.

PropagateLocalBounds()

bool operations_research::sat::BinaryRelationRepository::PropagateLocalBounds	(	const IntegerTrail &	integer_trail,
		Literal	lit,
		const absl::flat_hash_map< IntegerVariable, IntegerValue > &	input,
		absl::flat_hash_map< IntegerVariable, IntegerValue > *	output ) const

Assuming level-zero bounds + any (var >= value) in the input map, fills "output" with a "propagated" set of bounds assuming lit is true (by using the relations enforced by lit, as well as the non-enforced ones).

Note

we will only fill bounds > level-zero ones in output.

Returns false if the new bounds are infeasible at level zero.

Important: by default this does not call output->clear() so we can take the max with already inferred bounds.

lb(b.y) <= b.y <= ub(b.y) and lhs <= a.x + b.y <= rhs imply ceil((lhs - ub(b.y)) / a) <= x <= floor((rhs - lb(b.y)) / a)

Check feasibility.

Todo

(user): we might do that earlier?

Definition at line 1220 of file precedences.cc.

relation()

const Relation & operations_research::sat::BinaryRelationRepository::relation ( int index ) const

inline

The returned relation is guaranteed to only have positive variables.

Definition at line 521 of file precedences.h.

size()

int operations_research::sat::BinaryRelationRepository::size ( ) const

inline

Definition at line 518 of file precedences.h.

---

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

• ortools/sat/precedences.h
• ortools/sat/precedences.cc