OR-Tools  8.2
constraint_solver/assignment.cc
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #include <stddef.h>
15 
16 #include <string>
17 #include <vector>
18 
19 #include "absl/container/flat_hash_map.h"
20 #include "absl/strings/str_format.h"
21 #include "absl/strings/str_join.h"
22 #include "ortools/base/file.h"
23 #include "ortools/base/hash.h"
25 #include "ortools/base/logging.h"
26 #include "ortools/base/map_util.h"
27 #include "ortools/base/recordio.h"
28 #include "ortools/constraint_solver/assignment.pb.h"
30 
31 namespace operations_research {
32 
33 // ----------------- Solutions ------------------------
34 
35 // ----- IntVarElement -----
36 
38 
40 
42  var_ = var;
43  min_ = kint64min;
44  max_ = kint64max;
45 }
46 
48  IntVarElement* element = new IntVarElement;
49  element->Copy(*this);
50  return element;
51 }
52 
53 void IntVarElement::Copy(const IntVarElement& element) {
54  SetRange(element.min_, element.max_);
55  var_ = element.var_;
56  if (element.Activated()) {
57  Activate();
58  } else {
59  Deactivate();
60  }
61 }
62 
64  const IntVarAssignment& int_var_assignment_proto) {
65  min_ = int_var_assignment_proto.min();
66  max_ = int_var_assignment_proto.max();
67  if (int_var_assignment_proto.active()) {
68  Activate();
69  } else {
70  Deactivate();
71  }
72 }
73 
74 bool IntVarElement::operator==(const IntVarElement& element) const {
75  if (var_ != element.var_) {
76  return false;
77  }
78  if (Activated() != element.Activated()) {
79  return false;
80  }
81  if (!Activated() && !element.Activated()) {
82  // If both elements are deactivated, then they are equal, regardless of
83  // their min and max.
84  return true;
85  }
86  return min_ == element.min_ && max_ == element.max_;
87 }
88 
90  IntVarAssignment* int_var_assignment_proto) const {
91  int_var_assignment_proto->set_var_id(var_->name());
92  int_var_assignment_proto->set_min(min_);
93  int_var_assignment_proto->set_max(max_);
94  int_var_assignment_proto->set_active(Activated());
95 }
96 
97 std::string IntVarElement::DebugString() const {
98  if (Activated()) {
99  if (min_ == max_) {
100  return absl::StrFormat("(%d)", min_);
101  } else {
102  return absl::StrFormat("(%d..%d)", min_, max_);
103  }
104  } else {
105  return "(...)";
106  }
107 }
108 
109 // ----- IntervalVarElement -----
110 
112 
114 
116  var_ = var;
117  start_min_ = kint64min;
118  start_max_ = kint64max;
119  duration_min_ = kint64min;
120  duration_max_ = kint64max;
121  end_min_ = kint64min;
122  end_max_ = kint64max;
123  performed_min_ = 0;
124  performed_max_ = 1;
125 }
126 
128  IntervalVarElement* element = new IntervalVarElement;
129  element->Copy(*this);
130  return element;
131 }
132 
134  SetStartRange(element.start_min_, element.start_max_);
135  SetDurationRange(element.duration_min_, element.duration_max_);
136  SetEndRange(element.end_min_, element.end_max_);
137  SetPerformedRange(element.performed_min_, element.performed_max_);
138  var_ = element.var_;
139  if (element.Activated()) {
140  Activate();
141  } else {
142  Deactivate();
143  }
144 }
145 
147  performed_min_ = static_cast<int64>(var_->MustBePerformed());
148  performed_max_ = static_cast<int64>(var_->MayBePerformed());
149  if (performed_max_ != 0LL) {
150  start_min_ = var_->StartMin();
151  start_max_ = var_->StartMax();
152  duration_min_ = var_->DurationMin();
153  duration_max_ = var_->DurationMax();
154  end_min_ = var_->EndMin();
155  end_max_ = var_->EndMax();
156  }
157 }
158 
160  if (performed_max_ == performed_min_) {
161  var_->SetPerformed(performed_min_);
162  }
163  if (performed_max_ != 0LL) {
164  var_->SetStartRange(start_min_, start_max_);
165  var_->SetDurationRange(duration_min_, duration_max_);
166  var_->SetEndRange(end_min_, end_max_);
167  }
168 }
169 
171  const IntervalVarAssignment& interval_var_assignment_proto) {
172  start_min_ = interval_var_assignment_proto.start_min();
173  start_max_ = interval_var_assignment_proto.start_max();
174  duration_min_ = interval_var_assignment_proto.duration_min();
175  duration_max_ = interval_var_assignment_proto.duration_max();
176  end_min_ = interval_var_assignment_proto.end_min();
177  end_max_ = interval_var_assignment_proto.end_max();
178  performed_min_ = interval_var_assignment_proto.performed_min();
179  performed_max_ = interval_var_assignment_proto.performed_max();
180  if (interval_var_assignment_proto.active()) {
181  Activate();
182  } else {
183  Deactivate();
184  }
185 }
186 
188  IntervalVarAssignment* interval_var_assignment_proto) const {
189  interval_var_assignment_proto->set_var_id(var_->name());
190  interval_var_assignment_proto->set_start_min(start_min_);
191  interval_var_assignment_proto->set_start_max(start_max_);
192  interval_var_assignment_proto->set_duration_min(duration_min_);
193  interval_var_assignment_proto->set_duration_max(duration_max_);
194  interval_var_assignment_proto->set_end_min(end_min_);
195  interval_var_assignment_proto->set_end_max(end_max_);
196  interval_var_assignment_proto->set_performed_min(performed_min_);
197  interval_var_assignment_proto->set_performed_max(performed_max_);
198  interval_var_assignment_proto->set_active(Activated());
199 }
200 
201 std::string IntervalVarElement::DebugString() const {
202  if (Activated()) {
203  std::string out;
204  absl::StrAppendFormat(&out, "(start = %d", start_min_);
205  if (start_max_ != start_min_) {
206  absl::StrAppendFormat(&out, "..%d", start_max_);
207  }
208  absl::StrAppendFormat(&out, ", duration = %d", duration_min_);
209  if (duration_max_ != duration_min_) {
210  absl::StrAppendFormat(&out, "..%d", duration_max_);
211  }
212  absl::StrAppendFormat(&out, ", status = %d", performed_min_);
213  if (performed_max_ != performed_min_) {
214  absl::StrAppendFormat(&out, "..%d", performed_max_);
215  }
216  out.append(")");
217  return out;
218  } else {
219  return "(...)";
220  }
221 }
222 
224  if (var_ != element.var_) {
225  return false;
226  }
227  if (Activated() != element.Activated()) {
228  return false;
229  }
230  if (!Activated() && !element.Activated()) {
231  // If both elements are deactivated, then they are equal, regardless of
232  // their other fields.
233  return true;
234  }
235  return start_min_ == element.start_min_ && start_max_ == element.start_max_ &&
236  duration_min_ == element.duration_min_ &&
237  duration_max_ == element.duration_max_ &&
238  end_min_ == element.end_min_ && end_max_ == element.end_max_ &&
239  performed_min_ == element.performed_min_ &&
240  performed_max_ == element.performed_max_ && var_ == element.var_;
241 }
242 
243 // ----- SequenceVarElement -----
244 
246 
248 
250  var_ = var;
251  forward_sequence_.clear();
252  backward_sequence_.clear();
253  unperformed_.clear();
254 }
255 
257  SequenceVarElement* const element = new SequenceVarElement;
258  element->Copy(*this);
259  return element;
260 }
261 
263  forward_sequence_ = element.forward_sequence_;
264  backward_sequence_ = element.backward_sequence_;
265  unperformed_ = element.unperformed_;
266  var_ = element.var_;
267  if (element.Activated()) {
268  Activate();
269  } else {
270  Deactivate();
271  }
272 }
273 
275  var_->FillSequence(&forward_sequence_, &backward_sequence_, &unperformed_);
276 }
277 
279  var_->RankSequence(forward_sequence_, backward_sequence_, unperformed_);
280 }
281 
283  const SequenceVarAssignment& sequence_var_assignment_proto) {
284  for (const int32 forward_sequence :
285  sequence_var_assignment_proto.forward_sequence()) {
286  forward_sequence_.push_back(forward_sequence);
287  }
288  for (const int32 backward_sequence :
289  sequence_var_assignment_proto.backward_sequence()) {
290  backward_sequence_.push_back(backward_sequence);
291  }
292  for (const int32 unperformed : sequence_var_assignment_proto.unperformed()) {
293  unperformed_.push_back(unperformed);
294  }
295  if (sequence_var_assignment_proto.active()) {
296  Activate();
297  } else {
298  Deactivate();
299  }
300  DCHECK(CheckClassInvariants());
301 }
302 
304  SequenceVarAssignment* sequence_var_assignment_proto) const {
305  sequence_var_assignment_proto->set_var_id(var_->name());
306  sequence_var_assignment_proto->set_active(Activated());
307  for (const int forward_sequence : forward_sequence_) {
308  sequence_var_assignment_proto->add_forward_sequence(forward_sequence);
309  }
310  for (const int backward_sequence : backward_sequence_) {
311  sequence_var_assignment_proto->add_backward_sequence(backward_sequence);
312  }
313  for (const int unperformed : unperformed_) {
314  sequence_var_assignment_proto->add_unperformed(unperformed);
315  }
316 }
317 
318 std::string SequenceVarElement::DebugString() const {
319  if (Activated()) {
320  return absl::StrFormat("[forward %s, backward %s, unperformed [%s]]",
321  absl::StrJoin(forward_sequence_, " -> "),
322  absl::StrJoin(backward_sequence_, " -> "),
323  absl::StrJoin(unperformed_, ", "));
324  } else {
325  return "(...)";
326  }
327 }
328 
330  if (var_ != element.var_) {
331  return false;
332  }
333  if (Activated() != element.Activated()) {
334  return false;
335  }
336  if (!Activated() && !element.Activated()) {
337  // If both elements are deactivated, then they are equal, regardless of
338  // their other fields.
339  return true;
340  }
341  return forward_sequence_ == element.forward_sequence_ &&
342  backward_sequence_ == element.backward_sequence_ &&
343  unperformed_ == element.unperformed_;
344 }
345 
346 const std::vector<int>& SequenceVarElement::ForwardSequence() const {
347  return forward_sequence_;
348 }
349 
350 const std::vector<int>& SequenceVarElement::BackwardSequence() const {
351  return backward_sequence_;
352 }
353 
354 const std::vector<int>& SequenceVarElement::Unperformed() const {
355  return unperformed_;
356 }
357 
358 void SequenceVarElement::SetSequence(const std::vector<int>& forward_sequence,
359  const std::vector<int>& backward_sequence,
360  const std::vector<int>& unperformed) {
361  forward_sequence_ = forward_sequence;
362  backward_sequence_ = backward_sequence;
363  unperformed_ = unperformed;
364  DCHECK(CheckClassInvariants());
365 }
366 
368  const std::vector<int>& forward_sequence) {
369  forward_sequence_ = forward_sequence;
370 }
371 
373  const std::vector<int>& backward_sequence) {
374  backward_sequence_ = backward_sequence;
375 }
376 
377 void SequenceVarElement::SetUnperformed(const std::vector<int>& unperformed) {
378  unperformed_ = unperformed;
379 }
380 
381 bool SequenceVarElement::CheckClassInvariants() {
382  absl::flat_hash_set<int> visited;
383  for (const int forward_sequence : forward_sequence_) {
384  if (gtl::ContainsKey(visited, forward_sequence)) {
385  return false;
386  }
387  visited.insert(forward_sequence);
388  }
389  for (const int backward_sequence : backward_sequence_) {
390  if (gtl::ContainsKey(visited, backward_sequence)) {
391  return false;
392  }
393  visited.insert(backward_sequence);
394  }
395  for (const int unperformed : unperformed_) {
396  if (gtl::ContainsKey(visited, unperformed)) {
397  return false;
398  }
399  visited.insert(unperformed);
400  }
401  return true;
402 }
403 
404 // ----- Assignment -----
405 
407  : PropagationBaseObject(copy->solver()),
408  int_var_container_(copy->int_var_container_),
409  interval_var_container_(copy->interval_var_container_),
410  sequence_var_container_(copy->sequence_var_container_),
411  objective_element_(copy->objective_element_) {}
412 
414  : PropagationBaseObject(s), objective_element_(nullptr) {}
415 
417 
419  objective_element_.Reset(nullptr);
420  int_var_container_.Clear();
421  interval_var_container_.Clear();
422  sequence_var_container_.Clear();
423 }
424 
426  int_var_container_.Store();
427  interval_var_container_.Store();
428  sequence_var_container_.Store();
429  if (HasObjective()) {
430  objective_element_.Store();
431  }
432 }
433 
435  FreezeQueue();
436  int_var_container_.Restore();
437  interval_var_container_.Restore();
438  sequence_var_container_.Restore();
439  UnfreezeQueue();
440 }
441 
442 namespace {
443 
444 template <class V, class E>
445 void IdToElementMap(AssignmentContainer<V, E>* container,
446  absl::flat_hash_map<std::string, E*>* id_to_element_map) {
447  CHECK(id_to_element_map != nullptr);
448  id_to_element_map->clear();
449  for (int i = 0; i < container->Size(); ++i) {
450  E* const element = container->MutableElement(i);
451  const V* const var = element->Var();
452  const std::string& name = var->name();
453  if (name.empty()) {
454  LOG(INFO) << "Cannot save/load variables with empty name"
455  << "; variable will be ignored";
456  } else if (gtl::ContainsKey(*id_to_element_map, name)) {
457  LOG(INFO) << "Cannot save/load variables with duplicate names: " << name
458  << "; variable will be ignored";
459  } else {
460  (*id_to_element_map)[name] = element;
461  }
462  }
463 }
464 
465 template <class E, class P>
466 void LoadElement(const absl::flat_hash_map<std::string, E*>& id_to_element_map,
467  const P& proto) {
468  const std::string& var_id = proto.var_id();
469  CHECK(!var_id.empty());
470  E* element = nullptr;
471  if (gtl::FindCopy(id_to_element_map, var_id, &element)) {
472  element->LoadFromProto(proto);
473  } else {
474  LOG(INFO) << "Variable " << var_id
475  << " not in assignment; skipping variable";
476  }
477 }
478 
479 } // namespace
480 
481 bool Assignment::Load(const std::string& filename) {
482  File* file;
483  if (!file::Open(filename, "r", &file, file::Defaults()).ok()) {
484  LOG(INFO) << "Cannot open " << filename;
485  return false;
486  }
487  return Load(file);
488 }
489 
491  CHECK(file != nullptr);
492  AssignmentProto assignment_proto;
494  if (!reader.ReadProtocolMessage(&assignment_proto)) {
495  LOG(INFO) << "No assignment found in " << file->filename();
496  return false;
497  }
498  Load(assignment_proto);
499  return reader.Close();
500 }
501 
502 template <class Var, class Element, class Proto, class Container>
503 void RealLoad(const AssignmentProto& assignment_proto,
504  Container* const container,
505  int (AssignmentProto::*GetSize)() const,
506  const Proto& (AssignmentProto::*GetElem)(int) const) {
507  bool fast_load = (container->Size() == (assignment_proto.*GetSize)());
508  for (int i = 0; fast_load && i < (assignment_proto.*GetSize)(); ++i) {
509  Element* const element = container->MutableElement(i);
510  const Proto& proto = (assignment_proto.*GetElem)(i);
511  if (element->Var()->name() == proto.var_id()) {
512  element->LoadFromProto(proto);
513  } else {
514  fast_load = false;
515  }
516  }
517  if (!fast_load) {
518  absl::flat_hash_map<std::string, Element*> id_to_element_map;
519  IdToElementMap<Var, Element>(container, &id_to_element_map);
520  for (int i = 0; i < (assignment_proto.*GetSize)(); ++i) {
521  LoadElement<Element, Proto>(id_to_element_map,
522  (assignment_proto.*GetElem)(i));
523  }
524  }
525 }
526 
527 void Assignment::Load(const AssignmentProto& assignment_proto) {
528  RealLoad<IntVar, IntVarElement, IntVarAssignment, IntContainer>(
529  assignment_proto, &int_var_container_,
530  &AssignmentProto::int_var_assignment_size,
531  &AssignmentProto::int_var_assignment);
532  RealLoad<IntervalVar, IntervalVarElement, IntervalVarAssignment,
533  IntervalContainer>(assignment_proto, &interval_var_container_,
534  &AssignmentProto::interval_var_assignment_size,
535  &AssignmentProto::interval_var_assignment);
536  RealLoad<SequenceVar, SequenceVarElement, SequenceVarAssignment,
537  SequenceContainer>(assignment_proto, &sequence_var_container_,
538  &AssignmentProto::sequence_var_assignment_size,
539  &AssignmentProto::sequence_var_assignment);
540  if (assignment_proto.has_objective()) {
541  const IntVarAssignment& objective = assignment_proto.objective();
542  const std::string& objective_id = objective.var_id();
543  CHECK(!objective_id.empty());
544  if (HasObjective() && objective_id == Objective()->name()) {
545  const int64 obj_min = objective.min();
546  const int64 obj_max = objective.max();
547  SetObjectiveRange(obj_min, obj_max);
548  if (objective.active()) {
550  } else {
552  }
553  }
554  }
555 }
556 
557 bool Assignment::Save(const std::string& filename) const {
558  File* file;
559  if (!file::Open(filename, "w", &file, file::Defaults()).ok()) {
560  LOG(INFO) << "Cannot open " << filename;
561  return false;
562  }
563  return Save(file);
564 }
565 
566 bool Assignment::Save(File* file) const {
567  CHECK(file != nullptr);
568  AssignmentProto assignment_proto;
569  Save(&assignment_proto);
571  return writer.WriteProtocolMessage(assignment_proto) && writer.Close();
572 }
573 
574 template <class Var, class Element, class Proto, class Container>
575 void RealSave(AssignmentProto* const assignment_proto,
576  const Container& container, Proto* (AssignmentProto::*Add)()) {
577  for (const Element& element : container.elements()) {
578  const Var* const var = element.Var();
579  const std::string& name = var->name();
580  if (!name.empty()) {
581  Proto* const var_assignment_proto = (assignment_proto->*Add)();
582  element.WriteToProto(var_assignment_proto);
583  }
584  }
585 }
586 
587 void Assignment::Save(AssignmentProto* const assignment_proto) const {
588  assignment_proto->Clear();
589  RealSave<IntVar, IntVarElement, IntVarAssignment, IntContainer>(
590  assignment_proto, int_var_container_,
591  &AssignmentProto::add_int_var_assignment);
592  RealSave<IntervalVar, IntervalVarElement, IntervalVarAssignment,
593  IntervalContainer>(assignment_proto, interval_var_container_,
594  &AssignmentProto::add_interval_var_assignment);
595  RealSave<SequenceVar, SequenceVarElement, SequenceVarAssignment,
596  SequenceContainer>(assignment_proto, sequence_var_container_,
597  &AssignmentProto::add_sequence_var_assignment);
598  if (HasObjective()) {
599  const IntVar* objective = Objective();
600  const std::string& name = objective->name();
601  if (!name.empty()) {
602  IntVarAssignment* objective = assignment_proto->mutable_objective();
603  objective->set_var_id(name);
604  const int64 obj_min = ObjectiveMin();
605  const int64 obj_max = ObjectiveMax();
606  objective->set_min(obj_min);
607  objective->set_max(obj_max);
608  objective->set_active(ActivatedObjective());
609  }
610  }
611 }
612 
613 template <class Container, class Element>
614 void RealDebugString(const Container& container, std::string* const out) {
615  for (const Element& element : container.elements()) {
616  if (element.Var() != nullptr) {
617  absl::StrAppendFormat(out, "%s %s | ", element.Var()->name(),
618  element.DebugString());
619  }
620  }
621 }
622 
623 std::string Assignment::DebugString() const {
624  std::string out = "Assignment(";
625  RealDebugString<IntContainer, IntVarElement>(int_var_container_, &out);
626  RealDebugString<IntervalContainer, IntervalVarElement>(
627  interval_var_container_, &out);
628  RealDebugString<SequenceContainer, SequenceVarElement>(
629  sequence_var_container_, &out);
630  if (HasObjective() && objective_element_.Activated()) {
631  out += objective_element_.DebugString();
632  }
633  out += ")";
634  return out;
635 }
636 
638  return int_var_container_.Add(var);
639 }
640 
641 void Assignment::Add(const std::vector<IntVar*>& vars) {
642  for (IntVar* const var : vars) {
643  Add(var);
644  }
645 }
646 
648  return int_var_container_.FastAdd(var);
649 }
650 
651 int64 Assignment::Min(const IntVar* const var) const {
652  return int_var_container_.Element(var).Min();
653 }
654 
655 int64 Assignment::Max(const IntVar* const var) const {
656  return int_var_container_.Element(var).Max();
657 }
658 
659 int64 Assignment::Value(const IntVar* const var) const {
660  return int_var_container_.Element(var).Value();
661 }
662 
663 bool Assignment::Bound(const IntVar* const var) const {
664  return int_var_container_.Element(var).Bound();
665 }
666 
667 void Assignment::SetMin(const IntVar* const var, int64 m) {
668  int_var_container_.MutableElement(var)->SetMin(m);
669 }
670 
671 void Assignment::SetMax(const IntVar* const var, int64 m) {
672  int_var_container_.MutableElement(var)->SetMax(m);
673 }
674 
675 void Assignment::SetRange(const IntVar* const var, int64 l, int64 u) {
676  int_var_container_.MutableElement(var)->SetRange(l, u);
677 }
678 
680  int_var_container_.MutableElement(var)->SetValue(value);
681 }
682 
683 // ----- Interval Var -----
684 
686  return interval_var_container_.Add(var);
687 }
688 
689 void Assignment::Add(const std::vector<IntervalVar*>& vars) {
690  for (IntervalVar* const var : vars) {
691  Add(var);
692  }
693 }
694 
696  return interval_var_container_.FastAdd(var);
697 }
698 
700  return interval_var_container_.Element(var).StartMin();
701 }
702 
704  return interval_var_container_.Element(var).StartMax();
705 }
706 
708  return interval_var_container_.Element(var).StartValue();
709 }
710 
712  return interval_var_container_.Element(var).DurationMin();
713 }
714 
716  return interval_var_container_.Element(var).DurationMax();
717 }
718 
720  return interval_var_container_.Element(var).DurationValue();
721 }
722 
724  return interval_var_container_.Element(var).EndMin();
725 }
726 
728  return interval_var_container_.Element(var).EndMax();
729 }
730 
732  return interval_var_container_.Element(var).EndValue();
733 }
734 
736  return interval_var_container_.Element(var).PerformedMin();
737 }
738 
740  return interval_var_container_.Element(var).PerformedMax();
741 }
742 
744  return interval_var_container_.Element(var).PerformedValue();
745 }
746 
748  interval_var_container_.MutableElement(var)->SetStartMin(m);
749 }
750 
752  interval_var_container_.MutableElement(var)->SetStartMax(m);
753 }
754 
756  int64 ma) {
757  interval_var_container_.MutableElement(var)->SetStartRange(mi, ma);
758 }
759 
761  interval_var_container_.MutableElement(var)->SetStartValue(value);
762 }
763 
765  interval_var_container_.MutableElement(var)->SetDurationMin(m);
766 }
767 
769  interval_var_container_.MutableElement(var)->SetDurationMax(m);
770 }
771 
773  int64 ma) {
774  interval_var_container_.MutableElement(var)->SetDurationRange(mi, ma);
775 }
776 
778  interval_var_container_.MutableElement(var)->SetDurationValue(value);
779 }
780 
782  interval_var_container_.MutableElement(var)->SetEndMin(m);
783 }
784 
786  interval_var_container_.MutableElement(var)->SetEndMax(m);
787 }
788 
789 void Assignment::SetEndRange(const IntervalVar* const var, int64 mi, int64 ma) {
790  interval_var_container_.MutableElement(var)->SetEndRange(mi, ma);
791 }
792 
794  interval_var_container_.MutableElement(var)->SetEndValue(value);
795 }
796 
798  interval_var_container_.MutableElement(var)->SetPerformedMin(m);
799 }
800 
802  interval_var_container_.MutableElement(var)->SetPerformedMax(m);
803 }
804 
806  int64 ma) {
807  interval_var_container_.MutableElement(var)->SetPerformedRange(mi, ma);
808 }
809 
811  interval_var_container_.MutableElement(var)->SetPerformedValue(value);
812 }
813 
814 // ----- Sequence Var -----
815 
817  return sequence_var_container_.Add(var);
818 }
819 
820 void Assignment::Add(const std::vector<SequenceVar*>& vars) {
821  for (SequenceVar* const var : vars) {
822  Add(var);
823  }
824 }
825 
827  return sequence_var_container_.FastAdd(var);
828 }
829 
830 const std::vector<int>& Assignment::ForwardSequence(
831  const SequenceVar* const var) const {
832  return sequence_var_container_.Element(var).ForwardSequence();
833 }
834 
835 const std::vector<int>& Assignment::BackwardSequence(
836  const SequenceVar* const var) const {
837  return sequence_var_container_.Element(var).BackwardSequence();
838 }
839 
840 const std::vector<int>& Assignment::Unperformed(
841  const SequenceVar* const var) const {
842  return sequence_var_container_.Element(var).Unperformed();
843 }
844 
846  const std::vector<int>& forward_sequence,
847  const std::vector<int>& backward_sequence,
848  const std::vector<int>& unperformed) {
849  sequence_var_container_.MutableElement(var)->SetSequence(
850  forward_sequence, backward_sequence, unperformed);
851 }
852 
854  const std::vector<int>& forward_sequence) {
855  sequence_var_container_.MutableElement(var)->SetForwardSequence(
856  forward_sequence);
857 }
858 
860  const SequenceVar* const var, const std::vector<int>& backward_sequence) {
861  sequence_var_container_.MutableElement(var)->SetBackwardSequence(
862  backward_sequence);
863 }
864 
866  const std::vector<int>& unperformed) {
867  sequence_var_container_.MutableElement(var)->SetUnperformed(unperformed);
868 }
869 
870 // ----- Objective -----
871 
873  // Check if adding twice an objective to the solution.
874  CHECK(!HasObjective());
875  objective_element_.Reset(v);
876 }
877 
878 IntVar* Assignment::Objective() const { return objective_element_.Var(); }
879 
881  if (HasObjective()) {
882  return objective_element_.Min();
883  }
884  return 0;
885 }
886 
888  if (HasObjective()) {
889  return objective_element_.Max();
890  }
891  return 0;
892 }
893 
895  if (HasObjective()) {
896  return objective_element_.Value();
897  }
898  return 0;
899 }
900 
902  if (HasObjective()) {
903  return objective_element_.Bound();
904  }
905  return true;
906 }
907 
909  if (HasObjective()) {
910  objective_element_.SetMin(m);
911  }
912 }
913 
915  if (HasObjective()) {
916  objective_element_.SetMax(m);
917  }
918 }
919 
921  if (HasObjective()) {
922  objective_element_.SetRange(l, u);
923  }
924 }
925 
927  if (HasObjective()) {
928  objective_element_.SetValue(value);
929  }
930 }
931 
932 void Assignment::Activate(const IntVar* const var) {
933  int_var_container_.MutableElement(var)->Activate();
934 }
935 
936 void Assignment::Deactivate(const IntVar* const var) {
937  int_var_container_.MutableElement(var)->Deactivate();
938 }
939 
940 bool Assignment::Activated(const IntVar* const var) const {
941  return int_var_container_.Element(var).Activated();
942 }
943 
945  interval_var_container_.MutableElement(var)->Activate();
946 }
947 
949  interval_var_container_.MutableElement(var)->Deactivate();
950 }
951 
952 bool Assignment::Activated(const IntervalVar* const var) const {
953  return interval_var_container_.Element(var).Activated();
954 }
955 
957  sequence_var_container_.MutableElement(var)->Activate();
958 }
959 
961  sequence_var_container_.MutableElement(var)->Deactivate();
962 }
963 
964 bool Assignment::Activated(const SequenceVar* const var) const {
965  return sequence_var_container_.Element(var).Activated();
966 }
967 
969  if (HasObjective()) {
970  objective_element_.Activate();
971  }
972 }
973 
975  if (HasObjective()) {
976  objective_element_.Deactivate();
977  }
978 }
979 
981  if (HasObjective()) {
982  return objective_element_.Activated();
983  }
984  return true;
985 }
986 
987 bool Assignment::Contains(const IntVar* const var) const {
988  return int_var_container_.Contains(var);
989 }
990 
991 bool Assignment::Contains(const IntervalVar* const var) const {
992  return interval_var_container_.Contains(var);
993 }
994 
995 bool Assignment::Contains(const SequenceVar* const var) const {
996  return sequence_var_container_.Contains(var);
997 }
998 
999 void Assignment::CopyIntersection(const Assignment* assignment) {
1000  int_var_container_.CopyIntersection(assignment->int_var_container_);
1001  interval_var_container_.CopyIntersection(assignment->interval_var_container_);
1002  sequence_var_container_.CopyIntersection(assignment->sequence_var_container_);
1003  if (objective_element_.Var() == assignment->objective_element_.Var()) {
1004  objective_element_ = assignment->objective_element_;
1005  }
1006 }
1007 
1008 void Assignment::Copy(const Assignment* assignment) {
1009  Clear();
1010  int_var_container_.Copy(assignment->int_var_container_);
1011  interval_var_container_.Copy(assignment->interval_var_container_);
1012  sequence_var_container_.Copy(assignment->sequence_var_container_);
1013  objective_element_ = assignment->objective_element_;
1014 }
1015 
1016 void SetAssignmentFromAssignment(Assignment* target_assignment,
1017  const std::vector<IntVar*>& target_vars,
1018  const Assignment* source_assignment,
1019  const std::vector<IntVar*>& source_vars) {
1020  const int vars_size = target_vars.size();
1021  CHECK_EQ(source_vars.size(), vars_size);
1022  CHECK(target_assignment != nullptr);
1023 
1024  target_assignment->Clear();
1025  const Solver* const target_solver = target_assignment->solver();
1026  const Solver* const source_solver = source_assignment->solver();
1027  for (int index = 0; index < vars_size; index++) {
1028  IntVar* target_var = target_vars[index];
1029  CHECK_EQ(target_var->solver(), target_solver);
1030  IntVar* source_var = source_vars[index];
1031  CHECK_EQ(source_var->solver(), source_solver);
1032  target_assignment->Add(target_var)
1033  ->SetValue(source_assignment->Value(source_var));
1034  }
1035 }
1036 
1038 
1040  return RevAlloc(new Assignment(a));
1041 }
1042 
1043 // ----- Storing and Restoring assignments -----
1044 namespace {
1045 class RestoreAssignment : public DecisionBuilder {
1046  public:
1047  explicit RestoreAssignment(Assignment* assignment)
1048  : assignment_(assignment) {}
1049 
1050  ~RestoreAssignment() override {}
1051 
1052  Decision* Next(Solver* const solver) override {
1053  assignment_->Restore();
1054  return nullptr;
1055  }
1056 
1057  std::string DebugString() const override { return "RestoreAssignment"; }
1058 
1059  private:
1060  Assignment* const assignment_;
1061 };
1062 
1063 class StoreAssignment : public DecisionBuilder {
1064  public:
1065  explicit StoreAssignment(Assignment* assignment) : assignment_(assignment) {}
1066 
1067  ~StoreAssignment() override {}
1068 
1069  Decision* Next(Solver* const solver) override {
1070  assignment_->Store();
1071  return nullptr;
1072  }
1073 
1074  std::string DebugString() const override { return "StoreAssignment"; }
1075 
1076  private:
1077  Assignment* const assignment_;
1078 };
1079 } // namespace
1080 
1082  return RevAlloc(new RestoreAssignment(assignment));
1083 }
1084 
1086  return RevAlloc(new StoreAssignment(assignment));
1087 }
1088 
1089 std::ostream& operator<<(std::ostream& out, const Assignment& assignment) {
1090  return out << assignment.DebugString();
1091 }
1092 
1093 } // namespace operations_research
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
Definition: base/file.h:32
bool Contains(const V *const var) const
void Copy(const AssignmentContainer< V, E > &container)
Copies all the elements of 'container' to this container, clearing its previous content.
const E & Element(const V *const var) const
void CopyIntersection(const AssignmentContainer< V, E > &container)
Copies the elements of 'container' which are already in the calling container.
E * FastAdd(V *var)
Adds element without checking its presence in the container.
An Assignment is a variable -> domains mapping, used to report solutions to the user.
const std::vector< int > & Unperformed(const SequenceVar *const var) const
int64 DurationMin(const IntervalVar *const var) const
void SetForwardSequence(const SequenceVar *const var, const std::vector< int > &forward_sequence)
int64 Value(const IntVar *const var) const
void Deactivate(const IntVar *const var)
void SetStartMin(const IntervalVar *const var, int64 m)
void SetBackwardSequence(const SequenceVar *const var, const std::vector< int > &backward_sequence)
const std::vector< int > & BackwardSequence(const SequenceVar *const var) const
void SetDurationValue(const IntervalVar *const var, int64 value)
void SetEndMax(const IntervalVar *const var, int64 m)
int64 EndMax(const IntervalVar *const var) const
int64 StartValue(const IntervalVar *const var) const
void SetStartMax(const IntervalVar *const var, int64 m)
void SetPerformedValue(const IntervalVar *const var, int64 value)
int64 PerformedMin(const IntervalVar *const var) const
bool Load(const std::string &filename)
Loads an assignment from a file; does not add variables to the assignment (only the variables contain...
int64 Min(const IntVar *const var) const
bool Contains(const IntVar *const var) const
bool Activated(const IntVar *const var) const
bool Save(const std::string &filename) const
Saves the assignment to a file.
int64 EndMin(const IntervalVar *const var) const
void SetMax(const IntVar *const var, int64 m)
void SetPerformedRange(const IntervalVar *const var, int64 mi, int64 ma)
void SetEndMin(const IntervalVar *const var, int64 m)
const std::vector< int > & ForwardSequence(const SequenceVar *const var) const
int64 StartMin(const IntervalVar *const var) const
void SetPerformedMin(const IntervalVar *const var, int64 m)
void SetMin(const IntVar *const var, int64 m)
void SetPerformedMax(const IntervalVar *const var, int64 m)
int64 Max(const IntVar *const var) const
void SetEndValue(const IntervalVar *const var, int64 value)
void SetUnperformed(const SequenceVar *const var, const std::vector< int > &unperformed)
int64 DurationMax(const IntervalVar *const var) const
void SetStartValue(const IntervalVar *const var, int64 value)
void CopyIntersection(const Assignment *assignment)
Copies the intersection of the two assignments to the current assignment.
void SetDurationMax(const IntervalVar *const var, int64 m)
void SetStartRange(const IntervalVar *const var, int64 mi, int64 ma)
void SetValue(const IntVar *const var, int64 value)
void Copy(const Assignment *assignment)
Copies 'assignment' to the current assignment, clearing its previous content.
int64 PerformedMax(const IntervalVar *const var) const
void SetSequence(const SequenceVar *const var, const std::vector< int > &forward_sequence, const std::vector< int > &backward_sequence, const std::vector< int > &unperformed)
int64 DurationValue(const IntervalVar *const var) const
void SetDurationMin(const IntervalVar *const var, int64 m)
int64 StartMax(const IntervalVar *const var) const
int64 EndValue(const IntervalVar *const var) const
int64 PerformedValue(const IntervalVar *const var) const
IntVarElement * Add(IntVar *const var)
void SetEndRange(const IntervalVar *const var, int64 mi, int64 ma)
void SetDurationRange(const IntervalVar *const var, int64 mi, int64 ma)
bool Bound(const IntVar *const var) const
IntVarElement * FastAdd(IntVar *const var)
Adds without checking if variable has been previously added.
void SetRange(const IntVar *const var, int64 l, int64 u)
A DecisionBuilder is responsible for creating the search tree.
void Copy(const IntVarElement &element)
bool operator==(const IntVarElement &element) const
void WriteToProto(IntVarAssignment *int_var_assignment_proto) const
void LoadFromProto(const IntVarAssignment &int_var_assignment_proto)
The class IntVar is a subset of IntExpr.
IntVar * Var() override
Creates a variable from the expression.
void LoadFromProto(const IntervalVarAssignment &interval_var_assignment_proto)
bool operator==(const IntervalVarElement &element) const
void Copy(const IntervalVarElement &element)
void WriteToProto(IntervalVarAssignment *interval_var_assignment_proto) const
Interval variables are often used in scheduling.
virtual int64 StartMax() const =0
virtual int64 DurationMax() const =0
virtual void SetPerformed(bool val)=0
virtual int64 EndMax() const =0
virtual void SetEndRange(int64 mi, int64 ma)=0
virtual bool MustBePerformed() const =0
These methods query, set, and watch the performed status of the interval var.
virtual int64 StartMin() const =0
These methods query, set, and watch the start position of the interval var.
virtual void SetStartRange(int64 mi, int64 ma)=0
virtual int64 EndMin() const =0
These methods query, set, and watch the end position of the interval var.
virtual int64 DurationMin() const =0
These methods query, set, and watch the duration of the interval var.
virtual void SetDurationRange(int64 mi, int64 ma)=0
virtual bool MayBePerformed() const =0
virtual std::string name() const
Object naming.
void FreezeQueue()
This method freezes the propagation queue.
void UnfreezeQueue()
This method unfreezes the propagation queue.
The SequenceVarElement stores a partial representation of ranked interval variables in the underlying...
void SetSequence(const std::vector< int > &forward_sequence, const std::vector< int > &backward_sequence, const std::vector< int > &unperformed)
bool operator==(const SequenceVarElement &element) const
const std::vector< int > & BackwardSequence() const
void SetBackwardSequence(const std::vector< int > &backward_sequence)
const std::vector< int > & Unperformed() const
void SetUnperformed(const std::vector< int > &unperformed)
const std::vector< int > & ForwardSequence() const
void Copy(const SequenceVarElement &element)
void LoadFromProto(const SequenceVarAssignment &sequence_var_assignment_proto)
void WriteToProto(SequenceVarAssignment *sequence_var_assignment_proto) const
void SetForwardSequence(const std::vector< int > &forward_sequence)
A sequence variable is a variable whose domain is a set of possible orderings of the interval variabl...
void FillSequence(std::vector< int > *const rank_first, std::vector< int > *const rank_last, std::vector< int > *const unperformed) const
Clears 'rank_first' and 'rank_last', and fills them with the intervals in the order of the ranks.
void RankSequence(const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)
Applies the following sequence of ranks, ranks first, then rank last.
T * RevAlloc(T *object)
Registers the given object as being reversible.
Assignment * MakeAssignment()
This method creates an empty assignment.
DecisionBuilder * MakeStoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which stores an Assignment (calls void Assignment::Store())
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which restores an Assignment (calls void Assignment::Restore())
bool ReadProtocolMessage(P *const proto)
Definition: recordio.h:91
bool WriteProtocolMessage(const P &proto)
Definition: recordio.h:41
CpModelProto proto
const std::string name
int64 value
IntVar * var
Definition: expr_array.cc:1858
int int32
static const int64 kint64max
int64_t int64
static const int64 kint64min
const int INFO
Definition: log_severity.h:31
Definition: file.cc:141
int Defaults()
Definition: base/file.h:119
absl::Status Open(const absl::string_view &filename, const absl::string_view &mode, File **f, int flags)
Definition: file.cc:142
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
Definition: map_util.h:155
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
void StoreAssignment(const VariablesAssignment &assignment, BooleanAssignment *output)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
void RealLoad(const AssignmentProto &assignment_proto, Container *const container, int(AssignmentProto::*GetSize)() const, const Proto &(AssignmentProto::*GetElem)(int) const)
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
void SetAssignmentFromAssignment(Assignment *target_assignment, const std::vector< IntVar * > &target_vars, const Assignment *source_assignment, const std::vector< IntVar * > &source_vars)
NOLINT.
void RealDebugString(const Container &container, std::string *const out)
void RealSave(AssignmentProto *const assignment_proto, const Container &container, Proto *(AssignmentProto::*Add)())
int index
Definition: pack.cc:508