22#include "absl/container/flat_hash_map.h"
23#include "absl/strings/str_format.h"
24#include "absl/strings/str_join.h"
39struct AffineTransformation {
40 AffineTransformation() :
a(1),
b(0) {}
65 std::string DebugString()
const {
66 return absl::StrFormat(
"(%d * x + %d)",
a,
b);
71class VarLinearizer :
public ModelParser {
73 VarLinearizer() :
target_var_(nullptr), transformation_(nullptr) {}
74 ~VarLinearizer()
override {}
76 void VisitIntegerVariable(
const IntVar*
const variable,
78 IntVar*
const delegate)
override {
81 delegate->Accept(
this);
85 delegate->Accept(
this);
88 PushMultiplier(
value);
89 delegate->Accept(
this);
93 transformation_->a = multipliers_.back();
97 void VisitIntegerVariable(
const IntVar*
const variable,
98 IntExpr*
const delegate)
override {
100 transformation_->a = multipliers_.back();
103 void Visit(
const IntVar*
const var, IntVar**
const target_var,
104 AffineTransformation*
const transformation) {
106 transformation_ = transformation;
107 transformation->Clear();
111 CHECK(multipliers_.empty());
114 std::string DebugString()
const override {
return "VarLinearizer"; }
117 void AddConstant(
int64 constant) {
118 transformation_->b += constant * multipliers_.back();
121 void PushMultiplier(
int64 multiplier) {
122 if (multipliers_.empty()) {
123 multipliers_.push_back(multiplier);
125 multipliers_.push_back(multiplier * multipliers_.back());
129 void PopMultiplier() { multipliers_.pop_back(); }
131 std::vector<int64> multipliers_;
133 AffineTransformation* transformation_;
136static const int kBitsInUint64 = 64;
152class BasePositiveTableConstraint :
public Constraint {
154 BasePositiveTableConstraint(Solver*
const s,
const std::vector<IntVar*>& vars,
155 const IntTupleSet& tuples)
163 transformations_(
arity_) {
173 VarLinearizer linearizer;
174 for (
int i = 0; i <
arity_; ++i) {
175 linearizer.Visit(vars[i], &
vars_[i], &transformations_[i]);
178 for (
int i = 0; i <
arity_; ++i) {
184 ~BasePositiveTableConstraint()
override {}
186 std::string DebugString()
const override {
187 return absl::StrFormat(
"AllowedAssignments(arity = %d, tuple_count = %d)",
191 void Accept(ModelVisitor*
const visitor)
const override {
200 bool TupleValue(
int tuple_index,
int var_index,
int64*
const value)
const {
201 return transformations_[var_index].Reverse(
202 tuples_.Value(tuple_index, var_index),
value);
205 int64 UnsafeTupleValue(
int tuple_index,
int var_index)
const {
206 return transformations_[var_index].UnsafeReverse(
207 tuples_.Value(tuple_index, var_index));
210 bool IsTupleSupported(
int tuple_index) {
211 for (
int var_index = 0; var_index <
arity_; ++var_index) {
213 if (!TupleValue(tuple_index, var_index, &
value) ||
230 const IntTupleSet tuples_;
233 std::vector<AffineTransformation> transformations_;
236class PositiveTableConstraint :
public BasePositiveTableConstraint {
238 typedef absl::flat_hash_map<int, std::vector<uint64>> ValueBitset;
240 PositiveTableConstraint(Solver*
const s,
const std::vector<IntVar*>& vars,
241 const IntTupleSet& tuples)
242 : BasePositiveTableConstraint(s, vars, tuples),
246 ~PositiveTableConstraint()
override {}
248 void Post()
override {
250 solver(),
this, &PositiveTableConstraint::Propagate,
"Propagate");
251 for (
int i = 0; i <
arity_; ++i) {
252 vars_[i]->WhenDomain(d);
254 solver(),
this, &PositiveTableConstraint::Update,
"Update", i);
255 vars_[i]->WhenDomain(u);
265 for (
int tuple_index = 0; tuple_index <
tuple_count_; ++tuple_index) {
266 if (IsTupleSupported(tuple_index)) {
267 SetBit64(actives.data(), tuple_index);
273 void InitialPropagate()
override {
275 for (
int var_index = 0; var_index <
arity_; ++var_index) {
276 for (
const auto& it :
masks_[var_index]) {
277 if (!
vars_[var_index]->Contains(it.first)) {
286 for (
int var_index = 0; var_index <
arity_; ++var_index) {
287 const ValueBitset& mask =
masks_[var_index];
288 IntVar*
const var =
vars_[var_index];
302 for (
int var_index = 0; var_index <
arity_; ++var_index) {
303 IntVar*
const var =
vars_[var_index];
306 if (!Supported(var_index,
value)) {
316 void Update(
int index) {
319 const int64 old_max =
var->OldMax();
323 const auto& it = var_masks.find(
value);
324 if (it != var_masks.end()) {
325 BlankActives(it->second);
329 const auto& it = var_masks.find(
value);
330 if (it != var_masks.end()) {
331 BlankActives(it->second);
335 const auto& it = var_masks.find(
value);
336 if (it != var_masks.end()) {
337 BlankActives(it->second);
342 void BlankActives(
const std::vector<uint64>& mask) {
355 const std::vector<uint64>& mask =
masks_[var_index][
value];
360 std::string DebugString()
const override {
361 return absl::StrFormat(
"PositiveTableConstraint([%s], %d tuples)",
366 void InitializeMask(
int tuple_index) {
367 std::vector<int64> cache(
arity_);
368 for (
int var_index = 0; var_index <
arity_; ++var_index) {
369 if (!TupleValue(tuple_index, var_index, &cache[var_index])) {
373 for (
int var_index = 0; var_index <
arity_; ++var_index) {
375 std::vector<uint64>& mask =
masks_[var_index][
value];
391class CompactPositiveTableConstraint :
public BasePositiveTableConstraint {
393 CompactPositiveTableConstraint(Solver*
const s,
394 const std::vector<IntVar*>& vars,
395 const IntTupleSet& tuples)
396 : BasePositiveTableConstraint(s, vars, tuples),
409 ~CompactPositiveTableConstraint()
override {}
411 void Post()
override {
413 solver(),
this, &CompactPositiveTableConstraint::Propagate,
415 for (
int i = 0; i <
arity_; ++i) {
417 solver(),
this, &CompactPositiveTableConstraint::Update,
"Update", i);
418 vars_[i]->WhenDomain(u);
420 for (
int i = 0; i <
arity_; ++i) {
421 var_sizes_.SetValue(solver(), i,
vars_[i]->Size());
425 void InitialPropagate()
override {
427 FillMasksAndActiveTuples();
428 ComputeMasksBoundaries();
430 RemoveUnsupportedValues();
437 if (touched_var_ == -2) {
444 for (
int var_index = 0; var_index <
arity_; ++var_index) {
449 if (var_index == touched_var_) {
453 IntVar*
const var =
vars_[var_index];
454 const int64 original_min = original_min_[var_index];
460 if (!Supported(var_index,
var->Min() - original_min)) {
468 const bool min_support = Supported(var_index, var_min - original_min);
469 const bool max_support = Supported(var_index, var_max - original_min);
474 var->SetValue(var_max);
475 var_sizes_.SetValue(solver(), var_index, 1);
477 }
else if (!max_support) {
478 var->SetValue(var_min);
479 var_sizes_.SetValue(solver(), var_index, 1);
487 int64 new_min = var_min;
488 int64 new_max = var_max;
492 if (var_max - var_min + 1 == var_size) {
493 for (; new_min <= var_max; ++new_min) {
494 if (Supported(var_index, new_min - original_min)) {
498 for (; new_max >= new_min; --new_max) {
499 if (Supported(var_index, new_max - original_min)) {
503 var->SetRange(new_min, new_max);
505 if (!Supported(var_index,
value - original_min)) {
515 if (!Supported(var_index,
value - original_min)) {
526 var->SetRange(new_min, new_max);
535 var_sizes_.SetValue(solver(), var_index,
var->Size());
541 void Update(
int var_index) {
542 if (
vars_[var_index]->Size() == var_sizes_.Value(var_index)) {
549 IntVar*
const var =
vars_[var_index];
550 bool changed =
false;
551 const int64 omin = original_min_[var_index];
558 changed = AndMaskWithActive(
masks_[var_index][var_min - omin]);
562 SetTempMask(var_index, var_min - omin);
563 OrTempMask(var_index, var_max - omin);
568 const int64 estimated_hole_size =
569 var_sizes_.Value(var_index) - var_size;
570 const int64 old_min =
var->OldMin();
571 const int64 old_max =
var->OldMax();
574 const int64 number_of_operations =
575 estimated_hole_size + var_min - old_min + old_max - var_max;
576 if (number_of_operations < var_size) {
579 changed |= SubtractMaskFromActive(
masks_[var_index][
value - omin]);
582 changed |= SubtractMaskFromActive(
masks_[var_index][
value - omin]);
585 changed |= SubtractMaskFromActive(
masks_[var_index][
value - omin]);
591 if (var_max - var_min + 1 == var_size) {
593 OrTempMask(var_index,
value - omin);
597 OrTempMask(var_index,
value - omin);
605 var_sizes_.SetValue(solver(), var_index, var_size);
610 if (touched_var_ == -1 || touched_var_ == var_index) {
611 touched_var_ = var_index;
615 EnqueueDelayedDemon(demon_);
619 std::string DebugString()
const override {
620 return absl::StrFormat(
"CompactPositiveTableConstraint([%s], %d tuples)",
629 for (
int i = 0; i <
arity_; ++i) {
630 original_min_[i] =
vars_[i]->Min();
631 const int64 span =
vars_[i]->Max() - original_min_[i] + 1;
636 void FillMasksAndActiveTuples() {
638 for (
int tuple_index = 0; tuple_index <
tuple_count_; ++tuple_index) {
639 if (IsTupleSupported(tuple_index)) {
640 SetBit64(actives.data(), tuple_index);
642 for (
int var_index = 0; var_index <
arity_; ++var_index) {
643 const int64 value = UnsafeTupleValue(tuple_index, var_index);
644 const int64 value_index =
value - original_min_[var_index];
647 if (
masks_[var_index][value_index].empty()) {
657 void RemoveUnsupportedValues() {
659 for (
int var_index = 0; var_index <
arity_; ++var_index) {
660 IntVar*
const var =
vars_[var_index];
663 if (
masks_[var_index][
value - original_min_[var_index]].empty()) {
673 void ComputeMasksBoundaries() {
674 for (
int var_index = 0; var_index <
arity_; ++var_index) {
675 mask_starts_[var_index].resize(
masks_[var_index].size());
676 mask_ends_[var_index].resize(
masks_[var_index].size());
677 for (
int value_index = 0; value_index <
masks_[var_index].size();
679 const std::vector<uint64>& mask =
masks_[var_index][value_index];
689 while (end > start && mask[end] == 0) {
695 mask_starts_[var_index][value_index] = start;
696 mask_ends_[var_index][value_index] = end;
701 void BuildSupports() {
702 for (
int var_index = 0; var_index <
arity_; ++var_index) {
709 bool AndMaskWithActive(
const std::vector<uint64>& mask) {
717 bool SubtractMaskFromActive(
const std::vector<uint64>& mask) {
725 bool Supported(
int var_index,
int64 value_index) {
730 const std::vector<uint64>& mask =
masks_[var_index][value_index];
735 void OrTempMask(
int var_index,
int64 value_index) {
736 const std::vector<uint64>& mask =
masks_[var_index][value_index];
738 const int mask_span = mask_ends_[var_index][value_index] -
739 mask_starts_[var_index][value_index] + 1;
745 for (
int i = mask_starts_[var_index][value_index];
746 i <= mask_ends_[var_index][value_index]; ++i) {
753 void SetTempMask(
int var_index,
int64 value_index) {
768 void ClearTempMask() {
784 std::vector<std::vector<std::vector<uint64>>>
masks_;
786 std::vector<std::vector<int>> mask_starts_;
787 std::vector<std::vector<int>> mask_ends_;
789 std::vector<int64> original_min_;
797 RevArray<int64> var_sizes_;
804class SmallCompactPositiveTableConstraint :
public BasePositiveTableConstraint {
806 SmallCompactPositiveTableConstraint(Solver*
const s,
807 const std::vector<IntVar*>& vars,
808 const IntTupleSet& tuples)
809 : BasePositiveTableConstraint(s, vars, tuples),
818 CHECK_LE(tuples.NumTuples(), kBitsInUint64);
821 ~SmallCompactPositiveTableConstraint()
override {}
823 void Post()
override {
825 solver(),
this, &SmallCompactPositiveTableConstraint::Propagate,
827 for (
int i = 0; i <
arity_; ++i) {
828 if (!
vars_[i]->Bound()) {
830 solver(),
this, &SmallCompactPositiveTableConstraint::Update,
832 vars_[i]->WhenDomain(update_demon);
840 for (
int i = 0; i <
arity_; ++i) {
841 original_min_[i] =
vars_[i]->Min();
842 const int64 span =
vars_[i]->Max() - original_min_[i] + 1;
843 masks_[i].assign(span, 0);
847 bool IsTupleSupported(
int tuple_index) {
848 for (
int var_index = 0; var_index <
arity_; ++var_index) {
850 if (!TupleValue(tuple_index, var_index, &
value) ||
858 void ComputeActiveTuples() {
861 for (
int tuple_index = 0; tuple_index <
tuple_count_; ++tuple_index) {
862 if (IsTupleSupported(tuple_index)) {
865 for (
int var_index = 0; var_index <
arity_; ++var_index) {
866 const int64 value = UnsafeTupleValue(tuple_index, var_index);
867 masks_[var_index][
value - original_min_[var_index]] |= local_mask;
876 void RemoveUnsupportedValues() {
878 for (
int var_index = 0; var_index <
arity_; ++var_index) {
879 IntVar*
const var =
vars_[var_index];
880 const int64 original_min = original_min_[var_index];
883 if (
masks_[var_index][
value - original_min] == 0) {
893 void InitialPropagate()
override {
895 ComputeActiveTuples();
896 RemoveUnsupportedValues();
906 if (touched_var_ == -2) {
914 for (
int var_index = 0; var_index <
arity_; ++var_index) {
919 if (var_index == touched_var_) {
923 const std::vector<uint64>& var_mask =
masks_[var_index];
924 const int64 original_min = original_min_[var_index];
925 IntVar*
const var =
vars_[var_index];
929 if ((var_mask[
var->Min() - original_min] & actives) == 0) {
941 const bool min_support =
942 (var_mask[var_min - original_min] & actives) != 0;
943 const bool max_support =
944 (var_mask[var_max - original_min] & actives) != 0;
945 if (!min_support && !max_support) {
947 }
else if (!min_support) {
948 var->SetValue(var_max);
949 }
else if (!max_support) {
950 var->SetValue(var_min);
958 int64 new_min = var_min;
959 int64 new_max = var_max;
960 if (var_max - var_min + 1 == var_size) {
962 for (; new_min <= var_max; ++new_min) {
963 if ((var_mask[new_min - original_min] & actives) != 0) {
967 for (; new_max >= new_min; --new_max) {
968 if ((var_mask[new_max - original_min] & actives) != 0) {
972 var->SetRange(new_min, new_max);
974 if ((var_mask[
value - original_min] & actives) == 0) {
979 bool min_set =
false;
984 if ((var_mask[
value - original_min] & actives) == 0) {
998 var->SetRange(new_min, new_max);
1010 void Update(
int var_index) {
1014 IntVar*
const var =
vars_[var_index];
1015 const int64 original_min = original_min_[var_index];
1016 const int64 var_size =
var->Size();
1019 ApplyMask(var_index,
masks_[var_index][
var->Min() - original_min]);
1023 ApplyMask(var_index,
masks_[var_index][
var->Min() - original_min] |
1024 masks_[var_index][
var->Max() - original_min]);
1030 const std::vector<uint64>& var_mask =
masks_[var_index];
1031 const int64 old_min =
var->OldMin();
1032 const int64 old_max =
var->OldMax();
1035 const bool contiguous = var_size == var_max - var_min + 1;
1036 const bool nearly_contiguous =
1037 var_size > (var_max - var_min + 1) * 7 / 10;
1047 hole_mask |= var_mask[
value - original_min];
1050 const int64 hole_operations = var_min - old_min + old_max - var_max;
1052 const int64 domain_operations = contiguous ? var_size : 4 * var_size;
1053 if (hole_operations < domain_operations) {
1055 hole_mask |= var_mask[
value - original_min];
1058 hole_mask |= var_mask[
value - original_min];
1061 ApplyMask(var_index, ~hole_mask);
1066 domain_mask |= var_mask[
value - original_min];
1068 }
else if (nearly_contiguous) {
1071 domain_mask |= var_mask[
value - original_min];
1076 domain_mask |= var_mask[
value - original_min];
1079 ApplyMask(var_index, domain_mask);
1085 std::string DebugString()
const override {
1086 return absl::StrFormat(
1087 "SmallCompactPositiveTableConstraint([%s], %d tuples)",
1092 void ApplyMask(
int var_index,
uint64 mask) {
1095 const uint64 current_stamp = solver()->stamp();
1096 if (
stamp_ < current_stamp) {
1103 if (touched_var_ == -1 || touched_var_ == var_index) {
1104 touched_var_ = var_index;
1108 EnqueueDelayedDemon(demon_);
1122 std::vector<std::vector<uint64>>
masks_;
1124 std::vector<int64> original_min_;
1129bool HasCompactDomains(
const std::vector<IntVar*>& vars) {
1146 const IntTupleSet& transition_table,
int64 initial_state,
1147 const std::vector<int64>& final_states)
1150 transition_table_(transition_table),
1151 initial_state_(initial_state),
1152 final_states_(final_states) {}
1155 const IntTupleSet& transition_table,
int64 initial_state,
1156 const std::vector<int>& final_states)
1159 transition_table_(transition_table),
1160 initial_state_(initial_state),
1161 final_states_(final_states.size()) {
1162 for (
int i = 0; i < final_states.size(); ++i) {
1163 final_states_[i] = final_states[i];
1167 ~TransitionConstraint()
override {}
1169 void Post()
override {
1170 Solver*
const s = solver();
1173 const int nb_vars =
vars_.size();
1174 for (
int i = 0; i < transition_table_.NumTuples(); ++i) {
1185 std::vector<IntVar*> states;
1186 states.push_back(s->MakeIntConst(initial_state_));
1187 for (
int var_index = 1; var_index < nb_vars; ++var_index) {
1188 states.push_back(s->MakeIntVar(state_min, state_max));
1190 states.push_back(s->MakeIntVar(final_states_));
1191 CHECK_EQ(nb_vars + 1, states.size());
1193 const int num_tuples = transition_table_.NumTuples();
1195 for (
int var_index = 0; var_index < nb_vars; ++var_index) {
1196 std::vector<IntVar*> tmp_vars(3);
1197 tmp_vars[0] = states[var_index];
1198 tmp_vars[1] =
vars_[var_index];
1199 tmp_vars[2] = states[var_index + 1];
1201 if (num_tuples <= kBitsInUint64) {
1202 s->AddConstraint(s->RevAlloc(
new SmallCompactPositiveTableConstraint(
1203 s, tmp_vars, transition_table_)));
1205 s->AddConstraint(s->RevAlloc(
new CompactPositiveTableConstraint(
1206 s, tmp_vars, transition_table_)));
1211 void InitialPropagate()
override {}
1213 void Accept(ModelVisitor*
const visitor)
const override {
1225 std::string DebugString()
const override {
1226 return absl::StrFormat(
1227 "TransitionConstraint([%s], %d transitions, initial = %d, final = "
1230 initial_state_, absl::StrJoin(final_states_,
", "));
1235 const std::vector<IntVar*>
vars_;
1237 const IntTupleSet transition_table_;
1239 const int64 initial_state_;
1241 std::vector<int64> final_states_;
1253 if (HasCompactDomains(vars)) {
1254 if (tuples.
NumTuples() < kBitsInUint64 && parameters_.use_small_table()) {
1256 new SmallCompactPositiveTableConstraint(
this, vars, tuples));
1258 return RevAlloc(
new CompactPositiveTableConstraint(
this, vars, tuples));
1261 return RevAlloc(
new PositiveTableConstraint(
this, vars, tuples));
1265 const std::vector<IntVar*>& vars,
const IntTupleSet& transition_table,
1266 int64 initial_state,
const std::vector<int64>& final_states) {
1268 initial_state, final_states));
1272 const std::vector<IntVar*>& vars,
const IntTupleSet& transition_table,
1273 int64 initial_state,
const std::vector<int>& final_states) {
1275 initial_state, final_states));
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define DCHECK_GE(val1, val2)
#define CHECK_NE(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define CHECK_LE(val1, val2)
#define DCHECK_EQ(val1, val2)
A constraint is the main modeling object.
static const char kFinalStatesArgument[]
static const char kProductOperation[]
static const char kTraceOperation[]
static const char kTransition[]
static const char kTuplesArgument[]
static const char kAllowedAssignments[]
static const char kDifferenceOperation[]
static const char kVarsArgument[]
static const char kSumOperation[]
static const char kInitialState[]
Constraint * MakeTransitionConstraint(const std::vector< IntVar * > &vars, const IntTupleSet &transition_table, int64 initial_state, const std::vector< int64 > &final_states)
This constraint create a finite automaton that will check the sequence of variables vars.
Constraint * MakeAllowedAssignments(const std::vector< IntVar * > &vars, const IntTupleSet &tuples)
This method creates a constraint where the graph of the relation between the variables is given in ex...
T * RevAlloc(T *object)
Registers the given object as being reversible.
std::vector< int64 > to_remove_
UnsortedNullableRevBitset active_tuples_
static const int kTransitionTupleSize
std::vector< uint64 > temp_mask_
static const int kStatePosition
static const int kNextStatePosition
std::vector< ValueBitset > masks_
std::vector< IntVar * > vars_
std::vector< IntVarIterator * > holes_
std::vector< IntVarIterator * > iterators_
std::vector< int > supports_
static const int64 kint64max
static const int64 kint64min
bool ContainsKey(const Collection &collection, const Key &key)
std::function< void(Model *)> TransitionConstraint(const std::vector< IntegerVariable > &vars, const std::vector< std::vector< int64 > > &automaton, int64 initial_state, const std::vector< int64 > &final_states)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
uint64 BitLength64(uint64 size)
void SetBit64(uint64 *const bitset, uint64 pos)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
BeginEndReverseIteratorWrapper< Container > Reverse(const Container &c)
IntervalVar *const target_var_