operations_research::sat::PrecedenceRelations Class Reference

#include <precedences.h>

Inheritance diagram for operations_research::sat::PrecedenceRelations:

Classes
struct	PrecedenceData

Public Member Functions
	PrecedenceRelations (Model *model)
void	Resize (int num_variables)
bool	Add (IntegerVariable tail, IntegerVariable head, IntegerValue offset)
void	PushConditionalRelation (absl::Span< const Literal > enforcements, IntegerVariable a, IntegerVariable b, IntegerValue rhs)
void	SetLevel (int level) final
	Called each time we change decision level.
void	ComputeFullPrecedences (absl::Span< const IntegerVariable > vars, std::vector< FullIntegerPrecedence > *output)
void	CollectPrecedences (absl::Span< const IntegerVariable > vars, std::vector< PrecedenceData > *output)
IntegerValue	GetOffset (IntegerVariable a, IntegerVariable b) const
IntegerValue	GetConditionalOffset (IntegerVariable a, IntegerVariable b) const
absl::Span< const Literal >	GetConditionalEnforcements (IntegerVariable a, IntegerVariable b) const
void	Build ()
Public Member Functions inherited from operations_research::ReversibleInterface
	ReversibleInterface ()
virtual	~ReversibleInterface ()

Detailed Description

Stores all the precedences relation of the form "tail_X + offset <= head_X" that we could extract from the linear constraint of the model. These are stored in a directed graph.

Todo

(user): Support conditional relation.

(user): Support non-DAG like graph.

(user): Support variable offset that can be updated as search progress.

Definition at line 55 of file precedences.h.

Constructor & Destructor Documentation

PrecedenceRelations()

operations_research::sat::PrecedenceRelations::PrecedenceRelations ( Model * model )

inlineexplicit

Definition at line 57 of file precedences.h.

Member Function Documentation

Add()

bool operations_research::sat::PrecedenceRelations::Add	(	IntegerVariable	tail,
		IntegerVariable	head,
		IntegerValue	offset )

Add a relation tail + offset <= head. Returns true if it was added and is considered "new".

Ignore trivial relation: tail + offset <= head.

Todo

(user): Return infeasible if tail == head and offset > 0.

Todo

Todo

(user): if tail = Negation(head) also update Domain.

Add to root_relations_.

Todo

(user): AddInternal() only returns true if this is the first relation between head and tail. But we can still avoid an extra lookup.

If we are not built, make sure there is enough room in the graph.

Todo

(user): Alternatively, force caller to do a Resize().

Definition at line 54 of file precedences.cc.

Build()

void operations_research::sat::PrecedenceRelations::Build

(

)

The current code requires the internal data to be processed once all relations are loaded.

Todo

(user): Be more dynamic as we start to add relations during search.

We will construct a graph with the current relation from all_relations_. And use this to compute the "closure".

Note

the non-determinism of the arcs order shouldn't matter.

Todo

(user): Support negative offset?

Note

if we only have >= 0 ones, if we do have a cycle, we could make sure all variales are the same, and otherwise, we have a DAG or a conflict.

We have two arcs.

Is it a DAG? Get a topological order of the DAG formed by all the arcs that are present.

Todo

(user): This can fail if we don't have a DAG. We could just skip Bad edges instead, and have a sub-DAG as an heuristic. Or analyze the arc weight and make sure cycle are not an issue. We can also start with arcs with strictly positive weight.

Todo

(user): Only explore the sub-graph reachable from "vars".

Lets build full precedences if we don't have too many of them.

Todo

(user): Also do that if we don't have a DAG?

Definition at line 208 of file precedences.cc.

CollectPrecedences()

void operations_research::sat::PrecedenceRelations::CollectPrecedences	(	absl::Span< const IntegerVariable >	vars,
		std::vector< PrecedenceData > *	output )

+1 for the negation.

We first compute the degree/size in order to perform the transposition.

Note

we also remove duplicates.

We do not want duplicates.

Permute tmp_precedences_ into the output to put it in the correct order. For that we transform var_to_degree to point to the first position of each lbvar in the output vector.

