Generated on Mon Nov 30 23:53:17 2009 for Gecode by doxygen 1.6.1

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  *  Last modified:
00012  *     $Date: 2009-04-02 20:58:46 +0200 (Thu, 02 Apr 2009) $ by $Author: schulte $
00013  *     $Revision: 8649 $
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 
00041 #include <gecode/driver.hh>
00042 #include <gecode/int.hh>
00043 #include <gecode/set.hh>
00044 
00045 using namespace Gecode;
00046 
00047 namespace {
00049   typedef enum {
00050     Tom, David, Jeremy, Ron,
00051     Joe, Bill, Fred,
00052     Bob, Mario, Ed,
00053     Carol, Janet, Tracy,
00054     Marilyn, Carolyn, Cathy,
00055     Inez, Jean, Heather, Juliet
00056   } Employee;
00057   const int noOfEmployees = Juliet+1;
00058 
00060   struct Flight {
00061     int staff;     
00062     int stewards;  
00063     int hostesses; 
00064     int french;    
00065     int spanish;   
00066     int german;    
00067   };
00068 
00069   const char* employeeToName(Employee e);
00070   extern const int stewards[];
00071   extern const int noOfStewards;
00072   extern const int hostesses[];
00073   extern const int noOfHostesses;
00074   extern const int spanishSpeaking[];
00075   extern const int noOfSpanishSpeaking;
00076   extern const int frenchSpeaking[];
00077   extern const int noOfFrenchSpeaking;
00078   extern const int germanSpeaking[];
00079   extern const int noOfGermanSpeaking;
00080   extern const Flight requiredCrew[];
00081   extern const int noOfFlights;
00082 }
00083 
00094 class Crew : public Script {
00095 public:
00097   SetVarArray flight;
00098 
00100   Crew(const Options&) :
00101     flight(*this,noOfFlights,IntSet::empty,0,noOfEmployees-1)
00102   {
00103     IntSet stewardsDS(stewards,noOfStewards);
00104     IntSet hostessesDS(hostesses,noOfHostesses);
00105     IntSet spanishDS(spanishSpeaking, noOfSpanishSpeaking);
00106     IntSet frenchDS(frenchSpeaking, noOfFrenchSpeaking);
00107     IntSet germanDS(germanSpeaking, noOfGermanSpeaking);
00108 
00109     for (int i=0; i<noOfFlights; i++) {
00110       IntVarArray required(*this,5,0,noOfEmployees-1);
00111       SetVar team = flight[i];
00112 
00113       int N        = requiredCrew[i].staff;
00114       int NStew    = requiredCrew[i].stewards;
00115       int NHost    = requiredCrew[i].hostesses;
00116       int NFrench  = requiredCrew[i].french;
00117       int NSpanish = requiredCrew[i].spanish;
00118       int NGerman  = requiredCrew[i].german;
00119 
00120       // The team has N members (as required by the specification)
00121       cardinality(*this, team,N,N);
00122 
00123       // Make sure that enough team members of different categories are on board
00124 
00125       SetVar stewardsInTeam(*this);
00126       rel(*this, team, SOT_INTER, stewardsDS, SRT_EQ, stewardsInTeam);
00127       cardinality(*this, stewardsInTeam, required[0]);
00128       rel(*this, required[0], IRT_GQ, NStew);
00129 
00130       SetVar hostessesInTeam(*this);
00131       rel(*this, team, SOT_INTER, hostessesDS, SRT_EQ, hostessesInTeam);
00132       cardinality(*this, hostessesInTeam, required[1]);
00133       rel(*this, required[1], IRT_GQ, NHost);
00134 
00135       SetVar spanishInTeam(*this);
00136       rel(*this, team, SOT_INTER, spanishDS, SRT_EQ, spanishInTeam);
00137       cardinality(*this, spanishInTeam, required[2]);
00138       rel(*this, required[2], IRT_GQ, NSpanish);
00139 
00140       SetVar frenchInTeam(*this);
00141       rel(*this, team, SOT_INTER, frenchDS, SRT_EQ, frenchInTeam);
00142       cardinality(*this, frenchInTeam, required[3]);
00143       rel(*this, required[3], IRT_GQ, NFrench);
00144 
00145       SetVar germanInTeam(*this);
00146       rel(*this, team, SOT_INTER, germanDS, SRT_EQ, germanInTeam);
00147       cardinality(*this, germanInTeam, required[4]);
00148       rel(*this, required[4], IRT_GQ, NGerman);
00149 
00150     }
00151 
00152     // No crew member of flight i works on flights i+1 and i+2
00153     for (int i=0; i<noOfFlights-2; i++) {
00154       rel(*this, flight[i], SRT_DISJ, flight[i+1]);
00155       rel(*this, flight[i], SRT_DISJ, flight[i+2]);
00156     }
00157     rel(*this, flight[noOfFlights-2], SRT_DISJ, flight[noOfFlights-1]);
00158 
00159     branch(*this, flight, SET_VAR_NONE, SET_VAL_MIN_INC);
00160   }
00161 
00163   virtual void
00164   print(std::ostream& os) const {
00165     for (int i=0; i<noOfFlights; i++) {
00166       os << "\tFlight " << i+1 << ":" << std::endl;
00167       os << "\t\tCrew\tStew.\tHost.\tFrench\tSpanish\tGerman"
00168          << std::endl << "\t";
00169       os << "\t" << requiredCrew[i].staff << "\t" << requiredCrew[i].stewards
00170          << "\t" << requiredCrew[i].hostesses << "\t"
00171          << requiredCrew[i].spanish
00172          << "\t" << requiredCrew[i].french << "\t" << requiredCrew[i].german
00173          << std::endl;
00174 
00175       os << "\t\tSchedule:" << std::endl << "\t\t";
00176       if (flight[i].assigned()) {
00177         for (SetVarGlbValues d(flight[i]);d();++d) {
00178           os << employeeToName(static_cast<Employee>(d.val())) << " ";
00179         }
00180       } else {
00181         os << "\tRequired: ";
00182         for (SetVarGlbValues d(flight[i]);d();++d) {
00183           os << employeeToName(static_cast<Employee>(d.val())) << " ";
00184         }
00185         os << std::endl << "\t\t\tPossible: ";
00186         for (SetVarUnknownValues d(flight[i]);d();++d) {
00187           os << employeeToName(static_cast<Employee>(d.val())) << " ";
00188         }
00189       }
00190       os << std::endl << std::endl;
00191     }
00192   }
00193 
00195   Crew(bool share, Crew& s)
00196     : Script(share,s) {
00197     flight.update(*this,share,s.flight);
00198   }
00200   virtual
00201   Space *copy(bool share) {
00202     return new Crew(share,*this);
00203   }
00204 
00205 };
00206 
00210 int
00211 main(int argc, char* argv[]) {
00212   Options o("Crew");
00213   o.iterations(100);
00214   o.parse(argc,argv);
00215   Script::run<Crew,DFS,Options>(o);
00216   return 0;
00217 }
00218 
00219 namespace {
00220 
00222   const char*
00223   employeeToName(Employee e) {
00224     switch(e) {
00225     case Tom : return "Tom";
00226     case David : return "David";
00227     case Jeremy: return "Jeremy";
00228     case Ron: return "Ron";
00229     case Joe: return "Joe";
00230     case Bill: return "Bill";
00231     case Fred: return "Fred";
00232     case Bob: return "Bob";
00233     case Mario: return "Mario";
00234     case Ed: return "Ed";
00235     case Carol: return "Carol";
00236     case Janet: return "Janet";
00237     case Tracy: return "Tracy";
00238     case Marilyn: return "Marilyn";
00239     case Carolyn: return "Carolyn";
00240     case Cathy: return "Cathy";
00241     case Inez: return "Inez";
00242     case Jean: return "Jean";
00243     case Heather: return "Heather";
00244     case Juliet: return "Juliet";
00245     default: GECODE_NEVER; return "";
00246     }
00247   }
00248 
00249   // these have to be sorted!
00251   const int stewards[] =
00252     {Tom, David, Jeremy, Ron, Joe, Bill, Fred, Bob, Mario, Ed};
00254   const int noOfStewards = sizeof(stewards) / sizeof(int);
00256   const int hostesses[] =
00257     { Carol, Janet, Tracy, Marilyn, Carolyn, Cathy, Inez,
00258       Jean, Heather, Juliet };
00260   const int noOfHostesses = sizeof(hostesses) / sizeof(int);
00262   const int frenchSpeaking[] =
00263     { Bill, Inez, Jean, Juliet };
00265   const int noOfFrenchSpeaking = sizeof(frenchSpeaking) / sizeof(int);
00267   const int germanSpeaking[] =
00268     { Tom, Jeremy, Mario, Cathy, Juliet };
00270   const int noOfGermanSpeaking = sizeof(germanSpeaking) / sizeof(int);
00272   const int spanishSpeaking[] =
00273     { Joe, Bill, Fred, Mario, Marilyn, Inez, Heather };
00275   const int noOfSpanishSpeaking = sizeof(spanishSpeaking) / sizeof(int);
00276 
00278   const Flight requiredCrew[] =
00279     { {4,1,1,1,1,1},
00280       {5,1,1,1,1,1},
00281       {5,1,1,1,1,1},
00282       {6,2,2,1,1,1},
00283       {7,3,3,1,1,1},
00284       {4,1,1,1,1,1},
00285       {5,1,1,1,1,1},
00286       {6,1,1,1,1,1},
00287       {6,2,2,1,1,1},
00288       {7,3,3,1,1,1} };
00289 
00291   const int noOfFlights = sizeof(requiredCrew) / sizeof(Flight);
00292 }
00293 
00294 // STATISTICS: example-any
00295