![]() |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
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.
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_ |
|
inline |
Definition at line 159 of file linear_propagation.h.
|
inline |
Definition at line 195 of file linear_propagation.h.
|
inline |
Definition at line 298 of file linear_propagation.h.
|
inline |
Return -1 if there is none. This returns a constraint with min degree.
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.
|
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.
|
inline |
Definition at line 166 of file linear_propagation.h.
|
inline |
Definition at line 287 of file linear_propagation.h.
|
inline |
Definition at line 300 of file linear_propagation.h.
std::function<absl::Span<const IntegerVariable>(int)> operations_research::sat::ConstraintPropagationOrder::id_to_vars_func_ |
Definition at line 309 of file linear_propagation.h.
std::deque<int> operations_research::sat::ConstraintPropagationOrder::ids_ |
Definition at line 322 of file linear_propagation.h.
Bitset64<int> operations_research::sat::ConstraintPropagationOrder::in_ids_ |
Definition at line 321 of file linear_propagation.h.
ModelRandomGenerator* operations_research::sat::ConstraintPropagationOrder::random_ |
Definition at line 307 of file linear_propagation.h.
int operations_research::sat::ConstraintPropagationOrder::start_ = 0 |
Set/queue of constraints to be propagated.
Definition at line 320 of file linear_propagation.h.
TimeLimit* operations_research::sat::ConstraintPropagationOrder::time_limit_ |
Definition at line 308 of file linear_propagation.h.
std::vector<IntegerVariable> operations_research::sat::ConstraintPropagationOrder::to_clear_ |
Definition at line 317 of file linear_propagation.h.
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.
util_intops::StrongVector<IntegerVariable, int> operations_research::sat::ConstraintPropagationOrder::var_to_id_ |
Definition at line 314 of file linear_propagation.h.
util_intops::StrongVector<IntegerVariable, IntegerValue> operations_research::sat::ConstraintPropagationOrder::var_to_lb_ |
Definition at line 315 of file linear_propagation.h.
util_intops::StrongVector<IntegerVariable, int> operations_research::sat::ConstraintPropagationOrder::var_to_pos_ |
Definition at line 316 of file linear_propagation.h.