Generated on Fri Oct 19 11:24:48 2018 for Gecode by doxygen 1.6.3

crew.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Guido Tack, 2004
00009  *     Christian Schulte, 2004
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 
00037 #include <gecode/driver.hh>
00038 #include <gecode/int.hh>
00039 #include <gecode/set.hh>
00040 
00041 using namespace Gecode;
00042 
00043 namespace {
00045   typedef enum {
00046     Tom, David, Jeremy, Ron,
00047     Joe, Bill, Fred,
00048     Bob, Mario, Ed,
00049     Carol, Janet, Tracy,
00050     Marilyn, Carolyn, Cathy,
00051     Inez, Jean, Heather, Juliet
00052   } Employee;
00053   const int noOfEmployees = Juliet+1;
00054 
00056   struct Flight {
00057     int staff;     
00058     int stewards;  
00059     int hostesses; 
00060     int french;    
00061     int spanish;   
00062     int german;    
00063   };
00064 
00065   const char* employeeToName(Employee e);
00066   extern const int stewards[];
00067   extern const int noOfStewards;
00068   extern const int hostesses[];
00069   extern const int noOfHostesses;
00070   extern const int spanishSpeaking[];
00071   extern const int noOfSpanishSpeaking;
00072   extern const int frenchSpeaking[];
00073   extern const int noOfFrenchSpeaking;
00074   extern const int germanSpeaking[];
00075   extern const int noOfGermanSpeaking;
00076   extern const Flight requiredCrew[];
00077   extern const int noOfFlights;
00078 }
00079 
00090 class Crew : public Script {
00091 public:
00093   SetVarArray flight;
00094 
00096   Crew(const Options& opt)
00097     : Script(opt), flight(*this,noOfFlights,IntSet::empty,0,noOfEmployees-1) {
00098     IntSet stewardsDS(stewards,noOfStewards);
00099     IntSet hostessesDS(hostesses,noOfHostesses);
00100     IntSet spanishDS(spanishSpeaking, noOfSpanishSpeaking);
00101     IntSet frenchDS(frenchSpeaking, noOfFrenchSpeaking);
00102     IntSet germanDS(germanSpeaking, noOfGermanSpeaking);
00103 
00104     for (int i=0; i<noOfFlights; i++) {
00105       // The flight has staff as required by the specification
00106       rel(*this, cardinality(flight[i]) == requiredCrew[i].staff);
00107 
00108       // Enough members of different categories are on board
00109       rel(*this, cardinality(flight[i] & stewardsDS) >=
00110           requiredCrew[i].stewards);
00111       rel(*this, cardinality(flight[i] & hostessesDS) >=
00112           requiredCrew[i].hostesses);
00113       rel(*this, cardinality(flight[i] & spanishDS) >=
00114           requiredCrew[i].spanish);
00115       rel(*this, cardinality(flight[i] & frenchDS) >=
00116           requiredCrew[i].french);
00117       rel(*this, cardinality(flight[i] & germanDS) >=
00118           requiredCrew[i].german);
00119     }
00120 
00121     // No crew member of flight i works on flights i+1 and i+2
00122     for (int i=0; i<noOfFlights-2; i++) {
00123       rel(*this, flight[i] || flight[i+1]);
00124       rel(*this, flight[i] || flight[i+2]);
00125     }
00126     rel(*this, flight[noOfFlights-2] || flight[noOfFlights-1]);
00127 
00128     branch(*this, flight, SET_VAR_NONE(), SET_VAL_MIN_INC());
00129   }
00130 
00132   virtual void
00133   print(std::ostream& os) const {
00134     for (int i=0; i<noOfFlights; i++) {
00135       os << "\tFlight " << i+1 << ":" << std::endl;
00136       os << "\t\tCrew\tStew.\tHost.\tFrench\tSpanish\tGerman"
00137          << std::endl << "\t";
00138       os << "\t" << requiredCrew[i].staff << "\t" << requiredCrew[i].stewards
00139          << "\t" << requiredCrew[i].hostesses << "\t"
00140          << requiredCrew[i].spanish
00141          << "\t" << requiredCrew[i].french << "\t" << requiredCrew[i].german
00142          << std::endl;
00143 
00144       os << "\t\tSchedule:" << std::endl << "\t\t";
00145       if (flight[i].assigned()) {
00146         for (SetVarGlbValues d(flight[i]);d();++d) {
00147           os << employeeToName(static_cast<Employee>(d.val())) << " ";
00148         }
00149       } else {
00150         os << "\tRequired: ";
00151         for (SetVarGlbValues d(flight[i]);d();++d) {
00152           os << employeeToName(static_cast<Employee>(d.val())) << " ";
00153         }
00154         os << std::endl << "\t\t\tPossible: ";
00155         for (SetVarUnknownValues d(flight[i]);d();++d) {
00156           os << employeeToName(static_cast<Employee>(d.val())) << " ";
00157         }
00158       }
00159       os << std::endl << std::endl;
00160     }
00161   }
00162 
00164   Crew(Crew& s)
00165     : Script(s) {
00166     flight.update(*this, s.flight);
00167   }
00169   virtual
00170   Space *copy(void) {
00171     return new Crew(*this);
00172   }
00173 
00174 };
00175 
00179 int
00180 main(int argc, char* argv[]) {
00181   Options o("Crew");
00182   o.iterations(100);
00183   o.parse(argc,argv);
00184   Script::run<Crew,DFS,Options>(o);
00185   return 0;
00186 }
00187 
00188 namespace {
00189 
00191   const char*
00192   employeeToName(Employee e) {
00193     switch(e) {
00194     case Tom : return "Tom";
00195     case David : return "David";
00196     case Jeremy: return "Jeremy";
00197     case Ron: return "Ron";
00198     case Joe: return "Joe";
00199     case Bill: return "Bill";
00200     case Fred: return "Fred";
00201     case Bob: return "Bob";
00202     case Mario: return "Mario";
00203     case Ed: return "Ed";
00204     case Carol: return "Carol";
00205     case Janet: return "Janet";
00206     case Tracy: return "Tracy";
00207     case Marilyn: return "Marilyn";
00208     case Carolyn: return "Carolyn";
00209     case Cathy: return "Cathy";
00210     case Inez: return "Inez";
00211     case Jean: return "Jean";
00212     case Heather: return "Heather";
00213     case Juliet: return "Juliet";
00214     default: GECODE_NEVER; return "";
00215     }
00216   }
00217 
00218   // these have to be sorted!
00220   const int stewards[] =
00221     {Tom, David, Jeremy, Ron, Joe, Bill, Fred, Bob, Mario, Ed};
00223   const int noOfStewards = sizeof(stewards) / sizeof(int);
00225   const int hostesses[] =
00226     { Carol, Janet, Tracy, Marilyn, Carolyn, Cathy, Inez,
00227       Jean, Heather, Juliet };
00229   const int noOfHostesses = sizeof(hostesses) / sizeof(int);
00231   const int frenchSpeaking[] =
00232     { Bill, Inez, Jean, Juliet };
00234   const int noOfFrenchSpeaking = sizeof(frenchSpeaking) / sizeof(int);
00236   const int germanSpeaking[] =
00237     { Tom, Jeremy, Mario, Cathy, Juliet };
00239   const int noOfGermanSpeaking = sizeof(germanSpeaking) / sizeof(int);
00241   const int spanishSpeaking[] =
00242     { Joe, Bill, Fred, Mario, Marilyn, Inez, Heather };
00244   const int noOfSpanishSpeaking = sizeof(spanishSpeaking) / sizeof(int);
00245 
00247   const Flight requiredCrew[] =
00248     { {4,1,1,1,1,1},
00249       {5,1,1,1,1,1},
00250       {5,1,1,1,1,1},
00251       {6,2,2,1,1,1},
00252       {7,3,3,1,1,1},
00253       {4,1,1,1,1,1},
00254       {5,1,1,1,1,1},
00255       {6,1,1,1,1,1},
00256       {6,2,2,1,1,1},
00257       {7,3,3,1,1,1} };
00258 
00260   const int noOfFlights = sizeof(requiredCrew) / sizeof(Flight);
00261 }
00262 
00263 // STATISTICS: example-any
00264