or-tools/src/constraint_solver/assignment.cc Source File

00001 // Copyright 2010-2012 Google
00002 // Licensed under the Apache License, Version 2.0 (the "License");
00003 // you may not use this file except in compliance with the License.
00004 // You may obtain a copy of the License at
00005 //
00006 //     http://www.apache.org/licenses/LICENSE-2.0
00007 //
00008 // Unless required by applicable law or agreed to in writing, software
00009 // distributed under the License is distributed on an "AS IS" BASIS,
00010 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00011 // See the License for the specific language governing permissions and
00012 // limitations under the License.
00013 
00014 #include <stddef.h>
00015 #include "base/hash.h"
00016 #include <string>
00017 #include <vector>
00018 
00019 #include "base/integral_types.h"
00020 #include "base/logging.h"
00021 #include "base/stringprintf.h"
00022 #include "base/file.h"
00023 #include "base/recordio.h"
00024 #include "base/concise_iterator.h"
00025 #include "base/map-util.h"
00026 #include "base/hash.h"
00027 #include "constraint_solver/assignment.pb.h"
00028 #include "constraint_solver/constraint_solver.h"
00029 #include "util/string_array.h"
00030 
00031 namespace operations_research {
00032 
00033 // ----------------- Solutions ------------------------
00034 
00035 // ----- IntVarElement -----
00036 
00037 IntVarElement::IntVarElement() {
00038   Reset(NULL);
00039 }
00040 
00041 IntVarElement::IntVarElement(IntVar* const var) {
00042   Reset(var);
00043 }
00044 
00045 void IntVarElement::Reset(IntVar* const var) {
00046   var_ = var;
00047   min_ = kint64min;
00048   max_ = kint64max;
00049 }
00050 
00051 IntVarElement* IntVarElement::Clone() {
00052   IntVarElement* element = new IntVarElement;
00053   element->Copy(*this);
00054   return element;
00055 }
00056 
00057 void IntVarElement::Copy(const IntVarElement& element) {
00058   SetRange(element.min_, element.max_);
00059   var_ = element.var_;
00060   if (element.Activated()) {
00061     Activate();
00062   } else {
00063     Deactivate();
00064   }
00065 }
00066 
00067 void IntVarElement::LoadFromProto(
00068     const IntVarAssignmentProto& int_var_assignment_proto) {
00069   min_ = int_var_assignment_proto.min();
00070   max_ = int_var_assignment_proto.has_max() ?
00071       int_var_assignment_proto.max() :
00072       min_;
00073   if (int_var_assignment_proto.active()) {
00074     Activate();
00075   } else {
00076     Deactivate();
00077   }
00078 }
00079 
00080 bool IntVarElement::operator==(const IntVarElement& element) const {
00081   if (var_ != element.var_) {
00082     return false;
00083   }
00084   if (Activated() != element.Activated()) {
00085     return false;
00086   }
00087   if (!Activated() && !element.Activated()) {
00088     // If both elements are deactivated, then they are equal, regardless of
00089     // their min and max.
00090     return true;
00091   }
00092   return min_ == element.min_ && max_ == element.max_;
00093 }
00094 
00095 
00096 void IntVarElement::WriteToProto(
00097     IntVarAssignmentProto* int_var_assignment_proto) const {
00098   int_var_assignment_proto->set_var_id(var_->name());
00099   int_var_assignment_proto->set_min(min_);
00100   if (max_ != min_) {
00101     int_var_assignment_proto->set_max(max_);
00102   }
00103   int_var_assignment_proto->set_active(Activated());
00104 }
00105 
00106 string IntVarElement::DebugString() const {
00107   if (Activated()) {
00108     if (min_ == max_) {
00109       return StringPrintf("(%" GG_LL_FORMAT "d)", min_);
00110     } else {
00111       return StringPrintf("(%" GG_LL_FORMAT "d..%" GG_LL_FORMAT "d)",
00112                           min_, max_);
00113     }
00114   } else {
00115     return "(...)";
00116   }
00117 }
00118 
00119 // ----- IntervalVarElement -----
00120 
00121 IntervalVarElement::IntervalVarElement() {
00122   Reset(NULL);
00123 }
00124 
00125 IntervalVarElement::IntervalVarElement(IntervalVar* const var) {
00126   Reset(var);
00127 }
00128 
00129 void IntervalVarElement::Reset(IntervalVar* const var) {
00130   var_ = var;
00131   start_min_ = kint64min;
00132   start_max_ = kint64max;
00133   duration_min_ = kint64min;
00134   duration_max_ = kint64max;
00135   end_min_ = kint64min;
00136   end_max_ = kint64max;
00137   performed_min_ = 0;
00138   performed_max_ = 1;
00139 }
00140 
00141 IntervalVarElement* IntervalVarElement::Clone() {
00142   IntervalVarElement* element = new IntervalVarElement;
00143   element->Copy(*this);
00144   return element;
00145 }
00146 
00147 void IntervalVarElement::Copy(const IntervalVarElement& element) {
00148   SetStartRange(element.start_min_, element.start_max_);
00149   SetDurationRange(element.duration_min_, element.duration_max_);
00150   SetEndRange(element.end_min_, element.end_max_);
00151   SetPerformedRange(element.performed_min_, element.performed_max_);
00152   var_ = element.var_;
00153   if (element.Activated()) {
00154     Activate();
00155   } else {
00156     Deactivate();
00157   }
00158 }
00159 
00160 void IntervalVarElement::Store() {
00161   performed_min_ = static_cast<int64>(var_->MustBePerformed());
00162   performed_max_ = static_cast<int64>(var_->MayBePerformed());
00163   if (performed_max_ != 0LL) {
00164     start_min_ = var_->StartMin();
00165     start_max_ = var_->StartMax();
00166     duration_min_ = var_->DurationMin();
00167     duration_max_ = var_->DurationMax();
00168     end_min_ = var_->EndMin();
00169     end_max_ = var_->EndMax();
00170   }
00171 }
00172 
00173 void IntervalVarElement::Restore() {
00174   if (performed_max_ == performed_min_) {
00175     var_->SetPerformed(performed_min_);
00176   }
00177   if (performed_max_ != 0LL) {
00178     var_->SetStartRange(start_min_, start_max_);
00179     var_->SetDurationRange(duration_min_, duration_max_);
00180     var_->SetEndRange(end_min_, end_max_);
00181   }
00182 }
00183 
00184 void IntervalVarElement::LoadFromProto(
00185     const IntervalVarAssignmentProto& interval_var_assignment_proto) {
00186   start_min_ = interval_var_assignment_proto.start_min();
00187   start_max_ = interval_var_assignment_proto.has_start_max() ?
00188       interval_var_assignment_proto.start_max() :
00189       start_min_;
00190   duration_min_ = interval_var_assignment_proto.duration_min();
00191   duration_max_ = interval_var_assignment_proto.has_duration_max() ?
00192       interval_var_assignment_proto.duration_max() :
00193       duration_min_;
00194   end_min_ = interval_var_assignment_proto.end_min();
00195   end_max_ = interval_var_assignment_proto.has_end_max() ?
00196       interval_var_assignment_proto.end_max() :
00197       end_min_;
00198   performed_min_ = interval_var_assignment_proto.performed_min();
00199   performed_max_ = interval_var_assignment_proto.has_performed_max() ?
00200       interval_var_assignment_proto.performed_max() :
00201       performed_min_;
00202   if (interval_var_assignment_proto.active()) {
00203     Activate();
00204   } else {
00205     Deactivate();
00206   }
00207 }
00208 
00209 void IntervalVarElement::WriteToProto(
00210     IntervalVarAssignmentProto* interval_var_assignment_proto) const {
00211   interval_var_assignment_proto->set_var_id(var_->name());
00212   interval_var_assignment_proto->set_start_min(start_min_);
00213   if (start_max_ != start_min_) {
00214     interval_var_assignment_proto->set_start_max(start_max_);
00215   }
00216   interval_var_assignment_proto->set_duration_min(duration_min_);
00217   if (duration_max_ != duration_min_) {
00218     interval_var_assignment_proto->set_duration_max(duration_max_);
00219   }
00220   interval_var_assignment_proto->set_end_min(end_min_);
00221   if (end_max_ != end_min_) {
00222     interval_var_assignment_proto->set_end_max(end_max_);
00223   }
00224   interval_var_assignment_proto->set_performed_min(performed_min_);
00225   if (performed_max_ != performed_min_) {
00226     interval_var_assignment_proto->set_performed_max(performed_max_);
00227   }
00228   interval_var_assignment_proto->set_active(Activated());
00229 }
00230 
00231 string IntervalVarElement::DebugString() const {
00232   if (Activated()) {
00233     string out;
00234     SStringPrintf(&out, "(start = %" GG_LL_FORMAT "d", start_min_);
00235     if (start_max_ != start_min_) {
00236       StringAppendF(&out, "..%" GG_LL_FORMAT "d", start_max_);
00237     }
00238     StringAppendF(&out, ", duration = %" GG_LL_FORMAT "d", duration_min_);
00239     if (duration_max_ != duration_min_) {
00240       StringAppendF(&out, "..%" GG_LL_FORMAT "d", duration_max_);
00241     }
00242     StringAppendF(&out, ", status = %" GG_LL_FORMAT "d", performed_min_);
00243     if (performed_max_ != performed_min_) {
00244       StringAppendF(&out, "..%" GG_LL_FORMAT "d", performed_max_);
00245     }
00246     return out;
00247   } else {
00248     return "(...)";
00249   }
00250 }
00251 
00252 bool IntervalVarElement::operator==(const IntervalVarElement& element) const {
00253   if (var_ != element.var_) {
00254     return false;
00255   }
00256   if (Activated() != element.Activated()) {
00257     return false;
00258   }
00259   if (!Activated() && !element.Activated()) {
00260     // If both elements are deactivated, then they are equal, regardless of
00261     // their other fields.
00262     return true;
00263   }
00264   return start_min_ == element.start_min_
00265       && start_max_ == element.start_max_
00266       && duration_min_ == element.duration_min_
00267       && duration_max_ == element.duration_max_
00268       && end_min_ == element.end_min_
00269       && end_max_ == element.end_max_
00270       && performed_min_ == element.performed_min_
00271       && performed_max_ == element.performed_max_
00272       && var_ == element.var_;
00273 }
00274 
00275 // ----- SequenceVarElement -----
00276 
00277 SequenceVarElement::SequenceVarElement() {
00278   Reset(NULL);
00279 }
00280 
00281 SequenceVarElement::SequenceVarElement(SequenceVar* const var) {
00282   Reset(var);
00283 }
00284 
00285 void SequenceVarElement::Reset(SequenceVar* const var) {
00286   var_ = var;
00287   forward_sequence_.clear();
00288   backward_sequence_.clear();
00289   unperformed_.clear();
00290 }
00291 
00292 SequenceVarElement* SequenceVarElement::Clone() {
00293   SequenceVarElement* const element = new SequenceVarElement;
00294   element->Copy(*this);
00295   return element;
00296 }
00297 
00298 void SequenceVarElement::Copy(const SequenceVarElement& element) {
00299   forward_sequence_ = element.forward_sequence_;
00300   backward_sequence_ = element.backward_sequence_;
00301   unperformed_ = element.unperformed_;
00302   var_ = element.var_;
00303   if (element.Activated()) {
00304     Activate();
00305   } else {
00306     Deactivate();
00307   }
00308 }
00309 
00310 void SequenceVarElement::Store() {
00311   var_->FillSequence(&forward_sequence_, &backward_sequence_, &unperformed_);
00312 }
00313 
00314 void SequenceVarElement::Restore() {
00315   var_->RankSequence(forward_sequence_, backward_sequence_, unperformed_);
00316 }
00317 
00318 void SequenceVarElement::LoadFromProto(
00319     const SequenceVarAssignmentProto& sequence_var_assignment_proto) {
00320   for (int i = 0;
00321        i < sequence_var_assignment_proto.forward_sequence_size();
00322        ++i) {
00323     forward_sequence_.push_back(
00324         sequence_var_assignment_proto.forward_sequence(i));
00325   }
00326   for (int i = 0;
00327        i < sequence_var_assignment_proto.backward_sequence_size();
00328        ++i) {
00329     backward_sequence_.push_back(
00330         sequence_var_assignment_proto.backward_sequence(i));
00331   }
00332   for (int i = 0;
00333        i < sequence_var_assignment_proto.unperformed_size();
00334        ++i) {
00335     unperformed_.push_back(
00336         sequence_var_assignment_proto.unperformed(i));
00337   }
00338   if (sequence_var_assignment_proto.active()) {
00339     Activate();
00340   } else {
00341     Deactivate();
00342   }
00343   DCHECK(CheckClassInvariants());
00344 }
00345 
00346 void SequenceVarElement::WriteToProto(
00347     SequenceVarAssignmentProto* sequence_var_assignment_proto) const {
00348   sequence_var_assignment_proto->set_var_id(var_->name());
00349   sequence_var_assignment_proto->set_active(Activated());
00350   for (int i = 0; i < forward_sequence_.size(); ++i) {
00351     sequence_var_assignment_proto->add_forward_sequence(forward_sequence_[i]);
00352   }
00353   for (int i = 0; i < backward_sequence_.size(); ++i) {
00354     sequence_var_assignment_proto->add_backward_sequence(backward_sequence_[i]);
00355   }
00356   for (int i = 0; i < unperformed_.size(); ++i) {
00357     sequence_var_assignment_proto->add_unperformed(unperformed_[i]);
00358   }
00359 }
00360 
00361 string SequenceVarElement::DebugString() const {
00362   if (Activated()) {
00363     return StringPrintf("[forward %s, backward %s, unperformed [%s]]",
00364                         IntVectorToString(forward_sequence_, " -> ").c_str(),
00365                         IntVectorToString(backward_sequence_, " -> ").c_str(),
00366                         IntVectorToString(unperformed_, ", ").c_str());
00367   } else {
00368     return "(...)";
00369   }
00370 }
00371 
00372 bool SequenceVarElement::operator==(const SequenceVarElement& element) const {
00373   if (var_ != element.var_) {
00374     return false;
00375   }
00376   if (Activated() != element.Activated()) {
00377     return false;
00378   }
00379   if (!Activated() && !element.Activated()) {
00380     // If both elements are deactivated, then they are equal, regardless of
00381     // their other fields.
00382     return true;
00383   }
00384   return forward_sequence_ == element.forward_sequence_ &&
00385       backward_sequence_ == element.backward_sequence_ &&
00386       unperformed_ == element.unperformed_;
00387 }
00388 
00389 const std::vector<int>& SequenceVarElement::ForwardSequence() const {
00390   return forward_sequence_;
00391 }
00392 
00393 const std::vector<int>& SequenceVarElement::BackwardSequence() const {
00394   return backward_sequence_;
00395 }
00396 
00397 const std::vector<int>& SequenceVarElement::Unperformed() const {
00398   return unperformed_;
00399 }
00400 
00401 void SequenceVarElement::SetSequence(const std::vector<int>& forward_sequence,
00402                                      const std::vector<int>& backward_sequence,
00403                                      const std::vector<int>& unperformed) {
00404   forward_sequence_ = forward_sequence;
00405   backward_sequence_ = backward_sequence;
00406   unperformed_ = unperformed;
00407   DCHECK(CheckClassInvariants());
00408 }
00409 
00410 void SequenceVarElement::SetForwardSequence(
00411     const std::vector<int>& forward_sequence) {
00412   forward_sequence_ = forward_sequence;
00413 }
00414 
00415 void SequenceVarElement::SetBackwardSequence(
00416     const std::vector<int>& backward_sequence) {
00417   backward_sequence_ = backward_sequence;
00418 }
00419 
00420 void SequenceVarElement::SetUnperformed(const std::vector<int>& unperformed) {
00421   unperformed_ = unperformed;
00422 }
00423 
00424 bool SequenceVarElement::CheckClassInvariants() {
00425   hash_set<int> visited;
00426   for (ConstIter<std::vector<int> > it(forward_sequence_); !it.at_end(); ++it) {
00427     if (ContainsKey(visited, *it)) {
00428       return false;
00429     }
00430     visited.insert(*it);
00431   }
00432   for (ConstIter<std::vector<int> > it(backward_sequence_); !it.at_end(); ++it) {
00433     if (ContainsKey(visited, *it)) {
00434       return false;
00435     }
00436     visited.insert(*it);
00437   }
00438   for (ConstIter<std::vector<int> > it(unperformed_); !it.at_end(); ++it) {
00439     if (ContainsKey(visited, *it)) {
00440       return false;
00441     }
00442     visited.insert(*it);
00443   }
00444   return true;
00445 }
00446 
00447 // ----- Assignment -----
00448 
00449 Assignment::Assignment(const Assignment* const copy)
00450     : PropagationBaseObject(copy->solver()),
00451       int_var_container_(copy->int_var_container_),
00452       interval_var_container_(copy->interval_var_container_),
00453       sequence_var_container_(copy->sequence_var_container_),
00454       objective_element_(copy->objective_element_) {}
00455 
00456 Assignment::Assignment(Solver* const s)
00457   : PropagationBaseObject(s),
00458     objective_element_(NULL) {}
00459 
00460 Assignment::~Assignment() {}
00461 
00462 void Assignment::Clear() {
00463   objective_element_.Reset(NULL);
00464   int_var_container_.Clear();
00465   interval_var_container_.Clear();
00466   sequence_var_container_.Clear();
00467 }
00468 
00469 void Assignment::Store() {
00470   int_var_container_.Store();
00471   interval_var_container_.Store();
00472   sequence_var_container_.Store();
00473   if (HasObjective()) {
00474     objective_element_.Store();
00475   }
00476 }
00477 
00478 void Assignment::Restore() {
00479   FreezeQueue();
00480   int_var_container_.Restore();
00481   interval_var_container_.Restore();
00482   sequence_var_container_.Restore();
00483   UnfreezeQueue();
00484 }
00485 
00486 namespace {
00487 
00488 template <class V, class E>
00489 void IdToElementMap(AssignmentContainer<V, E>* container,
00490                     hash_map<string, E*>* id_to_element_map) {
00491   CHECK(id_to_element_map != NULL);
00492   id_to_element_map->clear();
00493   for (int i = 0; i < container->Size(); ++i) {
00494     E& element = container->MutableElement(i);
00495     const V* const var = element.Var();
00496     const string& name = var->name();
00497     if (name.empty()) {
00498       LOG(INFO) << "Cannot save/load variables with empty name"
00499                 << "; variable will be ignored";
00500     } else if (ContainsKey(*id_to_element_map, name)) {
00501       LOG(INFO) << "Cannot save/load variables with duplicate names: " << name
00502                 << "; variable will be ignored";
00503     } else {
00504       (*id_to_element_map)[name] = &element;
00505     }
00506   }
00507 }
00508 
00509 template <class E, class P>
00510 void LoadElement(const hash_map<string, E*>& id_to_element_map,
00511                  const P& proto) {
00512   const string& var_id = proto.var_id();
00513   CHECK(!var_id.empty());
00514   E* element = NULL;
00515   if (FindCopy(id_to_element_map, var_id, &element)) {
00516     element->LoadFromProto(proto);
00517   } else {
00518     LOG(INFO) << "Variable " << var_id
00519               << " not in assignment; skipping variable";
00520   }
00521 }
00522 
00523 }  // namespace
00524 
00525 bool Assignment::Load(const string& filename) {
00526   File::Init();
00527   File* file = File::Open(filename, "r");
00528   if (file == NULL) {
00529     LOG(INFO) << "Cannot open " << filename;
00530     return false;
00531   }
00532   return Load(file);
00533 }
00534 
00535 bool Assignment::Load(File* file) {
00536   CHECK(file != NULL);
00537   AssignmentProto assignment_proto;
00538   RecordReader reader(file);
00539   if (!reader.ReadProtocolMessage(&assignment_proto)) {
00540     LOG(INFO) << "No assignment found in " << file->CreateFileName();
00541     return false;
00542   }
00543   Load(assignment_proto);
00544   return reader.Close();
00545 }
00546 
00547 template <class Var, class Element, class Proto, class Container>
00548 void RealLoad(const AssignmentProto& assignment_proto,
00549               Container* const container,
00550               int (AssignmentProto::*GetSize)() const,
00551               const Proto& (AssignmentProto::*GetElem)(int) const) {  // NOLINT
00552   bool fast_load = (container->Size() == (assignment_proto.*GetSize)());
00553   for (int i = 0; fast_load && i < (assignment_proto.*GetSize)(); ++i) {
00554     Element& element = container->MutableElement(i);
00555     const Proto& proto = (assignment_proto.*GetElem)(i);
00556     if (element.Var()->name() == proto.var_id()) {
00557       element.LoadFromProto(proto);
00558     } else {
00559       fast_load = false;
00560     }
00561   }
00562   if (!fast_load) {
00563     hash_map<string, Element*> id_to_element_map;
00564     IdToElementMap<Var, Element>(container, &id_to_element_map);
00565     for (int i = 0; i < (assignment_proto.*GetSize)(); ++i) {
00566       LoadElement<Element, Proto>(id_to_element_map,
00567                                   (assignment_proto.*GetElem)(i));
00568     }
00569   }
00570 }
00571 
00572 void Assignment::Load(const AssignmentProto& assignment_proto) {
00573   RealLoad<IntVar, IntVarElement, IntVarAssignmentProto, IntContainer> (
00574       assignment_proto,
00575       &int_var_container_,
00576       &AssignmentProto::int_var_assignment_size,
00577       &AssignmentProto::int_var_assignment);
00578   RealLoad<IntervalVar,
00579       IntervalVarElement,
00580       IntervalVarAssignmentProto,
00581       IntervalContainer> (
00582           assignment_proto,
00583           &interval_var_container_,
00584           &AssignmentProto::interval_var_assignment_size,
00585           &AssignmentProto::interval_var_assignment);
00586   RealLoad<SequenceVar,
00587       SequenceVarElement,
00588       SequenceVarAssignmentProto,
00589       SequenceContainer> (
00590           assignment_proto,
00591           &sequence_var_container_,
00592           &AssignmentProto::sequence_var_assignment_size,
00593           &AssignmentProto::sequence_var_assignment);
00594   if (assignment_proto.has_objective()) {
00595     const IntVarAssignmentProto& objective = assignment_proto.objective();
00596     const string objective_id = objective.var_id();
00597     CHECK(!objective_id.empty());
00598     if (HasObjective() && objective_id.compare(Objective()->name()) == 0) {
00599       const int64 obj_min = objective.min();
00600       const int64 obj_max = objective.has_max() ? objective.max() : obj_min;
00601       SetObjectiveRange(obj_min, obj_max);
00602       if (objective.active()) {
00603         ActivateObjective();
00604       } else {
00605         DeactivateObjective();
00606       }
00607     }
00608   }
00609 }
00610 
00611 bool Assignment::Save(const string& filename) const {
00612   File::Init();
00613   File* file = File::Open(filename, "w");
00614   if (file == NULL) {
00615     LOG(INFO) << "Cannot open " << filename;
00616     return false;
00617   }
00618   return Save(file);
00619 }
00620 
00621 bool Assignment::Save(File* file) const {
00622   CHECK(file != NULL);
00623   AssignmentProto assignment_proto;
00624   Save(&assignment_proto);
00625   RecordWriter writer(file);
00626   return writer.WriteProtocolMessage(assignment_proto) && writer.Close();
00627 }
00628 
00629 template <class Var, class Element, class Proto, class Container>
00630 void RealSave(AssignmentProto* const assignment_proto,
00631               const Container& container,
00632               Proto* (AssignmentProto::*Add)()) {
00633   for (int i = 0; i < container.Size(); ++i) {
00634     const Element& element = container.Element(i);
00635     const Var* const var = element.Var();
00636     const string& name = var->name();
00637     if (!name.empty()) {
00638       Proto* const var_assignment_proto = (assignment_proto->*Add)();
00639       element.WriteToProto(var_assignment_proto);
00640     }
00641   }
00642 }
00643 
00644 void Assignment::Save(AssignmentProto* const assignment_proto) const {
00645   assignment_proto->Clear();
00646   RealSave<IntVar, IntVarElement, IntVarAssignmentProto, IntContainer>(
00647       assignment_proto,
00648       int_var_container_,
00649       &AssignmentProto::add_int_var_assignment);
00650   RealSave<IntervalVar,
00651       IntervalVarElement,
00652       IntervalVarAssignmentProto,
00653       IntervalContainer>(
00654           assignment_proto,
00655           interval_var_container_,
00656           &AssignmentProto::add_interval_var_assignment);
00657   RealSave<SequenceVar,
00658       SequenceVarElement,
00659       SequenceVarAssignmentProto,
00660       SequenceContainer>(
00661           assignment_proto,
00662           sequence_var_container_,
00663           &AssignmentProto::add_sequence_var_assignment);
00664   if (HasObjective()) {
00665     const IntVar* objective = Objective();
00666     const string& name = objective->name();
00667     if (!name.empty()) {
00668       IntVarAssignmentProto* objective = assignment_proto->mutable_objective();
00669       objective->set_var_id(name);
00670       const int64 obj_min = ObjectiveMin();
00671       const int64 obj_max = ObjectiveMax();
00672       objective->set_min(obj_min);
00673       if (obj_min != obj_max) {
00674         objective->set_max(obj_max);
00675       }
00676       objective->set_active(ActivatedObjective());
00677     }
00678   }
00679 }
00680 
00681 template <class Container, class Element>
00682 void RealDebugString(const Container& container, string* const out) {
00683   for (int i = 0; i < container.Size(); ++i) {
00684     const Element& element = container.Element(i);
00685     StringAppendF(out, "%s %s | ",
00686                   element.Var()->name().c_str(),
00687                   element.DebugString().c_str());
00688   }
00689 }
00690 
00691 string Assignment::DebugString() const {
00692   string out = "Assignment(";
00693   RealDebugString<IntContainer, IntVarElement>(int_var_container_, &out);
00694   RealDebugString<IntervalContainer, IntervalVarElement>(
00695       interval_var_container_, &out);
00696   RealDebugString<SequenceContainer, SequenceVarElement>(
00697       sequence_var_container_, &out);
00698   if (HasObjective() && objective_element_.Activated()) {
00699     out += objective_element_.DebugString();
00700   }
00701   out += ")";
00702   return out;
00703 }
00704 
00705 IntVarElement& Assignment::Add(IntVar* const v) {
00706   return int_var_container_.Add(v);
00707 }
00708 
00709 void Assignment::Add(IntVar* const* v, int s) {
00710   DCHECK_GE(s, 0);
00711   for (int i = 0; i < s; ++i) {
00712     Add(v[i]);
00713   }
00714 }
00715 
00716 void Assignment::Add(const std::vector<IntVar*>& v) {
00717   for (ConstIter<std::vector<IntVar*> > it(v); !it.at_end(); ++it) {
00718     Add(*it);
00719   }
00720 }
00721 
00722 IntVarElement& Assignment::FastAdd(IntVar* const v) {
00723   return int_var_container_.FastAdd(v);
00724 }
00725 
00726 int64 Assignment::Min(const IntVar* const v) const {
00727   return int_var_container_.Element(v).Min();
00728 }
00729 
00730 int64 Assignment::Max(const IntVar* const v) const {
00731   return int_var_container_.Element(v).Max();
00732 }
00733 
00734 int64 Assignment::Value(const IntVar* const v) const {
00735   return int_var_container_.Element(v).Value();
00736 }
00737 
00738 bool Assignment::Bound(const IntVar* const v) const {
00739   return int_var_container_.Element(v).Bound();
00740 }
00741 
00742 void Assignment::SetMin(const IntVar* const v, int64 m) {
00743   int_var_container_.MutableElement(v).SetMin(m);
00744 }
00745 
00746 void Assignment::SetMax(const IntVar* const v, int64 m) {
00747   int_var_container_.MutableElement(v).SetMax(m);
00748 }
00749 
00750 void Assignment::SetRange(const IntVar* const v, int64 l, int64 u) {
00751   int_var_container_.MutableElement(v).SetRange(l, u);
00752 }
00753 
00754 void Assignment::SetValue(const IntVar* const v, int64 value) {
00755   int_var_container_.MutableElement(v).SetValue(value);
00756 }
00757 
00758 // ----- Interval Var -----
00759 
00760 IntervalVarElement& Assignment::Add(IntervalVar* const v) {
00761   return interval_var_container_.Add(v);
00762 }
00763 
00764 void Assignment::Add(IntervalVar* const * vars, int size) {
00765   DCHECK_GE(size, 0);
00766   for (int i = 0; i < size; ++i) {
00767     Add(vars[i]);
00768   }
00769 }
00770 
00771 void Assignment::Add(const std::vector<IntervalVar*>& vars) {
00772   for (ConstIter<std::vector<IntervalVar*> > it(vars); !it.at_end(); ++it) {
00773     Add(*it);
00774   }
00775 }
00776 
00777 IntervalVarElement& Assignment::FastAdd(IntervalVar* const v) {
00778   return interval_var_container_.FastAdd(v);
00779 }
00780 
00781 int64 Assignment::StartMin(const IntervalVar* const v) const {
00782   return interval_var_container_.Element(v).StartMin();
00783 }
00784 
00785 int64 Assignment::StartMax(const IntervalVar* const v) const {
00786   return interval_var_container_.Element(v).StartMax();
00787 }
00788 
00789 int64 Assignment::StartValue(const IntervalVar* const v) const {
00790   return interval_var_container_.Element(v).StartValue();
00791 }
00792 
00793 int64 Assignment::DurationMin(const IntervalVar* const v) const {
00794   return interval_var_container_.Element(v).DurationMin();
00795 }
00796 
00797 int64 Assignment::DurationMax(const IntervalVar* const v) const {
00798   return interval_var_container_.Element(v).DurationMax();
00799 }
00800 
00801 int64 Assignment::DurationValue(const IntervalVar* const v) const {
00802   return interval_var_container_.Element(v).DurationValue();
00803 }
00804 
00805 int64 Assignment::EndMin(const IntervalVar* const v) const {
00806   return interval_var_container_.Element(v).EndMin();
00807 }
00808 
00809 int64 Assignment::EndMax(const IntervalVar* const v) const {
00810   return interval_var_container_.Element(v).EndMax();
00811 }
00812 
00813 int64 Assignment::EndValue(const IntervalVar* const v) const {
00814   return interval_var_container_.Element(v).EndValue();
00815 }
00816 
00817 int64 Assignment::PerformedMin(const IntervalVar* const v) const {
00818   return interval_var_container_.Element(v).PerformedMin();
00819 }
00820 
00821 int64 Assignment::PerformedMax(const IntervalVar* const v) const {
00822   return interval_var_container_.Element(v).PerformedMax();
00823 }
00824 
00825 int64 Assignment::PerformedValue(const IntervalVar* const v) const {
00826   return interval_var_container_.Element(v).PerformedValue();
00827 }
00828 
00829 void Assignment::SetStartMin(const IntervalVar* const v, int64 m) {
00830   interval_var_container_.MutableElement(v).SetStartMin(m);
00831 }
00832 
00833 void Assignment::SetStartMax(const IntervalVar* const v, int64 m) {
00834   interval_var_container_.MutableElement(v).SetStartMax(m);
00835 }
00836 
00837 void Assignment::SetStartRange(const IntervalVar* const v, int64 mi, int64 ma) {
00838   interval_var_container_.MutableElement(v).SetStartRange(mi, ma);
00839 }
00840 
00841 void Assignment::SetStartValue(const IntervalVar* const v, int64 value) {
00842   interval_var_container_.MutableElement(v).SetStartValue(value);
00843 }
00844 
00845 void Assignment::SetDurationMin(const IntervalVar* const v, int64 m) {
00846   interval_var_container_.MutableElement(v).SetDurationMin(m);
00847 }
00848 
00849 void Assignment::SetDurationMax(const IntervalVar* const v, int64 m) {
00850   interval_var_container_.MutableElement(v).SetDurationMax(m);
00851 }
00852 
00853 void Assignment::SetDurationRange(const IntervalVar* const v,
00854                                   int64 mi, int64 ma) {
00855   interval_var_container_.MutableElement(v).SetDurationRange(mi, ma);
00856 }
00857 
00858 void Assignment::SetDurationValue(const IntervalVar* const v, int64 value) {
00859   interval_var_container_.MutableElement(v).SetDurationValue(value);
00860 }
00861 
00862 void Assignment::SetEndMin(const IntervalVar* const v, int64 m) {
00863   interval_var_container_.MutableElement(v).SetEndMin(m);
00864 }
00865 
00866 void Assignment::SetEndMax(const IntervalVar* const v, int64 m) {
00867   interval_var_container_.MutableElement(v).SetEndMax(m);
00868 }
00869 
00870 void Assignment::SetEndRange(const IntervalVar* const v, int64 mi, int64 ma) {
00871   interval_var_container_.MutableElement(v).SetEndRange(mi, ma);
00872 }
00873 
00874 void Assignment::SetEndValue(const IntervalVar* const v, int64 value) {
00875   interval_var_container_.MutableElement(v).SetEndValue(value);
00876 }
00877 
00878 void Assignment::SetPerformedMin(const IntervalVar* const v, int64 m) {
00879   interval_var_container_.MutableElement(v).SetPerformedMin(m);
00880 }
00881 
00882 void Assignment::SetPerformedMax(const IntervalVar* const v, int64 m) {
00883   interval_var_container_.MutableElement(v).SetPerformedMax(m);
00884 }
00885 
00886 void Assignment::SetPerformedRange(const IntervalVar* const v,
00887                                    int64 mi, int64 ma) {
00888   interval_var_container_.MutableElement(v).SetPerformedRange(mi, ma);
00889 }
00890 
00891 void Assignment::SetPerformedValue(const IntervalVar* const v, int64 value) {
00892   interval_var_container_.MutableElement(v).SetPerformedValue(value);
00893 }
00894 
00895 // ----- Sequence Var -----
00896 
00897 SequenceVarElement& Assignment::Add(SequenceVar* const v) {
00898   return sequence_var_container_.Add(v);
00899 }
00900 
00901 void Assignment::Add(SequenceVar* const * vars, int size) {
00902   DCHECK_GE(size, 0);
00903   for (int i = 0; i < size; ++i) {
00904     Add(vars[i]);
00905   }
00906 }
00907 
00908 void Assignment::Add(const std::vector<SequenceVar*>& vars) {
00909   for (ConstIter<std::vector<SequenceVar*> > it(vars); !it.at_end(); ++it) {
00910     Add(*it);
00911   }
00912 }
00913 
00914 SequenceVarElement& Assignment::FastAdd(SequenceVar* const v) {
00915   return sequence_var_container_.FastAdd(v);
00916 }
00917 
00918 const std::vector<int>& Assignment::ForwardSequence(
00919     const SequenceVar* const v) const {
00920   return sequence_var_container_.Element(v).ForwardSequence();
00921 }
00922 
00923 const std::vector<int>& Assignment::BackwardSequence(
00924     const SequenceVar* const v) const {
00925   return sequence_var_container_.Element(v).BackwardSequence();
00926 }
00927 
00928 const std::vector<int>& Assignment::Unperformed(
00929     const SequenceVar* const v) const {
00930   return sequence_var_container_.Element(v).Unperformed();
00931 }
00932 
00933 void Assignment::SetSequence(const SequenceVar* const v,
00934                              const std::vector<int>& forward_sequence,
00935                              const std::vector<int>& backward_sequence,
00936                              const std::vector<int>& unperformed) {
00937   sequence_var_container_.MutableElement(v).SetSequence(forward_sequence,
00938                                                         backward_sequence,
00939                                                         unperformed);
00940 }
00941 
00942 void Assignment::SetForwardSequence(const SequenceVar* const v,
00943                                     const std::vector<int>& forward_sequence) {
00944   sequence_var_container_.MutableElement(v).SetForwardSequence(
00945       forward_sequence);
00946 }
00947 
00948 void Assignment::SetBackwardSequence(const SequenceVar* const v,
00949                                      const std::vector<int>& backward_sequence) {
00950   sequence_var_container_.MutableElement(v).SetBackwardSequence(
00951       backward_sequence);
00952 }
00953 
00954 void Assignment::SetUnperformed(const SequenceVar* const v,
00955                                 const std::vector<int>& unperformed) {
00956   sequence_var_container_.MutableElement(v).SetUnperformed(unperformed);
00957 }
00958 
00959 // ----- Objective -----
00960 
00961 void Assignment::AddObjective(IntVar* const v) {
00962   // Check if adding twice an objective to the solution.
00963   CHECK(!HasObjective());
00964   objective_element_.Reset(v);
00965 }
00966 
00967 IntVar* Assignment::Objective() const {
00968   return objective_element_.Var();
00969 }
00970 
00971 int64 Assignment::ObjectiveMin() const {
00972   if (HasObjective()) {
00973     return objective_element_.Min();
00974   }
00975   return 0;
00976 }
00977 
00978 int64 Assignment::ObjectiveMax() const {
00979   if (HasObjective()) {
00980     return objective_element_.Max();
00981   }
00982   return 0;
00983 }
00984 
00985 int64 Assignment::ObjectiveValue() const {
00986   if (HasObjective()) {
00987     return objective_element_.Value();
00988   }
00989   return 0;
00990 }
00991 
00992 bool Assignment::ObjectiveBound() const {
00993   if (HasObjective()) {
00994     return objective_element_.Bound();
00995   }
00996   return true;
00997 }
00998 
00999 void Assignment::SetObjectiveMin(int64 m) {
01000   if (HasObjective()) {
01001     objective_element_.SetMin(m);
01002   }
01003 }
01004 
01005 void Assignment::SetObjectiveMax(int64 m) {
01006   if (HasObjective()) {
01007     objective_element_.SetMax(m);
01008   }
01009 }
01010 
01011 void Assignment::SetObjectiveRange(int64 l, int64 u) {
01012   if (HasObjective()) {
01013     objective_element_.SetRange(l, u);
01014   }
01015 }
01016 
01017 void Assignment::SetObjectiveValue(int64 value) {
01018   if (HasObjective()) {
01019     objective_element_.SetValue(value);
01020   }
01021 }
01022 
01023 void Assignment::Activate(const IntVar* const b) {
01024   int_var_container_.MutableElement(b).Activate();
01025 }
01026 
01027 void Assignment::Deactivate(const IntVar* const b) {
01028   int_var_container_.MutableElement(b).Deactivate();
01029 }
01030 
01031 bool Assignment::Activated(const IntVar* const b) const {
01032   return int_var_container_.Element(b).Activated();
01033 }
01034 
01035 void Assignment::Activate(const IntervalVar* const b) {
01036   interval_var_container_.MutableElement(b).Activate();
01037 }
01038 
01039 void Assignment::Deactivate(const IntervalVar* const b) {
01040   interval_var_container_.MutableElement(b).Deactivate();
01041 }
01042 
01043 bool Assignment::Activated(const IntervalVar* const b) const {
01044   return interval_var_container_.Element(b).Activated();
01045 }
01046 
01047 void Assignment::Activate(const SequenceVar* const b) {
01048   sequence_var_container_.MutableElement(b).Activate();
01049 }
01050 
01051 void Assignment::Deactivate(const SequenceVar* const b) {
01052   sequence_var_container_.MutableElement(b).Deactivate();
01053 }
01054 
01055 bool Assignment::Activated(const SequenceVar* const b) const {
01056   return sequence_var_container_.Element(b).Activated();
01057 }
01058 
01059 void Assignment::ActivateObjective() {
01060   if (HasObjective()) {
01061     objective_element_.Activate();
01062   }
01063 }
01064 
01065 void Assignment::DeactivateObjective() {
01066   if (HasObjective()) {
01067     objective_element_.Deactivate();
01068   }
01069 }
01070 
01071 bool Assignment::ActivatedObjective() const {
01072   if (HasObjective()) {
01073     return objective_element_.Activated();
01074   }
01075   return true;
01076 }
01077 
01078 bool Assignment::Contains(const IntVar* const var) const {
01079   return int_var_container_.Contains(var);
01080 }
01081 
01082 bool Assignment::Contains(const IntervalVar* const var) const {
01083   return interval_var_container_.Contains(var);
01084 }
01085 
01086 bool Assignment::Contains(const SequenceVar* const var) const {
01087   return sequence_var_container_.Contains(var);
01088 }
01089 
01090 void Assignment::Copy(const Assignment* assignment) {
01091   int_var_container_.Copy(assignment->int_var_container_);
01092   interval_var_container_.Copy(assignment->interval_var_container_);
01093   sequence_var_container_.Copy(assignment->sequence_var_container_);
01094   objective_element_ = assignment->objective_element_;
01095 }
01096 
01097 Assignment* Solver::MakeAssignment() {
01098   return RevAlloc(new Assignment(this));
01099 }
01100 
01101 Assignment* Solver::MakeAssignment(const Assignment* const a) {
01102   return RevAlloc(new Assignment(a));
01103 }
01104 
01105 // ----- Storing and Restoring assignments -----
01106 namespace {
01107 class RestoreAssignment : public DecisionBuilder {
01108  public:
01109   explicit RestoreAssignment(Assignment* assignment)
01110       : assignment_(assignment) {}
01111 
01112   virtual ~RestoreAssignment() {}
01113 
01114   virtual Decision* Next(Solver* const solver) {
01115     assignment_->Restore();
01116     return NULL;
01117   }
01118 
01119   virtual string DebugString() const {
01120     return "RestoreAssignment";
01121   }
01122 
01123  private:
01124   Assignment* const assignment_;
01125 };
01126 
01127 class StoreAssignment : public DecisionBuilder {
01128  public:
01129   explicit StoreAssignment(Assignment* assignment) : assignment_(assignment) {}
01130 
01131   virtual ~StoreAssignment() {}
01132 
01133   virtual Decision* Next(Solver* const solver)  {
01134     assignment_->Store();
01135     return NULL;
01136   }
01137 
01138   virtual string DebugString() const {
01139     return "StoreAssignment";
01140   }
01141 
01142  private:
01143   Assignment* const assignment_;
01144 };
01145 }  // namespace
01146 
01147 DecisionBuilder* Solver::MakeRestoreAssignment(Assignment* assignment) {
01148   return RevAlloc(new RestoreAssignment(assignment));
01149 }
01150 
01151 DecisionBuilder* Solver::MakeStoreAssignment(Assignment* assignment) {
01152   return RevAlloc(new StoreAssignment(assignment));
01153 }
01154 
01155 std::ostream& operator<<(std::ostream& out, const Assignment& assignment) {
01156   return out << assignment.DebugString();
01157 }
01158 
01159 }  // namespace operations_research