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: 2010-05-08 19:24:20 +0200 (Sat, 08 May 2010) $ by $Author: tack $ 00013 * $Revision: 10910 $ 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 // The flight has staff as required by the specification 00111 rel(*this, cardinality(flight[i]) == requiredCrew[i].staff); 00112 00113 // Enough members of different categories are on board 00114 rel(*this, cardinality(flight[i] & stewardsDS) >= 00115 requiredCrew[i].stewards); 00116 rel(*this, cardinality(flight[i] & hostessesDS) >= 00117 requiredCrew[i].hostesses); 00118 rel(*this, cardinality(flight[i] & spanishDS) >= 00119 requiredCrew[i].spanish); 00120 rel(*this, cardinality(flight[i] & frenchDS) >= 00121 requiredCrew[i].french); 00122 rel(*this, cardinality(flight[i] & germanDS) >= 00123 requiredCrew[i].german); 00124 } 00125 00126 // No crew member of flight i works on flights i+1 and i+2 00127 for (int i=0; i<noOfFlights-2; i++) { 00128 rel(*this, flight[i] || flight[i+1]); 00129 rel(*this, flight[i] || flight[i+2]); 00130 } 00131 rel(*this, flight[noOfFlights-2] || flight[noOfFlights-1]); 00132 00133 branch(*this, flight, SET_VAR_NONE, SET_VAL_MIN_INC); 00134 } 00135 00137 virtual void 00138 print(std::ostream& os) const { 00139 for (int i=0; i<noOfFlights; i++) { 00140 os << "\tFlight " << i+1 << ":" << std::endl; 00141 os << "\t\tCrew\tStew.\tHost.\tFrench\tSpanish\tGerman" 00142 << std::endl << "\t"; 00143 os << "\t" << requiredCrew[i].staff << "\t" << requiredCrew[i].stewards 00144 << "\t" << requiredCrew[i].hostesses << "\t" 00145 << requiredCrew[i].spanish 00146 << "\t" << requiredCrew[i].french << "\t" << requiredCrew[i].german 00147 << std::endl; 00148 00149 os << "\t\tSchedule:" << std::endl << "\t\t"; 00150 if (flight[i].assigned()) { 00151 for (SetVarGlbValues d(flight[i]);d();++d) { 00152 os << employeeToName(static_cast<Employee>(d.val())) << " "; 00153 } 00154 } else { 00155 os << "\tRequired: "; 00156 for (SetVarGlbValues d(flight[i]);d();++d) { 00157 os << employeeToName(static_cast<Employee>(d.val())) << " "; 00158 } 00159 os << std::endl << "\t\t\tPossible: "; 00160 for (SetVarUnknownValues d(flight[i]);d();++d) { 00161 os << employeeToName(static_cast<Employee>(d.val())) << " "; 00162 } 00163 } 00164 os << std::endl << std::endl; 00165 } 00166 } 00167 00169 Crew(bool share, Crew& s) 00170 : Script(share,s) { 00171 flight.update(*this,share,s.flight); 00172 } 00174 virtual 00175 Space *copy(bool share) { 00176 return new Crew(share,*this); 00177 } 00178 00179 }; 00180 00184 int 00185 main(int argc, char* argv[]) { 00186 Options o("Crew"); 00187 o.iterations(100); 00188 o.parse(argc,argv); 00189 Script::run<Crew,DFS,Options>(o); 00190 return 0; 00191 } 00192 00193 namespace { 00194 00196 const char* 00197 employeeToName(Employee e) { 00198 switch(e) { 00199 case Tom : return "Tom"; 00200 case David : return "David"; 00201 case Jeremy: return "Jeremy"; 00202 case Ron: return "Ron"; 00203 case Joe: return "Joe"; 00204 case Bill: return "Bill"; 00205 case Fred: return "Fred"; 00206 case Bob: return "Bob"; 00207 case Mario: return "Mario"; 00208 case Ed: return "Ed"; 00209 case Carol: return "Carol"; 00210 case Janet: return "Janet"; 00211 case Tracy: return "Tracy"; 00212 case Marilyn: return "Marilyn"; 00213 case Carolyn: return "Carolyn"; 00214 case Cathy: return "Cathy"; 00215 case Inez: return "Inez"; 00216 case Jean: return "Jean"; 00217 case Heather: return "Heather"; 00218 case Juliet: return "Juliet"; 00219 default: GECODE_NEVER; return ""; 00220 } 00221 } 00222 00223 // these have to be sorted! 00225 const int stewards[] = 00226 {Tom, David, Jeremy, Ron, Joe, Bill, Fred, Bob, Mario, Ed}; 00228 const int noOfStewards = sizeof(stewards) / sizeof(int); 00230 const int hostesses[] = 00231 { Carol, Janet, Tracy, Marilyn, Carolyn, Cathy, Inez, 00232 Jean, Heather, Juliet }; 00234 const int noOfHostesses = sizeof(hostesses) / sizeof(int); 00236 const int frenchSpeaking[] = 00237 { Bill, Inez, Jean, Juliet }; 00239 const int noOfFrenchSpeaking = sizeof(frenchSpeaking) / sizeof(int); 00241 const int germanSpeaking[] = 00242 { Tom, Jeremy, Mario, Cathy, Juliet }; 00244 const int noOfGermanSpeaking = sizeof(germanSpeaking) / sizeof(int); 00246 const int spanishSpeaking[] = 00247 { Joe, Bill, Fred, Mario, Marilyn, Inez, Heather }; 00249 const int noOfSpanishSpeaking = sizeof(spanishSpeaking) / sizeof(int); 00250 00252 const Flight requiredCrew[] = 00253 { {4,1,1,1,1,1}, 00254 {5,1,1,1,1,1}, 00255 {5,1,1,1,1,1}, 00256 {6,2,2,1,1,1}, 00257 {7,3,3,1,1,1}, 00258 {4,1,1,1,1,1}, 00259 {5,1,1,1,1,1}, 00260 {6,1,1,1,1,1}, 00261 {6,2,2,1,1,1}, 00262 {7,3,3,1,1,1} }; 00263 00265 const int noOfFlights = sizeof(requiredCrew) / sizeof(Flight); 00266 } 00267 00268 // STATISTICS: example-any 00269