1 // Copyright 2010-2021 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 <cstdint>
17 #include <limits>
18 #include <string>
19 #include <vector>
20
21 #include "absl/container/flat_hash_map.h"
22 #include "absl/strings/str_format.h"
23 #include "absl/strings/str_join.h"
24 #include "ortools/base/file.h"
25 #include "ortools/base/hash.h"
26 #include "ortools/base/integral_types.h"
27 #include "ortools/base/logging.h"
28 #include "ortools/base/map_util.h"
29 #include "ortools/base/recordio.h"
30 #include "ortools/constraint_solver/assignment.pb.h"
31 #include "ortools/constraint_solver/constraint_solver.h"
32
33 namespace operations_research {
34
35 // ----------------- Solutions ------------------------
36
37 // ----- IntVarElement -----
38
IntVarElement()39 IntVarElement::IntVarElement() { Reset(nullptr); }
40
IntVarElement(IntVar * const var)41 IntVarElement::IntVarElement(IntVar* const var) { Reset(var); }
42
Reset(IntVar * const var)43 void IntVarElement::Reset(IntVar* const var) {
44 var_ = var;
45 min_ = std::numeric_limits<int64_t>::min();
46 max_ = std::numeric_limits<int64_t>::max();
47 }
48
Clone()49 IntVarElement* IntVarElement::Clone() {
50 IntVarElement* element = new IntVarElement;
51 element->Copy(*this);
52 return element;
53 }
54
Copy(const IntVarElement & element)55 void IntVarElement::Copy(const IntVarElement& element) {
56 SetRange(element.min_, element.max_);
57 var_ = element.var_;
58 if (element.Activated()) {
59 Activate();
60 } else {
61 Deactivate();
62 }
63 }
64
LoadFromProto(const IntVarAssignment & int_var_assignment_proto)65 void IntVarElement::LoadFromProto(
66 const IntVarAssignment& int_var_assignment_proto) {
67 min_ = int_var_assignment_proto.min();
68 max_ = int_var_assignment_proto.max();
69 if (int_var_assignment_proto.active()) {
70 Activate();
71 } else {
72 Deactivate();
73 }
74 }
75
operator ==(const IntVarElement & element) const76 bool IntVarElement::operator==(const IntVarElement& element) const {
77 if (var_ != element.var_) {
78 return false;
79 }
80 if (Activated() != element.Activated()) {
81 return false;
82 }
83 if (!Activated() && !element.Activated()) {
84 // If both elements are deactivated, then they are equal, regardless of
85 // their min and max.
86 return true;
87 }
88 return min_ == element.min_ && max_ == element.max_;
89 }
90
WriteToProto(IntVarAssignment * int_var_assignment_proto) const91 void IntVarElement::WriteToProto(
92 IntVarAssignment* int_var_assignment_proto) const {
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_);
96 int_var_assignment_proto->set_active(Activated());
97 }
98
DebugString() const99 std::string IntVarElement::DebugString() const {
100 if (Activated()) {
101 if (min_ == max_) {
102 return absl::StrFormat("(%d)", min_);
103 } else {
104 return absl::StrFormat("(%d..%d)", min_, max_);
105 }
106 } else {
107 return "(...)";
108 }
109 }
110
111 // ----- IntervalVarElement -----
112
IntervalVarElement()113 IntervalVarElement::IntervalVarElement() { Reset(nullptr); }
114
IntervalVarElement(IntervalVar * const var)115 IntervalVarElement::IntervalVarElement(IntervalVar* const var) { Reset(var); }
116
Reset(IntervalVar * const var)117 void IntervalVarElement::Reset(IntervalVar* const var) {
118 var_ = var;
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();
124 end_max_ = std::numeric_limits<int64_t>::max();
125 performed_min_ = 0;
126 performed_max_ = 1;
127 }
128
Clone()129 IntervalVarElement* IntervalVarElement::Clone() {
130 IntervalVarElement* element = new IntervalVarElement;
131 element->Copy(*this);
132 return element;
133 }
134
Copy(const IntervalVarElement & element)135 void IntervalVarElement::Copy(const IntervalVarElement& element) {
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_);
140 var_ = element.var_;
141 if (element.Activated()) {
142 Activate();
143 } else {
144 Deactivate();
145 }
146 }
147
Store()148 void IntervalVarElement::Store() {
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();
157 end_max_ = var_->EndMax();
158 }
159 }
160
Restore()161 void IntervalVarElement::Restore() {
162 if (performed_max_ == performed_min_) {
163 var_->SetPerformed(performed_min_);
164 }
165 if (performed_max_ != 0LL) {
166 var_->SetStartRange(start_min_, start_max_);
167 var_->SetDurationRange(duration_min_, duration_max_);
168 var_->SetEndRange(end_min_, end_max_);
169 }
170 }
171
LoadFromProto(const IntervalVarAssignment & interval_var_assignment_proto)172 void IntervalVarElement::LoadFromProto(
173 const IntervalVarAssignment& interval_var_assignment_proto) {
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()) {
183 Activate();
184 } else {
185 Deactivate();
186 }
187 }
188
WriteToProto(IntervalVarAssignment * interval_var_assignment_proto) const189 void IntervalVarElement::WriteToProto(
190 IntervalVarAssignment* interval_var_assignment_proto) const {
191 interval_var_assignment_proto->set_var_id(var_->name());
192 interval_var_assignment_proto->set_start_min(start_min_);
193 interval_var_assignment_proto->set_start_max(start_max_);
194 interval_var_assignment_proto->set_duration_min(duration_min_);
195 interval_var_assignment_proto->set_duration_max(duration_max_);
196 interval_var_assignment_proto->set_end_min(end_min_);
197 interval_var_assignment_proto->set_end_max(end_max_);
198 interval_var_assignment_proto->set_performed_min(performed_min_);
199 interval_var_assignment_proto->set_performed_max(performed_max_);
200 interval_var_assignment_proto->set_active(Activated());
201 }
202
DebugString() const203 std::string IntervalVarElement::DebugString() const {
204 if (Activated()) {
205 std::string out;
206 absl::StrAppendFormat(&out, "(start = %d", start_min_);
207 if (start_max_ != start_min_) {
208 absl::StrAppendFormat(&out, "..%d", start_max_);
209 }
210 absl::StrAppendFormat(&out, ", duration = %d", duration_min_);
211 if (duration_max_ != duration_min_) {
212 absl::StrAppendFormat(&out, "..%d", duration_max_);
213 }
214 absl::StrAppendFormat(&out, ", status = %d", performed_min_);
215 if (performed_max_ != performed_min_) {
216 absl::StrAppendFormat(&out, "..%d", performed_max_);
217 }
218 out.append(")");
219 return out;
220 } else {
221 return "(...)";
222 }
223 }
224
operator ==(const IntervalVarElement & element) const225 bool IntervalVarElement::operator==(const IntervalVarElement& element) const {
226 if (var_ != element.var_) {
227 return false;
228 }
229 if (Activated() != element.Activated()) {
230 return false;
231 }
232 if (!Activated() && !element.Activated()) {
233 // If both elements are deactivated, then they are equal, regardless of
234 // their other fields.
235 return true;
236 }
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_;
243 }
244
245 // ----- SequenceVarElement -----
246
SequenceVarElement()247 SequenceVarElement::SequenceVarElement() { Reset(nullptr); }
248
SequenceVarElement(SequenceVar * const var)249 SequenceVarElement::SequenceVarElement(SequenceVar* const var) { Reset(var); }
250
Reset(SequenceVar * const var)251 void SequenceVarElement::Reset(SequenceVar* const var) {
252 var_ = var;
253 forward_sequence_.clear();
254 backward_sequence_.clear();
255 unperformed_.clear();
256 }
257
Clone()258 SequenceVarElement* SequenceVarElement::Clone() {
259 SequenceVarElement* const element = new SequenceVarElement;
260 element->Copy(*this);
261 return element;
262 }
263
Copy(const SequenceVarElement & element)264 void SequenceVarElement::Copy(const SequenceVarElement& element) {
265 forward_sequence_ = element.forward_sequence_;
266 backward_sequence_ = element.backward_sequence_;
267 unperformed_ = element.unperformed_;
268 var_ = element.var_;
269 if (element.Activated()) {
270 Activate();
271 } else {
272 Deactivate();
273 }
274 }
275
Store()276 void SequenceVarElement::Store() {
277 var_->FillSequence(&forward_sequence_, &backward_sequence_, &unperformed_);
278 }
279
Restore()280 void SequenceVarElement::Restore() {
281 var_->RankSequence(forward_sequence_, backward_sequence_, unperformed_);
282 }
283
LoadFromProto(const SequenceVarAssignment & sequence_var_assignment_proto)284 void SequenceVarElement::LoadFromProto(
285 const SequenceVarAssignment& sequence_var_assignment_proto) {
286 for (const int32_t forward_sequence :
287 sequence_var_assignment_proto.forward_sequence()) {
288 forward_sequence_.push_back(forward_sequence);
289 }
290 for (const int32_t backward_sequence :
291 sequence_var_assignment_proto.backward_sequence()) {
292 backward_sequence_.push_back(backward_sequence);
293 }
294 for (const int32_t unperformed :
295 sequence_var_assignment_proto.unperformed()) {
296 unperformed_.push_back(unperformed);
297 }
298 if (sequence_var_assignment_proto.active()) {
299 Activate();
300 } else {
301 Deactivate();
302 }
303 DCHECK(CheckClassInvariants());
304 }
305
WriteToProto(SequenceVarAssignment * sequence_var_assignment_proto) const306 void SequenceVarElement::WriteToProto(
307 SequenceVarAssignment* sequence_var_assignment_proto) const {
308 sequence_var_assignment_proto->set_var_id(var_->name());
309 sequence_var_assignment_proto->set_active(Activated());
310 for (const int forward_sequence : forward_sequence_) {
311 sequence_var_assignment_proto->add_forward_sequence(forward_sequence);
312 }
313 for (const int backward_sequence : backward_sequence_) {
314 sequence_var_assignment_proto->add_backward_sequence(backward_sequence);
315 }
316 for (const int unperformed : unperformed_) {
317 sequence_var_assignment_proto->add_unperformed(unperformed);
318 }
319 }
320
DebugString() const321 std::string SequenceVarElement::DebugString() const {
322 if (Activated()) {
323 return absl::StrFormat("[forward %s, backward %s, unperformed [%s]]",
324 absl::StrJoin(forward_sequence_, " -> "),
325 absl::StrJoin(backward_sequence_, " -> "),
326 absl::StrJoin(unperformed_, ", "));
327 } else {
328 return "(...)";
329 }
330 }
331
operator ==(const SequenceVarElement & element) const332 bool SequenceVarElement::operator==(const SequenceVarElement& element) const {
333 if (var_ != element.var_) {
334 return false;
335 }
336 if (Activated() != element.Activated()) {
337 return false;
338 }
339 if (!Activated() && !element.Activated()) {
340 // If both elements are deactivated, then they are equal, regardless of
341 // their other fields.
342 return true;
343 }
344 return forward_sequence_ == element.forward_sequence_ &&
345 backward_sequence_ == element.backward_sequence_ &&
346 unperformed_ == element.unperformed_;
347 }
348
ForwardSequence() const349 const std::vector<int>& SequenceVarElement::ForwardSequence() const {
350 return forward_sequence_;
351 }
352
BackwardSequence() const353 const std::vector<int>& SequenceVarElement::BackwardSequence() const {
354 return backward_sequence_;
355 }
356
Unperformed() const357 const std::vector<int>& SequenceVarElement::Unperformed() const {
358 return unperformed_;
359 }
360
SetSequence(const std::vector<int> & forward_sequence,const std::vector<int> & backward_sequence,const std::vector<int> & unperformed)361 void SequenceVarElement::SetSequence(const std::vector<int>& forward_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;
367 DCHECK(CheckClassInvariants());
368 }
369
SetForwardSequence(const std::vector<int> & forward_sequence)370 void SequenceVarElement::SetForwardSequence(
371 const std::vector<int>& forward_sequence) {
372 forward_sequence_ = forward_sequence;
373 }
374
SetBackwardSequence(const std::vector<int> & backward_sequence)375 void SequenceVarElement::SetBackwardSequence(
376 const std::vector<int>& backward_sequence) {
377 backward_sequence_ = backward_sequence;
378 }
379
SetUnperformed(const std::vector<int> & unperformed)380 void SequenceVarElement::SetUnperformed(const std::vector<int>& unperformed) {
381 unperformed_ = unperformed;
382 }
383
CheckClassInvariants()384 bool SequenceVarElement::CheckClassInvariants() {
385 absl::flat_hash_set<int> visited;
386 for (const int forward_sequence : forward_sequence_) {
387 if (gtl::ContainsKey(visited, forward_sequence)) {
388 return false;
389 }
390 visited.insert(forward_sequence);
391 }
392 for (const int backward_sequence : backward_sequence_) {
393 if (gtl::ContainsKey(visited, backward_sequence)) {
394 return false;
395 }
396 visited.insert(backward_sequence);
397 }
398 for (const int unperformed : unperformed_) {
399 if (gtl::ContainsKey(visited, unperformed)) {
400 return false;
401 }
402 visited.insert(unperformed);
403 }
404 return true;
405 }
406
407 // ----- Assignment -----
408
Assignment(const Assignment * const copy)409 Assignment::Assignment(const Assignment* const copy)
410 : PropagationBaseObject(copy->solver()),
411 int_var_container_(copy->int_var_container_),
412 interval_var_container_(copy->interval_var_container_),
413 sequence_var_container_(copy->sequence_var_container_),
414 objective_element_(copy->objective_element_) {}
415
Assignment(Solver * const s)416 Assignment::Assignment(Solver* const s)
417 : PropagationBaseObject(s), objective_element_(nullptr) {}
418
~Assignment()419 Assignment::~Assignment() {}
420
Clear()421 void Assignment::Clear() {
422 objective_element_.Reset(nullptr);
423 int_var_container_.Clear();
424 interval_var_container_.Clear();
425 sequence_var_container_.Clear();
426 }
427
Store()428 void Assignment::Store() {
429 int_var_container_.Store();
430 interval_var_container_.Store();
431 sequence_var_container_.Store();
432 if (HasObjective()) {
433 objective_element_.Store();
434 }
435 }
436
Restore()437 void Assignment::Restore() {
438 FreezeQueue();
439 int_var_container_.Restore();
440 interval_var_container_.Restore();
441 sequence_var_container_.Restore();
442 UnfreezeQueue();
443 }
444
445 namespace {
446
447 template <class V, class E>
IdToElementMap(AssignmentContainer<V,E> * container,absl::flat_hash_map<std::string,E * > * id_to_element_map)448 void IdToElementMap(AssignmentContainer<V, E>* container,
449 absl::flat_hash_map<std::string, E*>* id_to_element_map) {
450 CHECK(id_to_element_map != nullptr);
451 id_to_element_map->clear();
452 for (int i = 0; i < container->Size(); ++i) {
453 E* const element = container->MutableElement(i);
454 const V* const var = element->Var();
455 const std::string& name = var->name();
456 if (name.empty()) {
457 LOG(INFO) << "Cannot save/load variables with empty name"
458 << "; variable will be ignored";
459 } else if (gtl::ContainsKey(*id_to_element_map, name)) {
460 LOG(INFO) << "Cannot save/load variables with duplicate names: " << name
461 << "; variable will be ignored";
462 } else {
463 (*id_to_element_map)[name] = element;
464 }
465 }
466 }
467
468 template <class E, class P>
LoadElement(const absl::flat_hash_map<std::string,E * > & id_to_element_map,const P & proto)469 void LoadElement(const absl::flat_hash_map<std::string, E*>& id_to_element_map,
470 const P& proto) {
471 const std::string& var_id = proto.var_id();
472 CHECK(!var_id.empty());
473 E* element = nullptr;
474 if (gtl::FindCopy(id_to_element_map, var_id, &element)) {
475 element->LoadFromProto(proto);
476 } else {
477 LOG(INFO) << "Variable " << var_id
478 << " not in assignment; skipping variable";
479 }
480 }
481
482 } // namespace
483
Load(const std::string & filename)484 bool Assignment::Load(const std::string& filename) {
485 File* file;
486 if (!file::Open(filename, "r", &file, file::Defaults()).ok()) {
487 LOG(INFO) << "Cannot open " << filename;
488 return false;
489 }
490 return Load(file);
491 }
492
Load(File * file)493 bool Assignment::Load(File* file) {
494 CHECK(file != nullptr);
495 AssignmentProto assignment_proto;
496 recordio::RecordReader reader(file);
497 if (!reader.ReadProtocolMessage(&assignment_proto)) {
498 LOG(INFO) << "No assignment found in " << file->filename();
499 return false;
500 }
501 Load(assignment_proto);
502 return reader.Close();
503 }
504
505 template <class Var, class Element, class Proto, class Container>
RealLoad(const AssignmentProto & assignment_proto,Container * const container,int (AssignmentProto::* GetSize)()const,const Proto & (AssignmentProto::* GetElem)(int)const)506 void RealLoad(const AssignmentProto& assignment_proto,
507 Container* const container,
508 int (AssignmentProto::*GetSize)() const,
509 const Proto& (AssignmentProto::*GetElem)(int) const) {
510 bool fast_load = (container->Size() == (assignment_proto.*GetSize)());
511 for (int i = 0; fast_load && i < (assignment_proto.*GetSize)(); ++i) {
512 Element* const element = container->MutableElement(i);
513 const Proto& proto = (assignment_proto.*GetElem)(i);
514 if (element->Var()->name() == proto.var_id()) {
515 element->LoadFromProto(proto);
516 } else {
517 fast_load = false;
518 }
519 }
520 if (!fast_load) {
521 absl::flat_hash_map<std::string, Element*> id_to_element_map;
522 IdToElementMap<Var, Element>(container, &id_to_element_map);
523 for (int i = 0; i < (assignment_proto.*GetSize)(); ++i) {
524 LoadElement<Element, Proto>(id_to_element_map,
525 (assignment_proto.*GetElem)(i));
526 }
527 }
528 }
529
Load(const AssignmentProto & assignment_proto)530 void Assignment::Load(const AssignmentProto& assignment_proto) {
531 RealLoad<IntVar, IntVarElement, IntVarAssignment, IntContainer>(
532 assignment_proto, &int_var_container_,
533 &AssignmentProto::int_var_assignment_size,
534 &AssignmentProto::int_var_assignment);
535 RealLoad<IntervalVar, IntervalVarElement, IntervalVarAssignment,
536 IntervalContainer>(assignment_proto, &interval_var_container_,
537 &AssignmentProto::interval_var_assignment_size,
538 &AssignmentProto::interval_var_assignment);
539 RealLoad<SequenceVar, SequenceVarElement, SequenceVarAssignment,
540 SequenceContainer>(assignment_proto, &sequence_var_container_,
541 &AssignmentProto::sequence_var_assignment_size,
542 &AssignmentProto::sequence_var_assignment);
543 if (assignment_proto.has_objective()) {
544 const IntVarAssignment& objective = assignment_proto.objective();
545 const std::string& objective_id = objective.var_id();
546 CHECK(!objective_id.empty());
547 if (HasObjective() && objective_id == Objective()->name()) {
548 const int64_t obj_min = objective.min();
549 const int64_t obj_max = objective.max();
550 SetObjectiveRange(obj_min, obj_max);
551 if (objective.active()) {
552 ActivateObjective();
553 } else {
554 DeactivateObjective();
555 }
556 }
557 }
558 }
559
Save(const std::string & filename) const560 bool Assignment::Save(const std::string& filename) const {
561 File* file;
562 if (!file::Open(filename, "w", &file, file::Defaults()).ok()) {
563 LOG(INFO) << "Cannot open " << filename;
564 return false;
565 }
566 return Save(file);
567 }
568
Save(File * file) const569 bool Assignment::Save(File* file) const {
570 CHECK(file != nullptr);
571 AssignmentProto assignment_proto;
572 Save(&assignment_proto);
573 recordio::RecordWriter writer(file);
574 return writer.WriteProtocolMessage(assignment_proto) && writer.Close();
575 }
576
577 template <class Var, class Element, class Proto, class Container>
RealSave(AssignmentProto * const assignment_proto,const Container & container,Proto * (AssignmentProto::* Add)())578 void RealSave(AssignmentProto* const assignment_proto,
579 const Container& container, Proto* (AssignmentProto::*Add)()) {
580 for (const Element& element : container.elements()) {
581 const Var* const var = element.Var();
582 const std::string& name = var->name();
583 if (!name.empty()) {
584 Proto* const var_assignment_proto = (assignment_proto->*Add)();
585 element.WriteToProto(var_assignment_proto);
586 }
587 }
588 }
589
Save(AssignmentProto * const assignment_proto) const590 void Assignment::Save(AssignmentProto* const assignment_proto) const {
591 assignment_proto->Clear();
592 RealSave<IntVar, IntVarElement, IntVarAssignment, IntContainer>(
593 assignment_proto, int_var_container_,
594 &AssignmentProto::add_int_var_assignment);
595 RealSave<IntervalVar, IntervalVarElement, IntervalVarAssignment,
596 IntervalContainer>(assignment_proto, interval_var_container_,
597 &AssignmentProto::add_interval_var_assignment);
598 RealSave<SequenceVar, SequenceVarElement, SequenceVarAssignment,
599 SequenceContainer>(assignment_proto, sequence_var_container_,
600 &AssignmentProto::add_sequence_var_assignment);
601 if (HasObjective()) {
602 const IntVar* objective = Objective();
603 const std::string& name = objective->name();
604 if (!name.empty()) {
605 IntVarAssignment* objective = assignment_proto->mutable_objective();
606 objective->set_var_id(name);
607 const int64_t obj_min = ObjectiveMin();
608 const int64_t obj_max = ObjectiveMax();
609 objective->set_min(obj_min);
610 objective->set_max(obj_max);
611 objective->set_active(ActivatedObjective());
612 }
613 }
614 }
615
616 template <class Container, class Element>
RealDebugString(const Container & container,std::string * const out)617 void RealDebugString(const Container& container, std::string* const out) {
618 for (const Element& element : container.elements()) {
619 if (element.Var() != nullptr) {
620 absl::StrAppendFormat(out, "%s %s | ", element.Var()->name(),
621 element.DebugString());
622 }
623 }
624 }
625
DebugString() const626 std::string Assignment::DebugString() const {
627 std::string out = "Assignment(";
628 RealDebugString<IntContainer, IntVarElement>(int_var_container_, &out);
629 RealDebugString<IntervalContainer, IntervalVarElement>(
630 interval_var_container_, &out);
631 RealDebugString<SequenceContainer, SequenceVarElement>(
632 sequence_var_container_, &out);
633 if (HasObjective() && objective_element_.Activated()) {
634 out += objective_element_.DebugString();
635 }
636 out += ")";
637 return out;
638 }
639
Add(IntVar * const var)640 IntVarElement* Assignment::Add(IntVar* const var) {
641 return int_var_container_.Add(var);
642 }
643
Add(const std::vector<IntVar * > & vars)644 void Assignment::Add(const std::vector<IntVar*>& vars) {
645 for (IntVar* const var : vars) {
646 Add(var);
647 }
648 }
649
FastAdd(IntVar * const var)650 IntVarElement* Assignment::FastAdd(IntVar* const var) {
651 return int_var_container_.FastAdd(var);
652 }
653
Min(const IntVar * const var) const654 int64_t Assignment::Min(const IntVar* const var) const {
655 return int_var_container_.Element(var).Min();
656 }
657
Max(const IntVar * const var) const658 int64_t Assignment::Max(const IntVar* const var) const {
659 return int_var_container_.Element(var).Max();
660 }
661
Value(const IntVar * const var) const662 int64_t Assignment::Value(const IntVar* const var) const {
663 return int_var_container_.Element(var).Value();
664 }
665
Bound(const IntVar * const var) const666 bool Assignment::Bound(const IntVar* const var) const {
667 return int_var_container_.Element(var).Bound();
668 }
669
SetMin(const IntVar * const var,int64_t m)670 void Assignment::SetMin(const IntVar* const var, int64_t m) {
671 int_var_container_.MutableElement(var)->SetMin(m);
672 }
673
SetMax(const IntVar * const var,int64_t m)674 void Assignment::SetMax(const IntVar* const var, int64_t m) {
675 int_var_container_.MutableElement(var)->SetMax(m);
676 }
677
SetRange(const IntVar * const var,int64_t l,int64_t u)678 void Assignment::SetRange(const IntVar* const var, int64_t l, int64_t u) {
679 int_var_container_.MutableElement(var)->SetRange(l, u);
680 }
681
SetValue(const IntVar * const var,int64_t value)682 void Assignment::SetValue(const IntVar* const var, int64_t value) {
683 int_var_container_.MutableElement(var)->SetValue(value);
684 }
685
686 // ----- Interval Var -----
687
Add(IntervalVar * const var)688 IntervalVarElement* Assignment::Add(IntervalVar* const var) {
689 return interval_var_container_.Add(var);
690 }
691
Add(const std::vector<IntervalVar * > & vars)692 void Assignment::Add(const std::vector<IntervalVar*>& vars) {
693 for (IntervalVar* const var : vars) {
694 Add(var);
695 }
696 }
697
FastAdd(IntervalVar * const var)698 IntervalVarElement* Assignment::FastAdd(IntervalVar* const var) {
699 return interval_var_container_.FastAdd(var);
700 }
701
StartMin(const IntervalVar * const var) const702 int64_t Assignment::StartMin(const IntervalVar* const var) const {
703 return interval_var_container_.Element(var).StartMin();
704 }
705
StartMax(const IntervalVar * const var) const706 int64_t Assignment::StartMax(const IntervalVar* const var) const {
707 return interval_var_container_.Element(var).StartMax();
708 }
709
StartValue(const IntervalVar * const var) const710 int64_t Assignment::StartValue(const IntervalVar* const var) const {
711 return interval_var_container_.Element(var).StartValue();
712 }
713
DurationMin(const IntervalVar * const var) const714 int64_t Assignment::DurationMin(const IntervalVar* const var) const {
715 return interval_var_container_.Element(var).DurationMin();
716 }
717
DurationMax(const IntervalVar * const var) const718 int64_t Assignment::DurationMax(const IntervalVar* const var) const {
719 return interval_var_container_.Element(var).DurationMax();
720 }
721
DurationValue(const IntervalVar * const var) const722 int64_t Assignment::DurationValue(const IntervalVar* const var) const {
723 return interval_var_container_.Element(var).DurationValue();
724 }
725
EndMin(const IntervalVar * const var) const726 int64_t Assignment::EndMin(const IntervalVar* const var) const {
727 return interval_var_container_.Element(var).EndMin();
728 }
729
EndMax(const IntervalVar * const var) const730 int64_t Assignment::EndMax(const IntervalVar* const var) const {
731 return interval_var_container_.Element(var).EndMax();
732 }
733
EndValue(const IntervalVar * const var) const734 int64_t Assignment::EndValue(const IntervalVar* const var) const {
735 return interval_var_container_.Element(var).EndValue();
736 }
737
PerformedMin(const IntervalVar * const var) const738 int64_t Assignment::PerformedMin(const IntervalVar* const var) const {
739 return interval_var_container_.Element(var).PerformedMin();
740 }
741
PerformedMax(const IntervalVar * const var) const742 int64_t Assignment::PerformedMax(const IntervalVar* const var) const {
743 return interval_var_container_.Element(var).PerformedMax();
744 }
745
PerformedValue(const IntervalVar * const var) const746 int64_t Assignment::PerformedValue(const IntervalVar* const var) const {
747 return interval_var_container_.Element(var).PerformedValue();
748 }
749
SetStartMin(const IntervalVar * const var,int64_t m)750 void Assignment::SetStartMin(const IntervalVar* const var, int64_t m) {
751 interval_var_container_.MutableElement(var)->SetStartMin(m);
752 }
753
SetStartMax(const IntervalVar * const var,int64_t m)754 void Assignment::SetStartMax(const IntervalVar* const var, int64_t m) {
755 interval_var_container_.MutableElement(var)->SetStartMax(m);
756 }
757
SetStartRange(const IntervalVar * const var,int64_t mi,int64_t ma)758 void Assignment::SetStartRange(const IntervalVar* const var, int64_t mi,
759 int64_t ma) {
760 interval_var_container_.MutableElement(var)->SetStartRange(mi, ma);
761 }
762
SetStartValue(const IntervalVar * const var,int64_t value)763 void Assignment::SetStartValue(const IntervalVar* const var, int64_t value) {
764 interval_var_container_.MutableElement(var)->SetStartValue(value);
765 }
766
SetDurationMin(const IntervalVar * const var,int64_t m)767 void Assignment::SetDurationMin(const IntervalVar* const var, int64_t m) {
768 interval_var_container_.MutableElement(var)->SetDurationMin(m);
769 }
770
SetDurationMax(const IntervalVar * const var,int64_t m)771 void Assignment::SetDurationMax(const IntervalVar* const var, int64_t m) {
772 interval_var_container_.MutableElement(var)->SetDurationMax(m);
773 }
774
SetDurationRange(const IntervalVar * const var,int64_t mi,int64_t ma)775 void Assignment::SetDurationRange(const IntervalVar* const var, int64_t mi,
776 int64_t ma) {
777 interval_var_container_.MutableElement(var)->SetDurationRange(mi, ma);
778 }
779
SetDurationValue(const IntervalVar * const var,int64_t value)780 void Assignment::SetDurationValue(const IntervalVar* const var, int64_t value) {
781 interval_var_container_.MutableElement(var)->SetDurationValue(value);
782 }
783
SetEndMin(const IntervalVar * const var,int64_t m)784 void Assignment::SetEndMin(const IntervalVar* const var, int64_t m) {
785 interval_var_container_.MutableElement(var)->SetEndMin(m);
786 }
787
SetEndMax(const IntervalVar * const var,int64_t m)788 void Assignment::SetEndMax(const IntervalVar* const var, int64_t m) {
789 interval_var_container_.MutableElement(var)->SetEndMax(m);
790 }
791
SetEndRange(const IntervalVar * const var,int64_t mi,int64_t ma)792 void Assignment::SetEndRange(const IntervalVar* const var, int64_t mi,
793 int64_t ma) {
794 interval_var_container_.MutableElement(var)->SetEndRange(mi, ma);
795 }
796
SetEndValue(const IntervalVar * const var,int64_t value)797 void Assignment::SetEndValue(const IntervalVar* const var, int64_t value) {
798 interval_var_container_.MutableElement(var)->SetEndValue(value);
799 }
800
SetPerformedMin(const IntervalVar * const var,int64_t m)801 void Assignment::SetPerformedMin(const IntervalVar* const var, int64_t m) {
802 interval_var_container_.MutableElement(var)->SetPerformedMin(m);
803 }
804
SetPerformedMax(const IntervalVar * const var,int64_t m)805 void Assignment::SetPerformedMax(const IntervalVar* const var, int64_t m) {
806 interval_var_container_.MutableElement(var)->SetPerformedMax(m);
807 }
808
SetPerformedRange(const IntervalVar * const var,int64_t mi,int64_t ma)809 void Assignment::SetPerformedRange(const IntervalVar* const var, int64_t mi,
810 int64_t ma) {
811 interval_var_container_.MutableElement(var)->SetPerformedRange(mi, ma);
812 }
813
SetPerformedValue(const IntervalVar * const var,int64_t value)814 void Assignment::SetPerformedValue(const IntervalVar* const var,
815 int64_t value) {
816 interval_var_container_.MutableElement(var)->SetPerformedValue(value);
817 }
818
819 // ----- Sequence Var -----
820
Add(SequenceVar * const var)821 SequenceVarElement* Assignment::Add(SequenceVar* const var) {
822 return sequence_var_container_.Add(var);
823 }
824
Add(const std::vector<SequenceVar * > & vars)825 void Assignment::Add(const std::vector<SequenceVar*>& vars) {
826 for (SequenceVar* const var : vars) {
827 Add(var);
828 }
829 }
830
FastAdd(SequenceVar * const var)831 SequenceVarElement* Assignment::FastAdd(SequenceVar* const var) {
832 return sequence_var_container_.FastAdd(var);
833 }
834
ForwardSequence(const SequenceVar * const var) const835 const std::vector<int>& Assignment::ForwardSequence(
836 const SequenceVar* const var) const {
837 return sequence_var_container_.Element(var).ForwardSequence();
838 }
839
BackwardSequence(const SequenceVar * const var) const840 const std::vector<int>& Assignment::BackwardSequence(
841 const SequenceVar* const var) const {
842 return sequence_var_container_.Element(var).BackwardSequence();
843 }
844
Unperformed(const SequenceVar * const var) const845 const std::vector<int>& Assignment::Unperformed(
846 const SequenceVar* const var) const {
847 return sequence_var_container_.Element(var).Unperformed();
848 }
849
SetSequence(const SequenceVar * const var,const std::vector<int> & forward_sequence,const std::vector<int> & backward_sequence,const std::vector<int> & unperformed)850 void Assignment::SetSequence(const SequenceVar* const var,
851 const std::vector<int>& forward_sequence,
852 const std::vector<int>& backward_sequence,
853 const std::vector<int>& unperformed) {
854 sequence_var_container_.MutableElement(var)->SetSequence(
855 forward_sequence, backward_sequence, unperformed);
856 }
857
SetForwardSequence(const SequenceVar * const var,const std::vector<int> & forward_sequence)858 void Assignment::SetForwardSequence(const SequenceVar* const var,
859 const std::vector<int>& forward_sequence) {
860 sequence_var_container_.MutableElement(var)->SetForwardSequence(
861 forward_sequence);
862 }
863
SetBackwardSequence(const SequenceVar * const var,const std::vector<int> & backward_sequence)864 void Assignment::SetBackwardSequence(
865 const SequenceVar* const var, const std::vector<int>& backward_sequence) {
866 sequence_var_container_.MutableElement(var)->SetBackwardSequence(
867 backward_sequence);
868 }
869
SetUnperformed(const SequenceVar * const var,const std::vector<int> & unperformed)870 void Assignment::SetUnperformed(const SequenceVar* const var,
871 const std::vector<int>& unperformed) {
872 sequence_var_container_.MutableElement(var)->SetUnperformed(unperformed);
873 }
874
875 // ----- Objective -----
876
AddObjective(IntVar * const v)877 void Assignment::AddObjective(IntVar* const v) {
878 // Check if adding twice an objective to the solution.
879 CHECK(!HasObjective());
880 objective_element_.Reset(v);
881 }
882
Objective() const883 IntVar* Assignment::Objective() const { return objective_element_.Var(); }
884
ObjectiveMin() const885 int64_t Assignment::ObjectiveMin() const {
886 if (HasObjective()) {
887 return objective_element_.Min();
888 }
889 return 0;
890 }
891
ObjectiveMax() const892 int64_t Assignment::ObjectiveMax() const {
893 if (HasObjective()) {
894 return objective_element_.Max();
895 }
896 return 0;
897 }
898
ObjectiveValue() const899 int64_t Assignment::ObjectiveValue() const {
900 if (HasObjective()) {
901 return objective_element_.Value();
902 }
903 return 0;
904 }
905
ObjectiveBound() const906 bool Assignment::ObjectiveBound() const {
907 if (HasObjective()) {
908 return objective_element_.Bound();
909 }
910 return true;
911 }
912
SetObjectiveMin(int64_t m)913 void Assignment::SetObjectiveMin(int64_t m) {
914 if (HasObjective()) {
915 objective_element_.SetMin(m);
916 }
917 }
918
SetObjectiveMax(int64_t m)919 void Assignment::SetObjectiveMax(int64_t m) {
920 if (HasObjective()) {
921 objective_element_.SetMax(m);
922 }
923 }
924
SetObjectiveRange(int64_t l,int64_t u)925 void Assignment::SetObjectiveRange(int64_t l, int64_t u) {
926 if (HasObjective()) {
927 objective_element_.SetRange(l, u);
928 }
929 }
930
SetObjectiveValue(int64_t value)931 void Assignment::SetObjectiveValue(int64_t value) {
932 if (HasObjective()) {
933 objective_element_.SetValue(value);
934 }
935 }
936
Activate(const IntVar * const var)937 void Assignment::Activate(const IntVar* const var) {
938 int_var_container_.MutableElement(var)->Activate();
939 }
940
Deactivate(const IntVar * const var)941 void Assignment::Deactivate(const IntVar* const var) {
942 int_var_container_.MutableElement(var)->Deactivate();
943 }
944
Activated(const IntVar * const var) const945 bool Assignment::Activated(const IntVar* const var) const {
946 return int_var_container_.Element(var).Activated();
947 }
948
Activate(const IntervalVar * const var)949 void Assignment::Activate(const IntervalVar* const var) {
950 interval_var_container_.MutableElement(var)->Activate();
951 }
952
Deactivate(const IntervalVar * const var)953 void Assignment::Deactivate(const IntervalVar* const var) {
954 interval_var_container_.MutableElement(var)->Deactivate();
955 }
956
Activated(const IntervalVar * const var) const957 bool Assignment::Activated(const IntervalVar* const var) const {
958 return interval_var_container_.Element(var).Activated();
959 }
960
Activate(const SequenceVar * const var)961 void Assignment::Activate(const SequenceVar* const var) {
962 sequence_var_container_.MutableElement(var)->Activate();
963 }
964
Deactivate(const SequenceVar * const var)965 void Assignment::Deactivate(const SequenceVar* const var) {
966 sequence_var_container_.MutableElement(var)->Deactivate();
967 }
968
Activated(const SequenceVar * const var) const969 bool Assignment::Activated(const SequenceVar* const var) const {
970 return sequence_var_container_.Element(var).Activated();
971 }
972
ActivateObjective()973 void Assignment::ActivateObjective() {
974 if (HasObjective()) {
975 objective_element_.Activate();
976 }
977 }
978
DeactivateObjective()979 void Assignment::DeactivateObjective() {
980 if (HasObjective()) {
981 objective_element_.Deactivate();
982 }
983 }
984
ActivatedObjective() const985 bool Assignment::ActivatedObjective() const {
986 if (HasObjective()) {
987 return objective_element_.Activated();
988 }
989 return true;
990 }
991
Contains(const IntVar * const var) const992 bool Assignment::Contains(const IntVar* const var) const {
993 return int_var_container_.Contains(var);
994 }
995
Contains(const IntervalVar * const var) const996 bool Assignment::Contains(const IntervalVar* const var) const {
997 return interval_var_container_.Contains(var);
998 }
999
Contains(const SequenceVar * const var) const1000 bool Assignment::Contains(const SequenceVar* const var) const {
1001 return sequence_var_container_.Contains(var);
1002 }
1003
CopyIntersection(const Assignment * assignment)1004 void Assignment::CopyIntersection(const Assignment* assignment) {
1005 int_var_container_.CopyIntersection(assignment->int_var_container_);
1006 interval_var_container_.CopyIntersection(assignment->interval_var_container_);
1007 sequence_var_container_.CopyIntersection(assignment->sequence_var_container_);
1008 if (objective_element_.Var() == assignment->objective_element_.Var()) {
1009 objective_element_ = assignment->objective_element_;
1010 }
1011 }
1012
Copy(const Assignment * assignment)1013 void Assignment::Copy(const Assignment* assignment) {
1014 Clear();
1015 int_var_container_.Copy(assignment->int_var_container_);
1016 interval_var_container_.Copy(assignment->interval_var_container_);
1017 sequence_var_container_.Copy(assignment->sequence_var_container_);
1018 objective_element_ = assignment->objective_element_;
1019 }
1020
SetAssignmentFromAssignment(Assignment * target_assignment,const std::vector<IntVar * > & target_vars,const Assignment * source_assignment,const std::vector<IntVar * > & source_vars)1021 void SetAssignmentFromAssignment(Assignment* target_assignment,
1022 const std::vector<IntVar*>& target_vars,
1023 const Assignment* source_assignment,
1024 const std::vector<IntVar*>& source_vars) {
1025 const int vars_size = target_vars.size();
1026 CHECK_EQ(source_vars.size(), vars_size);
1027 CHECK(target_assignment != nullptr);
1028
1029 target_assignment->Clear();
1030 const Solver* const target_solver = target_assignment->solver();
1031 const Solver* const source_solver = source_assignment->solver();
1032 for (int index = 0; index < vars_size; index++) {
1033 IntVar* target_var = target_vars[index];
1034 CHECK_EQ(target_var->solver(), target_solver);
1035 IntVar* source_var = source_vars[index];
1036 CHECK_EQ(source_var->solver(), source_solver);
1037 target_assignment->Add(target_var)
1038 ->SetValue(source_assignment->Value(source_var));
1039 }
1040 }
1041
MakeAssignment()1042 Assignment* Solver::MakeAssignment() { return RevAlloc(new Assignment(this)); }
1043
MakeAssignment(const Assignment * const a)1044 Assignment* Solver::MakeAssignment(const Assignment* const a) {
1045 return RevAlloc(new Assignment(a));
1046 }
1047
1048 // ----- Storing and Restoring assignments -----
1049 namespace {
1050 class RestoreAssignment : public DecisionBuilder {
1051 public:
RestoreAssignment(Assignment * assignment)1052 explicit RestoreAssignment(Assignment* assignment)
1053 : assignment_(assignment) {}
1054
~RestoreAssignment()1055 ~RestoreAssignment() override {}
1056
Next(Solver * const solver)1057 Decision* Next(Solver* const solver) override {
1058 assignment_->Restore();
1059 return nullptr;
1060 }
1061
DebugString() const1062 std::string DebugString() const override { return "RestoreAssignment"; }
1063
1064 private:
1065 Assignment* const assignment_;
1066 };
1067
1068 class StoreAssignment : public DecisionBuilder {
1069 public:
StoreAssignment(Assignment * assignment)1070 explicit StoreAssignment(Assignment* assignment) : assignment_(assignment) {}
1071
~StoreAssignment()1072 ~StoreAssignment() override {}
1073
Next(Solver * const solver)1074 Decision* Next(Solver* const solver) override {
1075 assignment_->Store();
1076 return nullptr;
1077 }
1078
DebugString() const1079 std::string DebugString() const override { return "StoreAssignment"; }
1080
1081 private:
1082 Assignment* const assignment_;
1083 };
1084 } // namespace
1085
MakeRestoreAssignment(Assignment * assignment)1086 DecisionBuilder* Solver::MakeRestoreAssignment(Assignment* assignment) {
1087 return RevAlloc(new RestoreAssignment(assignment));
1088 }
1089
MakeStoreAssignment(Assignment * assignment)1090 DecisionBuilder* Solver::MakeStoreAssignment(Assignment* assignment) {
1091 return RevAlloc(new StoreAssignment(assignment));
1092 }
1093
operator <<(std::ostream & out,const Assignment & assignment)1094 std::ostream& operator<<(std::ostream& out, const Assignment& assignment) {
1095 return out << assignment.DebugString();
1096 }
1097
1098 } // namespace operations_research
1099