Generated on Fri Mar 20 15:55:53 2015 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  *  Last modified:
00012  *     $Date: 2015-03-17 16:09:39 +0100 (Tue, 17 Mar 2015) $ by $Author: schulte $
00013  *     $Revision: 14447 $
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& opt) 
00101     : Script(opt), flight(*this,noOfFlights,IntSet::empty,0,noOfEmployees-1) {
00102     IntSet stewardsDS(stewards,noOfStewards);
00103     IntSet hostessesDS(hostesses,noOfHostesses);
00104     IntSet spanishDS(spanishSpeaking, noOfSpanishSpeaking);
00105     IntSet frenchDS(frenchSpeaking, noOfFrenchSpeaking);
00106     IntSet germanDS(germanSpeaking, noOfGermanSpeaking);
00107 
00108     for (int i=0; i<noOfFlights; i++) {
00109       // The flight has staff as required by the specification
00110       rel(*this, cardinality(flight[i]) == requiredCrew[i].staff);
00111 
00112       // Enough members of different categories are on board
00113       rel(*this, cardinality(flight[i] & stewardsDS) >= 
00114           requiredCrew[i].stewards);
00115       rel(*this, cardinality(flight[i] & hostessesDS) >=
00116           requiredCrew[i].hostesses);
00117       rel(*this, cardinality(flight[i] & spanishDS) >=
00118           requiredCrew[i].spanish);
00119       rel(*this, cardinality(flight[i] & frenchDS) >=
00120           requiredCrew[i].french);
00121       rel(*this, cardinality(flight[i] & germanDS) >=
00122           requiredCrew[i].german);
00123     }
00124 
00125     // No crew member of flight i works on flights i+1 and i+2
00126     for (int i=0; i<noOfFlights-2; i++) {
00127       rel(*this, flight[i] || flight[i+1]);
00128       rel(*this, flight[i] || flight[i+2]);
00129     }
00130     rel(*this, flight[noOfFlights-2] || flight[noOfFlights-1]);
00131 
00132     branch(*this, flight, SET_VAR_NONE(), SET_VAL_MIN_INC());
00133   }
00134 
00136   virtual void
00137   print(std::ostream& os) const {
00138     for (int i=0; i<noOfFlights; i++) {
00139       os << "\tFlight " << i+1 << ":" << std::endl;
00140       os << "\t\tCrew\tStew.\tHost.\tFrench\tSpanish\tGerman"
00141          << std::endl << "\t";
00142       os << "\t" << requiredCrew[i].staff << "\t" << requiredCrew[i].stewards
00143          << "\t" << requiredCrew[i].hostesses << "\t"
00144          << requiredCrew[i].spanish
00145          << "\t" << requiredCrew[i].french << "\t" << requiredCrew[i].german
00146          << std::endl;
00147 
00148       os << "\t\tSchedule:" << std::endl << "\t\t";
00149       if (flight[i].assigned()) {
00150         for (SetVarGlbValues d(flight[i]);d();++d) {
00151           os << employeeToName(static_cast<Employee>(d.val())) << " ";
00152         }
00153       } else {
00154         os << "\tRequired: ";
00155         for (SetVarGlbValues d(flight[i]);d();++d) {
00156           os << employeeToName(static_cast<Employee>(d.val())) << " ";
00157         }
00158         os << std::endl << "\t\t\tPossible: ";
00159         for (SetVarUnknownValues d(flight[i]);d();++d) {
00160           os << employeeToName(static_cast<Employee>(d.val())) << " ";
00161         }
00162       }
00163       os << std::endl << std::endl;
00164     }
00165   }
00166 
00168   Crew(bool share, Crew& s)
00169     : Script(share,s) {
00170     flight.update(*this,share,s.flight);
00171   }
00173   virtual
00174   Space *copy(bool share) {
00175     return new Crew(share,*this);
00176   }
00177 
00178 };
00179 
00183 int
00184 main(int argc, char* argv[]) {
00185   Options o("Crew");
00186   o.iterations(100);
00187   o.parse(argc,argv);
00188   Script::run<Crew,DFS,Options>(o);
00189   return 0;
00190 }
00191 
00192 namespace {
00193 
00195   const char*
00196   employeeToName(Employee e) {
00197     switch(e) {
00198     case Tom : return "Tom";
00199     case David : return "David";
00200     case Jeremy: return "Jeremy";
00201     case Ron: return "Ron";
00202     case Joe: return "Joe";
00203     case Bill: return "Bill";
00204     case Fred: return "Fred";
00205     case Bob: return "Bob";
00206     case Mario: return "Mario";
00207     case Ed: return "Ed";
00208     case Carol: return "Carol";
00209     case Janet: return "Janet";
00210     case Tracy: return "Tracy";
00211     case Marilyn: return "Marilyn";
00212     case Carolyn: return "Carolyn";
00213     case Cathy: return "Cathy";
00214     case Inez: return "Inez";
00215     case Jean: return "Jean";
00216     case Heather: return "Heather";
00217     case Juliet: return "Juliet";
00218     default: GECODE_NEVER; return "";
00219     }
00220   }
00221 
00222   // these have to be sorted!
00224   const int stewards[] =
00225     {Tom, David, Jeremy, Ron, Joe, Bill, Fred, Bob, Mario, Ed};
00227   const int noOfStewards = sizeof(stewards) / sizeof(int);
00229   const int hostesses[] =
00230     { Carol, Janet, Tracy, Marilyn, Carolyn, Cathy, Inez,
00231       Jean, Heather, Juliet };
00233   const int noOfHostesses = sizeof(hostesses) / sizeof(int);
00235   const int frenchSpeaking[] =
00236     { Bill, Inez, Jean, Juliet };
00238   const int noOfFrenchSpeaking = sizeof(frenchSpeaking) / sizeof(int);
00240   const int germanSpeaking[] =
00241     { Tom, Jeremy, Mario, Cathy, Juliet };
00243   const int noOfGermanSpeaking = sizeof(germanSpeaking) / sizeof(int);
00245   const int spanishSpeaking[] =
00246     { Joe, Bill, Fred, Mario, Marilyn, Inez, Heather };
00248   const int noOfSpanishSpeaking = sizeof(spanishSpeaking) / sizeof(int);
00249 
00251   const Flight requiredCrew[] =
00252     { {4,1,1,1,1,1},
00253       {5,1,1,1,1,1},
00254       {5,1,1,1,1,1},
00255       {6,2,2,1,1,1},
00256       {7,3,3,1,1,1},
00257       {4,1,1,1,1,1},
00258       {5,1,1,1,1,1},
00259       {6,1,1,1,1,1},
00260       {6,2,2,1,1,1},
00261       {7,3,3,1,1,1} };
00262 
00264   const int noOfFlights = sizeof(requiredCrew) / sizeof(Flight);
00265 }
00266 
00267 // STATISTICS: example-any
00268