Google OR-Tools: ortools/constraint_solver/assignment.cc Source File
22#include "absl/container/flat_hash_map.h"
23#include "absl/strings/str_format.h"
24#include "absl/strings/str_join.h"
25#include "absl/strings/string_view.h"
67 min_ = int_var_assignment_proto.min();
68 max_ = int_var_assignment_proto.max();
69 if (int_var_assignment_proto.active()) {
93 int_var_assignment_proto->set_var_id(var_->name());
94 int_var_assignment_proto->set_min(min_);
95 int_var_assignment_proto->set_max(max_);
119 start_min_ = std::numeric_limits<int64_t>::min();
120 start_max_ = std::numeric_limits<int64_t>::max();
121 duration_min_ = std::numeric_limits<int64_t>::min();
122 duration_max_ = std::numeric_limits<int64_t>::max();
123 end_min_ = std::numeric_limits<int64_t>::min();
136 SetStartRange(element.start_min_, element.start_max_);
137 SetDurationRange(element.duration_min_, element.duration_max_);
138 SetEndRange(element.end_min_, element.end_max_);
139 SetPerformedRange(element.performed_min_, element.performed_max_);
149 performed_min_ = static_cast<int64_t>(var_->MustBePerformed());
150 performed_max_ = static_cast<int64_t>(var_->MayBePerformed());
151 if (performed_max_ != 0LL) {
152 start_min_ = var_->StartMin();
153 start_max_ = var_->StartMax();
154 duration_min_ = var_->DurationMin();
155 duration_max_ = var_->DurationMax();
156 end_min_ = var_->EndMin();
162 if (performed_max_ == performed_min_) {
163 var_->SetPerformed(performed_min_);
165 if (performed_max_ != 0LL) {
166 var_->SetStartRange(start_min_, start_max_);
167 var_->SetDurationRange(duration_min_, duration_max_);
174 start_min_ = interval_var_assignment_proto.start_min();
175 start_max_ = interval_var_assignment_proto.start_max();
176 duration_min_ = interval_var_assignment_proto.duration_min();
177 duration_max_ = interval_var_assignment_proto.duration_max();
178 end_min_ = interval_var_assignment_proto.end_min();
179 end_max_ = interval_var_assignment_proto.end_max();
180 performed_min_ = interval_var_assignment_proto.performed_min();
181 performed_max_ = interval_var_assignment_proto.performed_max();
182 if (interval_var_assignment_proto.active()) {
206 absl::StrAppendFormat(&out, "(start = %d", start_min_);
207 if (start_max_ != start_min_) {
208 absl::StrAppendFormat(&out, "..%d", start_max_);
210 absl::StrAppendFormat(&out, ", duration = %d", duration_min_);
211 if (duration_max_ != duration_min_) {
212 absl::StrAppendFormat(&out, "..%d", duration_max_);
214 absl::StrAppendFormat(&out, ", status = %d", performed_min_);
215 if (performed_max_ != performed_min_) {
226 if (var_ != element.var_) {
237 return start_min_ == element.start_min_ && start_max_ == element.start_max_ &&
238 duration_min_ == element.duration_min_ &&
239 duration_max_ == element.duration_max_ &&
240 end_min_ == element.end_min_ && end_max_ == element.end_max_ &&
241 performed_min_ == element.performed_min_ &&
242 performed_max_ == element.performed_max_ && var_ == element.var_;
265 forward_sequence_ = element.forward_sequence_;
266 backward_sequence_ = element.backward_sequence_;
277 var_->FillSequence(&forward_sequence_, &backward_sequence_, &unperformed_);
286 for (const int32_t forward_sequence :
288 forward_sequence_.push_back(forward_sequence);
290 for (const int32_t backward_sequence :
292 backward_sequence_.push_back(backward_sequence);
294 for (const int32_t unperformed :
295 sequence_var_assignment_proto.unperformed()) {
296 unperformed_.push_back(unperformed);
298 if (sequence_var_assignment_proto.active()) {
308 sequence_var_assignment_proto->set_var_id(var_->name());
310 for (const int forward_sequence : forward_sequence_) {
313 for (const int backward_sequence : backward_sequence_) {
316 for (const int unperformed : unperformed_) {
317 sequence_var_assignment_proto->add_unperformed(unperformed);
323 return absl::StrFormat("[forward %s, backward %s, unperformed [%s]]",
324 absl::StrJoin(forward_sequence_, " -> "),
325 absl::StrJoin(backward_sequence_, " -> "),
333 if (var_ != element.var_) {
344 return forward_sequence_ == element.forward_sequence_ &&
345 backward_sequence_ == element.backward_sequence_ &&
362 const std::vector<int>& backward_sequence,
363 const std::vector<int>& unperformed) {
364 forward_sequence_ = forward_sequence;
365 backward_sequence_ = backward_sequence;
366 unperformed_ = unperformed;
384bool SequenceVarElement::CheckClassInvariants() {
385 absl::flat_hash_set<int> visited;
386 for (const int forward_sequence : forward_sequence_) {
387 if (visited.contains(forward_sequence)) {
390 visited.insert(forward_sequence);
392 for (const int backward_sequence : backward_sequence_) {
393 if (visited.contains(backward_sequence)) {
396 visited.insert(backward_sequence);
398 for (const int unperformed : unperformed_) {
399 if (visited.contains(unperformed)) {
402 visited.insert(unperformed);
411 int_var_container_(copy->int_var_container_),
412 interval_var_container_(copy->interval_var_container_),
420 objective_elements_.clear();
421 int_var_container_.Clear();
422 interval_var_container_.Clear();
427 int_var_container_.Store();
428 interval_var_container_.Store();
429 sequence_var_container_.Store();
430 for (IntVarElement& objective_element : objective_elements_) {
437 int_var_container_.Restore();
438 interval_var_container_.Restore();
445template <class V, class E>
447 absl::flat_hash_map<std::string, E*>* id_to_element_map) {
448 CHECK(id_to_element_map != nullptr);
449 id_to_element_map->clear();
450 for (int i = 0; i < container->Size(); ++i) {
452 const V* const var = element->Var();
453 const std::string& name = var->name();
455 LOG(INFO) << "Cannot save/load variables with empty name"
456 << "; variable will be ignored";
457 } else if (id_to_element_map->contains(name)) {
458 LOG(INFO) << "Cannot save/load variables with duplicate names: " << name
459 << "; variable will be ignored";
461 (*id_to_element_map)[name] = element;
466template <class E, class P>
467void LoadElement(const absl::flat_hash_map<std::string, E*>& id_to_element_map,
469 absl::string_view var_id = proto.var_id();
472 if (gtl::FindCopy(id_to_element_map, var_id, &element)) {
473 element->LoadFromProto(proto);
475 LOG(INFO) << "Variable " << var_id
476 << " not in assignment; skipping variable";
492 CHECK(file != nullptr);
496 LOG(INFO) << "No assignment found in " << file->filename();
499 Load(assignment_proto);
500 return reader.Close();
503template <class Var, class Element, class Proto, class Container>
505 Container* const container,
508 bool fast_load = (container->Size() == (assignment_proto.*GetSize)());
509 for (int i = 0; fast_load && i < (assignment_proto.*GetSize)(); ++i) {
510 Element* const element = container->MutableElement(i);
511 const Proto& proto = (assignment_proto.*GetElem)(i);
512 if (element->Var()->name() == proto.var_id()) {
513 element->LoadFromProto(proto);
519 absl::flat_hash_map<std::string, Element*> id_to_element_map;
520 IdToElementMap<Var, Element>(container, &id_to_element_map);
521 for (int i = 0; i < (assignment_proto.*GetSize)(); ++i) {
522 LoadElement<Element, Proto>(id_to_element_map,
530 assignment_proto, &int_var_container_,
541 for (int i = 0; i < assignment_proto.objective_size(); ++i) {
543 absl::string_view objective_id = objective.var_id();
544 DCHECK(!objective_id.empty());
547 const int64_t obj_min = objective.min();
548 const int64_t obj_max = objective.max();
550 if (objective.active()) {
576template <class Var, class Element, class Proto, class Container>
578 const Container& container, Proto* (AssignmentProto::*Add)()) {
579 for (const Element& element : container.elements()) {
580 const Var* const var = element.Var();
581 const std::string& name = var->name();
583 Proto* const var_assignment_proto = (assignment_proto->*Add)();
590 assignment_proto->Clear();
592 assignment_proto, int_var_container_,
600 for (int i = 0; i < objective_elements_.size(); ++i) {
602 if (!name.empty()) {
612template <class Container, class Element>
613void RealDebugString(const Container& container, std::string* const out) {
614 for (const Element& element : container.elements()) {
615 if (element.Var() != nullptr) {
616 absl::StrAppendFormat(out, "%s %s | ", element.Var()->name(),
623 std::string out = "Assignment(";
626 interval_var_container_, &out);
628 sequence_var_container_, &out);
629 std::vector<std::string> objective_str;
630 for (const IntVarElement& objective_element : objective_elements_) {
631 if (objective_element.Activated()) {
632 objective_str.push_back(objective_element.DebugString());
635 absl::StrAppendFormat(&out, "%s)", absl::StrJoin(objective_str, ", "));
654 return int_var_container_.Element(var).Min();
850 const std::vector<int>& forward_sequence,
851 const std::vector<int>& backward_sequence,
852 const std::vector<int>& unperformed) {
853 sequence_var_container_.MutableElement(var)->SetSequence(
858 const std::vector<int>& forward_sequence) {
859 sequence_var_container_.MutableElement(var)->SetForwardSequence(
864 const SequenceVar* const var, const std::vector<int>& backward_sequence) {
865 sequence_var_container_.MutableElement(var)->SetBackwardSequence(
870 const std::vector<int>& unperformed) {
871 sequence_var_container_.MutableElement(var)->SetUnperformed(unperformed);
923 int_var_container_.CopyIntersection(assignment->int_var_container_);
924 interval_var_container_.CopyIntersection(assignment->interval_var_container_);
925 sequence_var_container_.CopyIntersection(assignment->sequence_var_container_);
926 for (int i = 0; i < objective_elements_.size(); i++) {
927 if (i >= assignment->objective_elements_.size() ||
931 objective_elements_[i].Var() !=
932 assignment->objective_elements_[i].Var()) {
935 objective_elements_[i] = assignment->objective_elements_[i];
941 int_var_container_.Copy(assignment->int_var_container_);
942 interval_var_container_.Copy(assignment->interval_var_container_);
943 sequence_var_container_.Copy(assignment->sequence_var_container_);
948 const std::vector<IntVar*>& target_vars,
950 const std::vector<IntVar*>& source_vars) {
951 const int vars_size = target_vars.size();
952 CHECK_EQ(source_vars.size(), vars_size);
953 CHECK(target_assignment != nullptr);
954 CHECK(source_assignment != nullptr);
956 target_assignment->Clear();
957 const Solver* const target_solver = target_assignment->solver();
958 const Solver* const source_solver = source_assignment->solver();
959 for (int index = 0; index < vars_size; index++) {
960 IntVar* target_var = target_vars[index];
961 CHECK_EQ(target_var->solver(), target_solver);
962 IntVar* source_var = source_vars[index];
963 CHECK_EQ(source_var->solver(), source_solver);
964 target_assignment->Add(target_var)
979 explicit RestoreAssignment(Assignment* assignment)
980 : assignment_(assignment) {}
982 ~RestoreAssignment() override {}
984 Decision* Next(Solver* const ) override {
989 std::string DebugString() const override { return "RestoreAssignment"; }
992 Assignment* const assignment_;
997 explicit StoreAssignment(Assignment* assignment) : assignment_(assignment) {}
999 ~StoreAssignment() override {}
1001 Decision* Next(Solver* const ) override {
1006 std::string DebugString() const override { return "StoreAssignment"; }
1009 Assignment* const assignment_;
1014 return RevAlloc(new RestoreAssignment(assignment));
1018 return RevAlloc(new StoreAssignment(assignment));
E * MutableElement(const V *const var)
int objective_size() const
::operations_research::SequenceVarAssignment *PROTOBUF_NONNULL add_sequence_var_assignment()
const ::operations_research::SequenceVarAssignment & sequence_var_assignment(int index) const
ABSL_ATTRIBUTE_REINITIALIZES void Clear() PROTOBUF_FINAL
int interval_var_assignment_size() const
const ::operations_research::IntVarAssignment & objective(int index) const
::operations_research::IntervalVarAssignment *PROTOBUF_NONNULL add_interval_var_assignment()
const ::operations_research::IntervalVarAssignment & interval_var_assignment(int index) const
int int_var_assignment_size() const
::operations_research::IntVarAssignment *PROTOBUF_NONNULL add_int_var_assignment()
int sequence_var_assignment_size() const
::operations_research::IntVarAssignment *PROTOBUF_NONNULL add_objective()
const ::operations_research::IntVarAssignment & int_var_assignment(int index) const
void Activate(const IntVar *var)
Definition assignment.cc:874
Assignment(Solver *solver)
Definition assignment.cc:416
void SetPerformedRange(const IntervalVar *var, int64_t mi, int64_t ma)
Definition assignment.cc:808
AssignmentContainer< SequenceVar, SequenceVarElement > SequenceContainer
int64_t Value(const IntVar *var) const
Definition assignment.cc:661
void SetStartMax(const IntervalVar *var, int64_t m)
Definition assignment.cc:753
void Restore()
Definition assignment.cc:435
void SetMax(const IntVar *var, int64_t m)
Definition assignment.cc:673
void SetForwardSequence(const SequenceVar *var, const std::vector< int > &forward_sequence)
Definition assignment.cc:857
int64_t EndMin(const IntervalVar *var) const
Definition assignment.cc:725
bool Activated(const IntVar *var) const
Definition assignment.cc:882
int64_t DurationMax(const IntervalVar *var) const
Definition assignment.cc:717
int64_t PerformedMin(const IntervalVar *var) const
Definition assignment.cc:737
int64_t Max(const IntVar *var) const
Definition assignment.cc:657
void SetBackwardSequence(const SequenceVar *var, const std::vector< int > &backward_sequence)
Definition assignment.cc:863
int64_t Min(const IntVar *var) const
Definition assignment.cc:653
void SetEndValue(const IntervalVar *var, int64_t value)
Definition assignment.cc:796
bool Contains(const IntVar *var) const
Definition assignment.cc:910
void SetValue(const IntVar *var, int64_t value)
Definition assignment.cc:681
void SetEndMin(const IntervalVar *var, int64_t m)
Definition assignment.cc:783
bool Load(const std::string &filename)
Definition assignment.cc:482
int64_t EndValue(const IntervalVar *var) const
Definition assignment.cc:733
void SetMin(const IntVar *var, int64_t m)
Definition assignment.cc:669
void DeactivateObjectiveFromIndex(int index)
const std::vector< int > & Unperformed(const SequenceVar *var) const
Definition assignment.cc:844
void SetPerformedValue(const IntervalVar *var, int64_t value)
Definition assignment.cc:813
int64_t PerformedValue(const IntervalVar *var) const
Definition assignment.cc:745
int64_t StartValue(const IntervalVar *var) const
Definition assignment.cc:709
IntVarElement * Add(IntVar *var)
Definition assignment.cc:639
void SetPerformedMax(const IntervalVar *var, int64_t m)
Definition assignment.cc:804
~Assignment() override
Definition assignment.cc:417
void ActivateObjectiveFromIndex(int index)
int64_t ObjectiveMinFromIndex(int index) const
std::string DebugString() const override
Definition assignment.cc:622
int64_t EndMax(const IntervalVar *var) const
Definition assignment.cc:729
void Store()
Definition assignment.cc:426
int64_t StartMin(const IntervalVar *var) const
Definition assignment.cc:701
IntVarElement * FastAdd(IntVar *var)
Adds without checking if variable has been previously added.
Definition assignment.cc:649
void Deactivate(const IntVar *var)
Definition assignment.cc:878
void Copy(const Assignment *assignment)
Definition assignment.cc:939
const std::vector< int > & ForwardSequence(const SequenceVar *var) const
Definition assignment.cc:834
void SetRange(const IntVar *var, int64_t l, int64_t u)
Definition assignment.cc:677
int64_t ObjectiveMaxFromIndex(int index) const
void Clear()
Definition assignment.cc:419
bool ActivatedObjectiveFromIndex(int index) const
int64_t DurationMin(const IntervalVar *var) const
Definition assignment.cc:713
bool Bound(const IntVar *var) const
Definition assignment.cc:665
int64_t DurationValue(const IntervalVar *var) const
Definition assignment.cc:721
AssignmentContainer< IntervalVar, IntervalVarElement > IntervalContainer
void SetSequence(const SequenceVar *var, const std::vector< int > &forward_sequence, const std::vector< int > &backward_sequence, const std::vector< int > &unperformed)
Definition assignment.cc:849
void SetStartMin(const IntervalVar *var, int64_t m)
Definition assignment.cc:749
void SetDurationMin(const IntervalVar *var, int64_t m)
Definition assignment.cc:766
void SetStartValue(const IntervalVar *var, int64_t value)
Definition assignment.cc:762
void SetDurationMax(const IntervalVar *var, int64_t m)
Definition assignment.cc:770
void SetEndMax(const IntervalVar *var, int64_t m)
Definition assignment.cc:787
void SetStartRange(const IntervalVar *var, int64_t mi, int64_t ma)
Definition assignment.cc:757
void SetDurationValue(const IntervalVar *var, int64_t value)
Definition assignment.cc:779
void CopyIntersection(const Assignment *assignment)
Definition assignment.cc:922
void SetEndRange(const IntervalVar *var, int64_t mi, int64_t ma)
Definition assignment.cc:791
void SetDurationRange(const IntervalVar *var, int64_t mi, int64_t ma)
Definition assignment.cc:774
bool HasObjectiveFromIndex(int index) const
int64_t StartMax(const IntervalVar *var) const
Definition assignment.cc:705
IntVar * ObjectiveFromIndex(int index) const
bool Save(const std::string &filename) const
Saves the assignment to a file.
Definition assignment.cc:559
const std::vector< int > & BackwardSequence(const SequenceVar *var) const
Definition assignment.cc:839
void SetPerformedMin(const IntervalVar *var, int64_t m)
Definition assignment.cc:800
void SetObjectiveRangeFromIndex(int index, int64_t l, int64_t u)
void SetUnperformed(const SequenceVar *var, const std::vector< int > &unperformed)
Definition assignment.cc:869
int64_t PerformedMax(const IntervalVar *var) const
Definition assignment.cc:741
void set_max(::int64_t value)
const ::std::string & var_id() const
void set_active(bool value)
void set_var_id(Arg_ &&arg, Args_... args)
void set_min(::int64_t value)
void Reset(IntVar *var)
Definition assignment.cc:43
bool operator==(const IntVarElement &element) const
Definition assignment.cc:76
void SetRange(int64_t l, int64_t u)
IntVarElement * Clone()
Definition assignment.cc:49
IntVarElement()
Definition assignment.cc:39
std::string DebugString() const
Definition assignment.cc:99
void Copy(const IntVarElement &element)
Definition assignment.cc:55
void WriteToProto(IntVarAssignment *int_var_assignment_proto) const
Definition assignment.cc:91
void LoadFromProto(const IntVarAssignment &int_var_assignment_proto)
Definition assignment.cc:65
void set_end_max(::int64_t value)
::int64_t start_min() const
::int64_t duration_max() const
::int64_t performed_max() const
void set_duration_max(::int64_t value)
void set_end_min(::int64_t value)
::int64_t duration_min() const
void set_var_id(Arg_ &&arg, Args_... args)
::int64_t start_max() const
void set_active(bool value)
void set_start_min(::int64_t value)
void set_performed_max(::int64_t value)
void set_duration_min(::int64_t value)
void set_performed_min(::int64_t value)
void set_start_max(::int64_t value)
::int64_t performed_min() const
::int64_t end_min() const
::int64_t end_max() const
void SetDurationRange(int64_t mi, int64_t ma)
IntervalVarElement * Clone()
Definition assignment.cc:129
std::string DebugString() const
Definition assignment.cc:203
void WriteToProto(IntervalVarAssignment *interval_var_assignment_proto) const
Definition assignment.cc:189
void Reset(IntervalVar *var)
Definition assignment.cc:117
void Copy(const IntervalVarElement &element)
Definition assignment.cc:135
void SetEndRange(int64_t mi, int64_t ma)
IntervalVarElement()
Definition assignment.cc:113
bool operator==(const IntervalVarElement &element) const
Definition assignment.cc:225
void SetStartRange(int64_t mi, int64_t ma)
void Store()
Definition assignment.cc:148
void SetPerformedRange(int64_t mi, int64_t ma)
void LoadFromProto(const IntervalVarAssignment &interval_var_assignment_proto)
Definition assignment.cc:172
void Restore()
Definition assignment.cc:161
virtual std::string name() const
Object naming.
PropagationBaseObject(Solver *const s)
void set_active(bool value)
::int32_t forward_sequence(int index) const
void add_forward_sequence(::int32_t value)
::int32_t backward_sequence(int index) const
void set_var_id(Arg_ &&arg, Args_... args)
void add_backward_sequence(::int32_t value)
void add_unperformed(::int32_t value)
::int32_t unperformed(int index) const
void Restore()
Definition assignment.cc:280
void Reset(SequenceVar *var)
Definition assignment.cc:251
void WriteToProto(SequenceVarAssignment *sequence_var_assignment_proto) const
Definition assignment.cc:306
bool operator==(const SequenceVarElement &element) const
Definition assignment.cc:332
std::string DebugString() const
Definition assignment.cc:321
SequenceVarElement * Clone()
Definition assignment.cc:258
SequenceVarElement()
Definition assignment.cc:247
void Store()
Definition assignment.cc:276
void SetUnperformed(const std::vector< int > &unperformed)
Definition assignment.cc:380
const std::vector< int > & ForwardSequence() const
Definition assignment.cc:349
void Copy(const SequenceVarElement &element)
Definition assignment.cc:264
void SetBackwardSequence(const std::vector< int > &backward_sequence)
Definition assignment.cc:375
const std::vector< int > & BackwardSequence() const
Definition assignment.cc:353
void SetSequence(const std::vector< int > &forward_sequence, const std::vector< int > &backward_sequence, const std::vector< int > &unperformed)
Definition assignment.cc:361
void SetForwardSequence(const std::vector< int > &forward_sequence)
Definition assignment.cc:370
void LoadFromProto(const SequenceVarAssignment &sequence_var_assignment_proto)
Definition assignment.cc:284
const std::vector< int > & Unperformed() const
Definition assignment.cc:357
void FillSequence(std::vector< int > *rank_first, std::vector< int > *rank_last, std::vector< int > *unperformed) const
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
Definition assignment.cc:1013
DecisionBuilder * MakeStoreAssignment(Assignment *assignment)
Definition assignment.cc:1017
bool ReadProtocolMessage(P *const proto)
bool WriteProtocolMessage(const P &proto)
absl::Status Open(absl::string_view file_name, absl::string_view mode, File **f, Options options)
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
void StoreAssignment(const VariablesAssignment &assignment, BooleanAssignment *output)
void RealLoad(const AssignmentProto &assignment_proto, Container *const container, int(AssignmentProto::*GetSize)() const, const Proto &(AssignmentProto::*GetElem)(int) const)
Definition assignment.cc:504
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
Definition assignment.cc:1021
void RealDebugString(const Container &container, std::string *const out)
Definition assignment.cc:613
void SetAssignmentFromAssignment(Assignment *target_assignment, const std::vector< IntVar * > &target_vars, const Assignment *source_assignment, const std::vector< IntVar * > &source_vars)
NOLINT.
Definition assignment.cc:947
void RealSave(AssignmentProto *const assignment_proto, const Container &container, Proto *(AssignmentProto::*Add)())
Definition assignment.cc:577