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"
28#include "ortools/constraint_solver/assignment.pb.h"
30
31namespace 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
53void 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
74bool 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
97std::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
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
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
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
346const std::vector<int>& SequenceVarElement::ForwardSequence() const {
347 return forward_sequence_;
348}
349
350const std::vector<int>& SequenceVarElement::BackwardSequence() const {
351 return backward_sequence_;
352}
353
354const std::vector<int>& SequenceVarElement::Unperformed() const {
355 return unperformed_;
356}
357
358void 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
377void SequenceVarElement::SetUnperformed(const std::vector<int>& unperformed) {
378 unperformed_ = unperformed;
379}
380
381bool 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();
440}
441
442namespace {
443
444template <class V, class E>
445void 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
465template <class E, class P>
466void 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
481bool 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
502template <class Var, class Element, class Proto, class Container>
503void 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
527void 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
557bool 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
567 CHECK(file != nullptr);
568 AssignmentProto assignment_proto;
569 Save(&assignment_proto);
571 return writer.WriteProtocolMessage(assignment_proto) && writer.Close();
572}
573
574template <class Var, class Element, class Proto, class Container>
575void 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
587void 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
613template <class Container, class Element>
614void 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
623std::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
641void 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
651int64 Assignment::Min(const IntVar* const var) const {
652 return int_var_container_.Element(var).Min();
653}
654
655int64 Assignment::Max(const IntVar* const var) const {
656 return int_var_container_.Element(var).Max();
657}
658
659int64 Assignment::Value(const IntVar* const var) const {
660 return int_var_container_.Element(var).Value();
661}
662
663bool Assignment::Bound(const IntVar* const var) const {
664 return int_var_container_.Element(var).Bound();
665}
666
667void Assignment::SetMin(const IntVar* const var, int64 m) {
668 int_var_container_.MutableElement(var)->SetMin(m);
669}
670
671void Assignment::SetMax(const IntVar* const var, int64 m) {
672 int_var_container_.MutableElement(var)->SetMax(m);
673}
674
675void 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
689void 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
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
820void 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
830const std::vector<int>& Assignment::ForwardSequence(
831 const SequenceVar* const var) const {
832 return sequence_var_container_.Element(var).ForwardSequence();
833}
834
835const std::vector<int>& Assignment::BackwardSequence(
836 const SequenceVar* const var) const {
837 return sequence_var_container_.Element(var).BackwardSequence();
838}
839
840const 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.
875 objective_element_.Reset(v);
876}
877
878IntVar* 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
932void Assignment::Activate(const IntVar* const var) {
933 int_var_container_.MutableElement(var)->Activate();
934}
935
937 int_var_container_.MutableElement(var)->Deactivate();
938}
939
940bool 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
952bool 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
964bool 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
987bool Assignment::Contains(const IntVar* const var) const {
988 return int_var_container_.Contains(var);
989}
990
991bool Assignment::Contains(const IntervalVar* const var) const {
992 return interval_var_container_.Contains(var);
993}
994
995bool Assignment::Contains(const SequenceVar* const var) const {
996 return sequence_var_container_.Contains(var);
997}
998
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
1008void 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
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 -----
1044namespace {
1045class 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
1063class 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
1089std::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
const E & Element(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.
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.
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())
T * RevAlloc(T *object)
Registers the given object as being reversible.
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
absl::Status Open(const absl::string_view &filename, const absl::string_view &mode, File **f, int flags)
Definition: file.cc:142
int Defaults()
Definition: base/file.h:119
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
Definition: map_util.h:155
void StoreAssignment(const VariablesAssignment &assignment, BooleanAssignment *output)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
void RealSave(AssignmentProto *const assignment_proto, const Container &container, Proto *(AssignmentProto::*Add)())
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 RealLoad(const AssignmentProto &assignment_proto, Container *const container, int(AssignmentProto::*GetSize)() const, const Proto &(AssignmentProto::*GetElem)(int) const)
int index
Definition: pack.cc:508