operations_research::sat::ConstraintPropagationOrder Class Reference

#include <linear_propagation.h>

Public Member Functions
	ConstraintPropagationOrder (ModelRandomGenerator *random, std::function< absl::Span< const IntegerVariable >(int)> id_to_vars)
void	Resize (int num_vars, int num_ids)
void	Register (int id, IntegerVariable var, IntegerValue lb)
void	Clear ()
int	NextId ()
void	UpdateBound (IntegerVariable var, IntegerValue lb)
bool	IsEmpty () const
bool	VarShouldBePushedById (IntegerVariable var, int id)

Public Attributes
ModelRandomGenerator *	random_
std::function< absl::Span< const IntegerVariable >(int)>	id_to_vars_func_
Bitset64< IntegerVariable >	var_has_entry_
util_intops::StrongVector< IntegerVariable, int >	var_to_id_
util_intops::StrongVector< IntegerVariable, IntegerValue >	var_to_lb_
util_intops::StrongVector< IntegerVariable, int >	var_to_pos_
std::vector< IntegerVariable >	to_clear_
int	start_ = 0
	Set/queue of constraints to be propagated.
Bitset64< int >	in_ids_
std::deque< int >	ids_

Detailed Description

Helper class to decide on the constraint propagation order.

Each constraint might push some variables which might in turn make other constraint tighter. In general, it seems better to make sure we push first constraints that are not affected by other variables and delay the propagation of constraint that we know will become tigher.

Note

we can have cycle in this graph, and that this is not necessarily a conflict.

Definition at line 156 of file linear_propagation.h.

Constructor & Destructor Documentation

ConstraintPropagationOrder()

operations_research::sat::ConstraintPropagationOrder::ConstraintPropagationOrder ( ModelRandomGenerator * random, std::function< absl::Span< const IntegerVariable >(int)> id_to_vars )

inline

Definition at line 158 of file linear_propagation.h.

Member Function Documentation

Clear()

void operations_research::sat::ConstraintPropagationOrder::Clear ( )

inline

Definition at line 192 of file linear_propagation.h.

IsEmpty()

bool operations_research::sat::ConstraintPropagationOrder::IsEmpty ( ) const

inline

Definition at line 270 of file linear_propagation.h.

NextId()

int operations_research::sat::ConstraintPropagationOrder::NextId ( )

inline

Return -1 if there is none. This returns a constraint with min degree.

Todo

(user): fix quadratic algo? We can use var_to_ids_func_() to maintain the degree. But note that with the start_ optim and because we expect mainly degree zero, this seems to be faster.

We select the min-degree and prefer lower constraint size. We however stop at the first degree zero.

We didn't find any degree zero, we scanned the whole queue. Extract best_id while keeping the order stable.

We tried to randomize the order, it does add more variance but also seem worse overall.

Definition at line 209 of file linear_propagation.h.

Register()

void operations_research::sat::ConstraintPropagationOrder::Register ( int id, IntegerVariable var, IntegerValue lb )

inline

All new ids are likely not in a cycle, we want to test them first.

Definition at line 172 of file linear_propagation.h.

Resize()

void operations_research::sat::ConstraintPropagationOrder::Resize ( int num_vars, int num_ids )

inline

Definition at line 163 of file linear_propagation.h.

UpdateBound()

void operations_research::sat::ConstraintPropagationOrder::UpdateBound ( IntegerVariable var, IntegerValue lb )

inline

Definition at line 259 of file linear_propagation.h.

VarShouldBePushedById()

bool operations_research::sat::ConstraintPropagationOrder::VarShouldBePushedById ( IntegerVariable var, int id )

inline

Definition at line 272 of file linear_propagation.h.

Member Data Documentation

id_to_vars_func_

std::function<absl::Span<const IntegerVariable>(int)> operations_research::sat::ConstraintPropagationOrder::id_to_vars_func_

Definition at line 280 of file linear_propagation.h.

ids_

std::deque<int> operations_research::sat::ConstraintPropagationOrder::ids_

Definition at line 293 of file linear_propagation.h.

in_ids_

Bitset64<int> operations_research::sat::ConstraintPropagationOrder::in_ids_

Definition at line 292 of file linear_propagation.h.

random_

ModelRandomGenerator* operations_research::sat::ConstraintPropagationOrder::random_

Definition at line 279 of file linear_propagation.h.

start_

int operations_research::sat::ConstraintPropagationOrder::start_ = 0

Set/queue of constraints to be propagated.

Definition at line 291 of file linear_propagation.h.

to_clear_

std::vector<IntegerVariable> operations_research::sat::ConstraintPropagationOrder::to_clear_

Definition at line 288 of file linear_propagation.h.

var_has_entry_

Bitset64<IntegerVariable> operations_research::sat::ConstraintPropagationOrder::var_has_entry_

For each variable we only keep the constraint id that pushes it further. In case of tie, we only keep the first to be registered.

Definition at line 284 of file linear_propagation.h.

var_to_id_

util_intops::StrongVector<IntegerVariable, int> operations_research::sat::ConstraintPropagationOrder::var_to_id_

Definition at line 285 of file linear_propagation.h.

var_to_lb_

util_intops::StrongVector<IntegerVariable, IntegerValue> operations_research::sat::ConstraintPropagationOrder::var_to_lb_

Definition at line 286 of file linear_propagation.h.

var_to_pos_

util_intops::StrongVector<IntegerVariable, int> operations_research::sat::ConstraintPropagationOrder::var_to_pos_

Definition at line 287 of file linear_propagation.h.

---

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

• ortools/sat/linear_propagation.h