Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
crew.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 * Christian Schulte <schulte@gecode.org>
6 *
7 * Copyright:
8 * Guido Tack, 2004
9 * Christian Schulte, 2004
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36
37#include <gecode/driver.hh>
38#include <gecode/int.hh>
39#include <gecode/set.hh>
40
41using namespace Gecode;
42
43namespace {
45 typedef enum {
46 Tom, David, Jeremy, Ron,
47 Joe, Bill, Fred,
48 Bob, Mario, Ed,
49 Carol, Janet, Tracy,
50 Marilyn, Carolyn, Cathy,
51 Inez, Jean, Heather, Juliet
52 } Employee;
53 const int noOfEmployees = Juliet+1;
54
56 struct Flight {
57 int staff;
58 int stewards;
59 int hostesses;
60 int french;
61 int spanish;
62 int german;
63 };
64
65 const char* employeeToName(Employee e);
66 extern const int stewards[];
67 extern const int noOfStewards;
68 extern const int hostesses[];
69 extern const int noOfHostesses;
70 extern const int spanishSpeaking[];
71 extern const int noOfSpanishSpeaking;
72 extern const int frenchSpeaking[];
73 extern const int noOfFrenchSpeaking;
74 extern const int germanSpeaking[];
75 extern const int noOfGermanSpeaking;
76 extern const Flight requiredCrew[];
77 extern const int noOfFlights;
78}
79
90class Crew : public Script {
91public:
94
96 Crew(const Options& opt)
97 : Script(opt), flight(*this,noOfFlights,IntSet::empty,0,noOfEmployees-1) {
98 IntSet stewardsDS(stewards,noOfStewards);
99 IntSet hostessesDS(hostesses,noOfHostesses);
100 IntSet spanishDS(spanishSpeaking, noOfSpanishSpeaking);
101 IntSet frenchDS(frenchSpeaking, noOfFrenchSpeaking);
102 IntSet germanDS(germanSpeaking, noOfGermanSpeaking);
103
104 for (int i=0; i<noOfFlights; i++) {
105 // The flight has staff as required by the specification
106 rel(*this, cardinality(flight[i]) == requiredCrew[i].staff);
107
108 // Enough members of different categories are on board
109 rel(*this, cardinality(flight[i] & stewardsDS) >=
110 requiredCrew[i].stewards);
111 rel(*this, cardinality(flight[i] & hostessesDS) >=
112 requiredCrew[i].hostesses);
113 rel(*this, cardinality(flight[i] & spanishDS) >=
114 requiredCrew[i].spanish);
115 rel(*this, cardinality(flight[i] & frenchDS) >=
116 requiredCrew[i].french);
117 rel(*this, cardinality(flight[i] & germanDS) >=
118 requiredCrew[i].german);
119 }
120
121 // No crew member of flight i works on flights i+1 and i+2
122 for (int i=0; i<noOfFlights-2; i++) {
123 rel(*this, flight[i] || flight[i+1]);
124 rel(*this, flight[i] || flight[i+2]);
125 }
126 rel(*this, flight[noOfFlights-2] || flight[noOfFlights-1]);
127
129 }
130
132 virtual void
133 print(std::ostream& os) const {
134 for (int i=0; i<noOfFlights; i++) {
135 os << "\tFlight " << i+1 << ":" << std::endl;
136 os << "\t\tCrew\tStew.\tHost.\tFrench\tSpanish\tGerman"
137 << std::endl << "\t";
138 os << "\t" << requiredCrew[i].staff << "\t" << requiredCrew[i].stewards
139 << "\t" << requiredCrew[i].hostesses << "\t"
140 << requiredCrew[i].spanish
141 << "\t" << requiredCrew[i].french << "\t" << requiredCrew[i].german
142 << std::endl;
143
144 os << "\t\tSchedule:" << std::endl << "\t\t";
145 if (flight[i].assigned()) {
146 for (SetVarGlbValues d(flight[i]);d();++d) {
147 os << employeeToName(static_cast<Employee>(d.val())) << " ";
148 }
149 } else {
150 os << "\tRequired: ";
151 for (SetVarGlbValues d(flight[i]);d();++d) {
152 os << employeeToName(static_cast<Employee>(d.val())) << " ";
153 }
154 os << std::endl << "\t\t\tPossible: ";
155 for (SetVarUnknownValues d(flight[i]);d();++d) {
156 os << employeeToName(static_cast<Employee>(d.val())) << " ";
157 }
158 }
159 os << std::endl << std::endl;
160 }
161 }
162
165 : Script(s) {
166 flight.update(*this, s.flight);
167 }
168
169 virtual
170 Space *copy(void) {
171 return new Crew(*this);
172 }
173
174};
175
179int
180main(int argc, char* argv[]) {
181 Options o("Crew");
182 o.iterations(100);
183 o.parse(argc,argv);
185 return 0;
186}
187
188namespace {
189
191 const char*
192 employeeToName(Employee e) {
193 switch(e) {
194 case Tom : return "Tom";
195 case David : return "David";
196 case Jeremy: return "Jeremy";
197 case Ron: return "Ron";
198 case Joe: return "Joe";
199 case Bill: return "Bill";
200 case Fred: return "Fred";
201 case Bob: return "Bob";
202 case Mario: return "Mario";
203 case Ed: return "Ed";
204 case Carol: return "Carol";
205 case Janet: return "Janet";
206 case Tracy: return "Tracy";
207 case Marilyn: return "Marilyn";
208 case Carolyn: return "Carolyn";
209 case Cathy: return "Cathy";
210 case Inez: return "Inez";
211 case Jean: return "Jean";
212 case Heather: return "Heather";
213 case Juliet: return "Juliet";
214 default: GECODE_NEVER; return "";
215 }
216 }
217
218 // these have to be sorted!
220 const int stewards[] =
221 {Tom, David, Jeremy, Ron, Joe, Bill, Fred, Bob, Mario, Ed};
223 const int noOfStewards = sizeof(stewards) / sizeof(int);
225 const int hostesses[] =
226 { Carol, Janet, Tracy, Marilyn, Carolyn, Cathy, Inez,
227 Jean, Heather, Juliet };
229 const int noOfHostesses = sizeof(hostesses) / sizeof(int);
231 const int frenchSpeaking[] =
232 { Bill, Inez, Jean, Juliet };
234 const int noOfFrenchSpeaking = sizeof(frenchSpeaking) / sizeof(int);
236 const int germanSpeaking[] =
237 { Tom, Jeremy, Mario, Cathy, Juliet };
239 const int noOfGermanSpeaking = sizeof(germanSpeaking) / sizeof(int);
241 const int spanishSpeaking[] =
242 { Joe, Bill, Fred, Mario, Marilyn, Inez, Heather };
244 const int noOfSpanishSpeaking = sizeof(spanishSpeaking) / sizeof(int);
245
247 const Flight requiredCrew[] =
248 { {4,1,1,1,1,1},
249 {5,1,1,1,1,1},
250 {5,1,1,1,1,1},
251 {6,2,2,1,1,1},
252 {7,3,3,1,1,1},
253 {4,1,1,1,1,1},
254 {5,1,1,1,1,1},
255 {6,1,1,1,1,1},
256 {6,2,2,1,1,1},
257 {7,3,3,1,1,1} };
258
260 const int noOfFlights = sizeof(requiredCrew) / sizeof(Flight);
261}
262
263// STATISTICS: example-any
264
int main(int argc, char *argv[])
Main-function.
Definition crew.cpp:180
Crew(const Options &opt)
The actual model.
Definition crew.cpp:96
Crew(Crew &s)
Constructor for cloning s.
Definition crew.cpp:164
SetVarArray flight
The crew for each flight.
Definition crew.cpp:93
virtual Space * copy(void)
Copy during cloning.
Definition crew.cpp:170
virtual void print(std::ostream &os) const
Print solution.
Definition crew.cpp:133
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition options.cpp:548
static void run(const Options &opt, Script *s=NULL)
Integer sets.
Definition int.hh:174
Options for scripts
Definition driver.hh:366
void iterations(unsigned int i)
Set default number of iterations.
Definition options.hpp:461
Set variable array
Definition set.hh:573
Iterator for the values in the greatest lower bound of a set variable.
Definition set.hh:369
Iterator for the values in the unknown set of a set variable.
Definition set.hh:425
Computation spaces.
Definition core.hpp:1744
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:801
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode toplevel namespace
Select first unassigned variable SetVarBranch SET_VAR_NONE(void)
Definition var.hpp:96
Include smallest element SetValBranch SET_VAL_MIN_INC(void)
Definition val.hpp:55
LinIntExpr cardinality(const SetExpr &)
Cardinality of set expression.
Definition set-expr.cpp:817
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56