Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::sat::ConstraintPropagationOrder Class Reference

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. This also likely simplifies the reasons.

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

Definition at line 157 of file linear_propagation.h.

#include <linear_propagation.h>

Public Member Functions

 ConstraintPropagationOrder (ModelRandomGenerator *random, TimeLimit *time_limit, 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_
TimeLimit * time_limit_
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_

Constructor & Destructor Documentation

◆ ConstraintPropagationOrder()

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

Definition at line 159 of file linear_propagation.h.

Member Function Documentation

◆ Clear()

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

Definition at line 195 of file linear_propagation.h.

◆ IsEmpty()

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

Definition at line 298 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 or even linear algo? We can use var_to_ids_func_() to maintain the degree. But note that since we reorder constraints and because we expect mainly degree zero, this seems to be faster.

By degree, we mean the number of variables of the constraint that do not have yet their lower bounds up to date; they will be pushed by other constraints as we propagate them. If possible, we want to delay the propagation of a constraint with positive degree until all involved lower bounds are up to date (i.e. degree == 0).

We have two constraints, this one (id) push NegationOf(var), and var_to_id_[var] push var. So whichever order we choose, the first constraint will need to be scanned at least twice. Lets not count this situation in the degree.

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 213 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 175 of file linear_propagation.h.

◆ Resize()

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

Definition at line 166 of file linear_propagation.h.

◆ UpdateBound()

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

Definition at line 287 of file linear_propagation.h.

◆ VarShouldBePushedById()

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

Definition at line 300 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 309 of file linear_propagation.h.

◆ ids_

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

Definition at line 322 of file linear_propagation.h.

◆ in_ids_

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

Definition at line 321 of file linear_propagation.h.

◆ random_

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

Definition at line 307 of file linear_propagation.h.

◆ start_

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

Set/queue of constraints to be propagated.

Definition at line 320 of file linear_propagation.h.

◆ time_limit_

TimeLimit* operations_research::sat::ConstraintPropagationOrder::time_limit_

Definition at line 308 of file linear_propagation.h.

◆ to_clear_

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

Definition at line 317 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 313 of file linear_propagation.h.

◆ var_to_id_

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

Definition at line 314 of file linear_propagation.h.

◆ var_to_lb_

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

Definition at line 315 of file linear_propagation.h.

◆ var_to_pos_

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

Definition at line 316 of file linear_propagation.h.

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