19 #include "absl/container/flat_hash_map.h"
20 #include "absl/strings/str_format.h"
21 #include "absl/strings/str_join.h"
28 #include "ortools/constraint_solver/assignment.pb.h"
54 SetRange(element.min_, element.max_);
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()) {
75 if (var_ != element.var_) {
86 return min_ == element.min_ && max_ == element.max_;
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());
100 return absl::StrFormat(
"(%d)", min_);
102 return absl::StrFormat(
"(%d..%d)", min_, max_);
129 element->
Copy(*
this);
149 if (performed_max_ != 0LL) {
154 end_min_ = var_->
EndMin();
155 end_max_ = var_->
EndMax();
160 if (performed_max_ == performed_min_) {
163 if (performed_max_ != 0LL) {
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()) {
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());
204 absl::StrAppendFormat(&out,
"(start = %d", start_min_);
205 if (start_max_ != start_min_) {
206 absl::StrAppendFormat(&out,
"..%d", start_max_);
208 absl::StrAppendFormat(&out,
", duration = %d", duration_min_);
209 if (duration_max_ != duration_min_) {
210 absl::StrAppendFormat(&out,
"..%d", duration_max_);
212 absl::StrAppendFormat(&out,
", status = %d", performed_min_);
213 if (performed_max_ != performed_min_) {
214 absl::StrAppendFormat(&out,
"..%d", performed_max_);
224 if (var_ != element.var_) {
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_;
251 forward_sequence_.clear();
252 backward_sequence_.clear();
253 unperformed_.clear();
258 element->
Copy(*
this);
263 forward_sequence_ = element.forward_sequence_;
264 backward_sequence_ = element.backward_sequence_;
265 unperformed_ = element.unperformed_;
275 var_->
FillSequence(&forward_sequence_, &backward_sequence_, &unperformed_);
279 var_->
RankSequence(forward_sequence_, backward_sequence_, unperformed_);
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);
288 for (
const int32 backward_sequence :
289 sequence_var_assignment_proto.backward_sequence()) {
290 backward_sequence_.push_back(backward_sequence);
292 for (
const int32 unperformed : sequence_var_assignment_proto.unperformed()) {
293 unperformed_.push_back(unperformed);
295 if (sequence_var_assignment_proto.active()) {
300 DCHECK(CheckClassInvariants());
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);
310 for (
const int backward_sequence : backward_sequence_) {
311 sequence_var_assignment_proto->add_backward_sequence(backward_sequence);
313 for (
const int unperformed : unperformed_) {
314 sequence_var_assignment_proto->add_unperformed(unperformed);
320 return absl::StrFormat(
"[forward %s, backward %s, unperformed [%s]]",
321 absl::StrJoin(forward_sequence_,
" -> "),
322 absl::StrJoin(backward_sequence_,
" -> "),
323 absl::StrJoin(unperformed_,
", "));
330 if (var_ != element.var_) {
341 return forward_sequence_ == element.forward_sequence_ &&
342 backward_sequence_ == element.backward_sequence_ &&
343 unperformed_ == element.unperformed_;
347 return forward_sequence_;
351 return backward_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());
368 const std::vector<int>& forward_sequence) {
369 forward_sequence_ = forward_sequence;
373 const std::vector<int>& backward_sequence) {
374 backward_sequence_ = backward_sequence;
378 unperformed_ = unperformed;
381 bool SequenceVarElement::CheckClassInvariants() {
382 absl::flat_hash_set<int> visited;
383 for (
const int forward_sequence : forward_sequence_) {
387 visited.insert(forward_sequence);
389 for (
const int backward_sequence : backward_sequence_) {
393 visited.insert(backward_sequence);
395 for (
const int unperformed : unperformed_) {
399 visited.insert(unperformed);
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_) {}
419 objective_element_.
Reset(
nullptr);
420 int_var_container_.
Clear();
421 interval_var_container_.
Clear();
422 sequence_var_container_.
Clear();
426 int_var_container_.
Store();
427 interval_var_container_.
Store();
428 sequence_var_container_.
Store();
430 objective_element_.
Store();
437 interval_var_container_.
Restore();
438 sequence_var_container_.
Restore();
444 template <
class V,
class E>
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) {
451 const V*
const var = element->
Var();
454 LOG(
INFO) <<
"Cannot save/load variables with empty name"
455 <<
"; variable will be ignored";
457 LOG(
INFO) <<
"Cannot save/load variables with duplicate names: " <<
name
458 <<
"; variable will be ignored";
460 (*id_to_element_map)[
name] = element;
465 template <
class E,
class P>
466 void LoadElement(
const absl::flat_hash_map<std::string, E*>& id_to_element_map,
468 const std::string& var_id =
proto.var_id();
469 CHECK(!var_id.empty());
470 E* element =
nullptr;
472 element->LoadFromProto(
proto);
474 LOG(
INFO) <<
"Variable " << var_id
475 <<
" not in assignment; skipping variable";
484 LOG(
INFO) <<
"Cannot open " << filename;
492 AssignmentProto assignment_proto;
495 LOG(
INFO) <<
"No assignment found in " <<
file->filename();
498 Load(assignment_proto);
499 return reader.
Close();
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);
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));
528 RealLoad<IntVar, IntVarElement, IntVarAssignment, IntContainer>(
529 assignment_proto, &int_var_container_,
530 &AssignmentProto::int_var_assignment_size,
531 &AssignmentProto::int_var_assignment);
534 &AssignmentProto::interval_var_assignment_size,
535 &AssignmentProto::interval_var_assignment);
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());
545 const int64 obj_min = objective.min();
546 const int64 obj_max = objective.max();
548 if (objective.active()) {
560 LOG(
INFO) <<
"Cannot open " << filename;
568 AssignmentProto assignment_proto;
569 Save(&assignment_proto);
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();
581 Proto*
const var_assignment_proto = (assignment_proto->*Add)();
582 element.WriteToProto(var_assignment_proto);
588 assignment_proto->Clear();
589 RealSave<IntVar, IntVarElement, IntVarAssignment, IntContainer>(
590 assignment_proto, int_var_container_,
591 &AssignmentProto::add_int_var_assignment);
594 &AssignmentProto::add_interval_var_assignment);
597 &AssignmentProto::add_sequence_var_assignment);
600 const std::string&
name = objective->
name();
602 IntVarAssignment* objective = assignment_proto->mutable_objective();
603 objective->set_var_id(
name);
606 objective->set_min(obj_min);
607 objective->set_max(obj_max);
613 template <
class Container,
class Element>
615 for (
const Element& element : container.elements()) {
616 if (element.Var() !=
nullptr) {
617 absl::StrAppendFormat(out,
"%s %s | ", element.Var()->name(),
618 element.DebugString());
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);
638 return int_var_container_.
Add(
var);
686 return interval_var_container_.
Add(
var);
817 return sequence_var_container_.
Add(
var);
846 const std::vector<int>& forward_sequence,
847 const std::vector<int>& backward_sequence,
848 const std::vector<int>& unperformed) {
850 forward_sequence, backward_sequence, unperformed);
854 const std::vector<int>& forward_sequence) {
860 const SequenceVar*
const var,
const std::vector<int>& backward_sequence) {
866 const std::vector<int>& unperformed) {
875 objective_element_.
Reset(v);
882 return objective_element_.
Min();
889 return objective_element_.
Max();
896 return objective_element_.
Value();
903 return objective_element_.
Bound();
910 objective_element_.
SetMin(m);
916 objective_element_.
SetMax(m);
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_;
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_;
1017 const std::vector<IntVar*>& target_vars,
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);
1024 target_assignment->
Clear();
1025 const Solver*
const target_solver = target_assignment->
solver();
1026 const Solver*
const source_solver = source_assignment->
solver();
1032 target_assignment->
Add(target_var)
1047 explicit RestoreAssignment(
Assignment* assignment)
1048 : assignment_(assignment) {}
1050 ~RestoreAssignment()
override {}
1052 Decision* Next(Solver*
const solver)
override {
1053 assignment_->Restore();
1057 std::string DebugString()
const override {
return "RestoreAssignment"; }
1060 Assignment*
const assignment_;
1065 explicit StoreAssignment(Assignment* assignment) : assignment_(assignment) {}
1069 Decision* Next(Solver*
const solver)
override {
1070 assignment_->Store();
1074 std::string DebugString()
const override {
return "StoreAssignment"; }
1077 Assignment*
const assignment_;
1082 return RevAlloc(
new RestoreAssignment(assignment));
#define CHECK_EQ(val1, val2)
#define DCHECK(condition)
E * MutableElement(const V *const var)
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.
bool ActivatedObjective() const
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)
void SetObjectiveRange(int64 l, int64 u)
const std::vector< int > & BackwardSequence(const SequenceVar *const var) const
int64 ObjectiveMin() const
void SetDurationValue(const IntervalVar *const var, int64 value)
void SetEndMax(const IntervalVar *const var, int64 m)
Assignment(Solver *const s)
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)
IntVar * Objective() const
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
bool HasObjective() const
void AddObjective(IntVar *const v)
int64 ObjectiveValue() const
int64 StartMin(const IntervalVar *const var) const
void Activate(const IntVar *const var)
void SetPerformedMin(const IntervalVar *const var, int64 m)
void DeactivateObjective()
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 SetObjectiveMax(int64 m)
void SetStartValue(const IntervalVar *const var, int64 value)
void CopyIntersection(const Assignment *assignment)
Copies the intersection of the two assignments to the current assignment.
bool ObjectiveBound() const
void SetDurationMax(const IntervalVar *const var, int64 m)
void SetStartRange(const IntervalVar *const var, int64 mi, int64 ma)
void SetObjectiveMin(int64 m)
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 ObjectiveMax() const
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
std::string DebugString() const override
void SetObjectiveValue(int64 value)
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)
void Reset(IntVar *const var)
bool operator==(const IntVarElement &element) const
std::string DebugString() const
void WriteToProto(IntVarAssignment *int_var_assignment_proto) const
void SetRange(int64 l, int64 u)
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.
IntervalVarElement * Clone()
void SetPerformedValue(int64 v)
void LoadFromProto(const IntervalVarAssignment &interval_var_assignment_proto)
void SetPerformedRange(int64 mi, int64 ma)
void SetStartValue(int64 v)
void Reset(IntervalVar *const var)
void SetPerformedMin(int64 m)
int64 DurationMin() const
void SetDurationValue(int64 v)
void SetStartMax(int64 m)
void SetEndValue(int64 v)
void SetEndRange(int64 mi, int64 ma)
int64 DurationValue() const
std::string DebugString() const
int64 DurationMax() const
void SetStartRange(int64 mi, int64 ma)
int64 PerformedValue() const
void SetStartMin(int64 m)
void SetDurationRange(int64 mi, int64 ma)
bool operator==(const IntervalVarElement &element) const
void Copy(const IntervalVarElement &element)
void SetDurationMin(int64 m)
void WriteToProto(IntervalVarAssignment *interval_var_assignment_proto) const
void SetPerformedMax(int64 m)
void SetDurationMax(int64 m)
int64 PerformedMin() const
int64 PerformedMax() 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)
void Reset(SequenceVar *const var)
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)
std::string DebugString() const
SequenceVarElement * Clone()
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)
bool WriteProtocolMessage(const P &proto)
static const int64 kint64max
static const int64 kint64min
absl::Status Open(const absl::string_view &filename, const absl::string_view &mode, File **f, int flags)
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
bool ContainsKey(const Collection &collection, const Key &key)
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)())