Optimization: we remove degree one relations.

Note

it is okay to increase the -1 pos since they appear only once.

Cleanup var_to_degree, note that we don't need to clean var_to_last_index_.

Definition at line 406 of file precedences.cc.

ComputeFullPrecedences()

void operations_research::sat::PrecedenceRelations::ComputeFullPrecedences	(	absl::Span< const IntegerVariable >	vars,
		std::vector< FullIntegerPrecedence > *	output )

Returns a set of relations var >= max_i(vars[index[i]] + offsets[i]).

This currently only works if the precedence relation form a DAG. If not we will just abort.

Todo

(user): generalize.

Todo

(user): Put some work limit in place, as this can be slow. Complexity is in O(vars.size()) * num_arcs.

Todo

(user): Since we don't need ALL precedences, we could just work on a sub-DAG of the full precedence graph instead of aborting. Or we can just support the general non-DAG cases.

Todo

(user): Many relations can be redundant. Filter them.

Compute all precedences. We loop over the node in topological order, and we maintain for all variable we encounter, the list of "to_consider" variables that are before.

Todo

(user): use vector of fixed size.

We copy the data for tail_var here, because the pointer is not stable.

Todo

(user): optimize when needed.

No need to create an empty entry in this case.

Small filtering heuristic: if we have (before) < tail, and tail < head, we really do not need to list (before, tail) < head. We only need that if the list of variable before head contains some variable that are not already before tail.

Extract the output for tail_var. Because of the topological ordering, the data for tail_var is already final now.

Todo

(user): Release the memory right away.

Definition at line 312 of file precedences.cc.

GetConditionalEnforcements()

absl::Span< const Literal > operations_research::sat::PrecedenceRelations::GetConditionalEnforcements	(	IntegerVariable	a,
		IntegerVariable	b ) const

Definition at line 178 of file precedences.cc.

GetConditionalOffset()

IntegerValue operations_research::sat::PrecedenceRelations::GetConditionalOffset	(	IntegerVariable	a,
		IntegerVariable	b ) const

Returns the minimum distance between a and b, and the reason for it (all true). Note that we always check GetOffset() so if it is better, the returned literal reason will be empty.

We separate the two because usually the reason is only needed when we push, which happen less often, so we don't mind doing two hash lookups, and we really want to optimize the GetConditionalOffset() instead.

Important: This doesn't contains the transitive closure. Important: The span is only valid in a narrow scope.

Definition at line 197 of file precedences.cc.

GetOffset()

IntegerValue operations_research::sat::PrecedenceRelations::GetOffset	(	IntegerVariable	a,
		IntegerVariable	b ) const

If we don't have too many variable, we compute the full transitive closure and can query in O(1) if there is a relation between two variables. This can be used to optimize some scheduling propagation and reasons.

Warning

If there are too many, this will NOT contain all relations.

Returns kMinIntegerValue if there are none. Otherwise a + offset <= b.

Definition at line 169 of file precedences.cc.

PushConditionalRelation()

void operations_research::sat::PrecedenceRelations::PushConditionalRelation	(	absl::Span< const Literal >	enforcements,
		IntegerVariable	a,
		IntegerVariable	b,
		IntegerValue	rhs )

Adds add relation (enf => a + b <= rhs) that is assumed to be true at the current level.

It will be automatically reverted via the SetLevel() functions that is called before any integer propagations trigger.

This is assumed to be called when a relation becomes true (enforcement are assigned) and when it becomes false in reverse order (CHECKed).

This must be currently true.

Ignore if no better than best_relations, otherwise increase it.

We should only decrease because we ignored entry worse than the one in best_relations_.

Update.

Definition at line 83 of file precedences.cc.

Resize()

void operations_research::sat::PrecedenceRelations::Resize ( int num_variables )

inline

Definition at line 64 of file precedences.h.

SetLevel()

void operations_research::sat::PrecedenceRelations::SetLevel ( int level )

finalvirtual

Called each time we change decision level.

We only pop what is needed.

Implements operations_research::ReversibleInterface.

Definition at line 142 of file precedences.cc.

---

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

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