this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5 *
6 * Contributing authors:
7 * Christian Schulte <schulte@gecode.org>
8 *
9 * Copyright:
10 * Patrick Pekczynski, 2004
11 * Christian Schulte, 2007
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#include <gecode/driver.hh>
39#include <gecode/int.hh>
40#include <gecode/minimodel.hh>
41
42#include <algorithm>
43#include <iomanip>
44
45using namespace Gecode;
46
47/// Entry in round robin schedule
48class Play {
49public:
50 int h; ///< home team
51 int a; ///< away team
52 int g; ///< game number
53 /// Default constructor
54 Play(void) : h(0), a(0), g(0) {}
55};
56
57/// Round robin schedule
58class RRS {
59protected:
60 /// Number of teams
61 const int teams;
62 /// Play information
63 Play* plays;
64 /// Return number of weeks
65 int weeks(void) const {
66 return teams-1;
67 }
68 /// Return number of periods
69 int periods(void) const {
70 return teams/2;
71 }
72 /// Game number for game between home team \a h and away team \a a
73 int gn(int h, int a) const {
74 return teams*(h-1) + a;
75 }
76 /// Play for period \a p and week \a w
77 Play& play(int p, int w) {
78 return plays[p*weeks() + w];
79 }
80public:
81 /**
82 * \brief Build a feasible schedule
83 *
84 * The games of the first week are fixed as:
85 * \f$ \langle 1,2 \rangle \cup
86 * \{\langle p + 2, t - p + 1\rangle | p \geq 1\}\f$. \n
87 * The remaining games are computed by transforming a game
88 * \f$ \langle h, a, g \rangle \f$ from the previous week
89 * in a new game \f$ \langle h', a'\rangle \f$, where: \n
90 * \f$ h' = \left\{
91 * \begin{tabular}{l c l}
92 * 1 & & if $h = 1$ \\
93 * 2 & & if $h = t$ \\
94 * $h + 1$ & & otherwise
95 * \end{tabular}\right.
96 * \f$ and
97 * \f$ a' = \left\{
98 * \begin{tabular}{l c l}
99 * 2 & & if $h = t$ \\
100 * a + 1 & & otherwise
101 * \end{tabular}\right.
102 * \f$
103 *
104 *
105 */
106 RRS(int t) : teams(t), plays(new Play[periods()*weeks()]) {
107 // Determine the first game (week 0 period 0)
108 play(0,0).h = 1;
109 play(0,0).a = 2;
110 play(0,0).g = 2;
111
112 // Determine the other games of the first week
113 for (int p=1; p<periods(); p++) {
114 play(p,0).h = (p + 1) + 1;
115 play(p,0).a = teams - (p + 1 - 2);
116 play(p,0).g = gn(play(p,0).h,play(p,0).a);
117 }
118
119 // Compute the games for the subsequent weeks
120 for (int w=1; w<weeks(); w++) {
121 for (int p=0; p<periods(); p++) {
122 if (play(p,w-1).h == teams)
123 play(p,w).h = 2;
124 else if (play(p,w-1).h == 1)
125 play(p,w).h = 1;
126 else
127 play(p,w).h = play(p,w-1).h + 1;
128 if (play(p,w-1).a == teams)
129 play(p,w).a = 2;
130 else
131 play(p,w).a = play(p,w-1).a + 1;
132
133 // maintain symmetry for (h,a): h < a
134 if (play(p,w).h > play(p,w).a)
135 std::swap(play(p,w).h,play(p,w).a);
136
137 play(p,w).g = gn(play(p,w).h,play(p,w).a);
138 }
139 }
140
141 }
142 /// Home, away, and game information
143 void hag(int w, IntArgs& h, IntArgs& a, IntArgs& g) {
144 for (int p=0; p<periods(); p++) {
145 h[p] = play(p,w).h;
146 a[p] = play(p,w).a;
147 g[p] = play(p,w).g;
148 }
149 }
150 /// Delete schedule
151 ~RRS(void) {
152 delete [] plays;
153 }
154};
155
156
157
158/**
159 * \brief %Example: %Sports league scheduling
160 *
161 * -# There are \f$ t \f$ teams (\f$ t \f$ even).
162 * -# The season lasts \f$ t - 1 \f$ weeks.
163 * -# Each game between two different teams occurs exactly once.
164 * -# Every team plays one game in each week of the season.
165 * -# There are \f$ \displaystyle\frac{t}{2} \f$ periods and each week
166 * every period is scheduled for one game.
167 * -# No team plays more than twice in the same period over
168 * the course of the season.
169 *
170 * See also problem 26 at http://www.csplib.org/.
171 *
172 * \ingroup Example
173 */
174class SportsLeague : public Script {
175protected:
176 const int teams; ///< number of teams
177 IntVarArray home; ///< home teams
178 IntVarArray away; ///< away teams
179 IntVarArray game; ///< game numbers
180
181 /// Return number of weeks
182 int weeks(void) const {
183 return teams-1;
184 }
185 /// Return number of periods
186 int periods(void) const {
187 return teams/2;
188 }
189 /// Home team in period \a p and week \a w
190 IntVar& h(int p, int w) {
191 return home[p*teams + w];
192 }
193 /// Home team in period \a p and week \a w
194 const IntVar& h(int p, int w) const {
195 return home[p*teams + w];
196 }
197 /// Away team in period \a p and week \a w
198 IntVar& a(int p, int w) {
199 return away[p*teams + w];
200 }
201 /// Away team in period \a p and week \a w
202 const IntVar& a(int p, int w) const {
203 return away[p*teams + w];
204 }
205 /// Return game number for game in period \a p and week \a w
206 IntVar& g(int p, int w) {
207 return game[p*weeks() + w];
208 }
209 /// Return game number for game in period \a p and week \a w
210 const IntVar& g(int p, int w) const {
211 return game[p*weeks() + w];
212 }
213
214public:
215 /// Setup model
216 SportsLeague(const SizeOptions& opt) :
217 Script(opt),
218 teams(opt.size()),
219 home(*this, periods() * teams, 1, weeks()),
220 away(*this, periods() * teams, 2, weeks()+1),
221 game(*this, weeks()*periods(), 2, teams*weeks())
222 {
223 // Initialize round robin schedule
224 RRS r(teams);
225
226 // Domain for gamenumber of period
227 for (int w=0; w<weeks(); w++) {
228 IntArgs rh(periods()), ra(periods()), rg(periods());
229 IntVarArgs n(*this,periods(),0,periods()-1);
230
231 distinct(*this, n, opt.ipl());
232
233 r.hag(w,rh,ra,rg);
234
235 for (int p=0; p<periods(); p++) {
236 element(*this, rh, n[p], h(p,w));
237 element(*this, ra, n[p], a(p,w));
238 element(*this, rg, n[p], g(p,w));
239 }
240 }
241
242 /// (h,a) and (a,h) are the same game, focus on home (that is, h<a)
243 for (int p=0; p<periods(); p++)
244 for (int w=0; w<teams; w++)
245 rel(*this, h(p,w), IRT_LE, a(p,w));
246
247 // Home teams in first week are ordered
248 {
249 IntVarArgs h0(periods());
250 for (int p=0; p<periods(); p++)
251 h0[p] = h(p,0);
252 rel(*this, h0, IRT_LE);
253 }
254
255 // Fix first pair
256 rel(*this, h(0,0), IRT_EQ, 1);
257 rel(*this, a(0,0), IRT_EQ, 2);
258
259 /// Column constraint: each team occurs exactly once
260 for (int w=0; w<teams; w++) {
261 IntVarArgs c(teams);
262 for (int p=0; p<periods(); p++) {
263 c[2*p] = h(p,w); c[2*p+1] = a(p,w);
264 }
265 distinct(*this, c, opt.ipl());
266 }
267
268 /// Row constraint: no team appears more than twice
269 for (int p=0; p<periods(); p++) {
270 IntVarArgs r(2*teams);
271 for (int t=0; t<teams; t++) {
272 r[2*t] = h(p,t);
273 r[2*t+1] = a(p,t);
274 }
275 IntArgs values(teams);
276 for (int i=1; i<=teams; i++)
277 values[i-1] = i;
278 count(*this, r, IntSet(2,2), values, opt.ipl());
279 }
280
281 // Redundant constraint
282 for (int p=0; p<periods(); p++)
283 for (int w=0; w<weeks(); w ++)
284 rel(*this, teams * h(p,w) + a(p,w) - g(p,w) == teams);
285
286 distinct(*this, game, opt.ipl());
287
288 branch(*this, game, INT_VAR_NONE(), INT_VAL_SPLIT_MIN());
289 }
290 /// Constructor for cloning \a s
291 SportsLeague(SportsLeague& s)
292 : Script(s), teams(s.teams) {
293 home.update(*this, s.home);
294 away.update(*this, s.away);
295 game.update(*this, s.game);
296 }
297 /// Copy during cloning
298 virtual Space*
299 copy(void) {
300 return new SportsLeague(*this);
301 }
302 /// Print solution
303 virtual void print(std::ostream& os) const {
304 // print period index
305 os << "\t ";
306 for (int p=0; p<periods(); p++) {
307 os << "P[";
308 os.width(2);
309 os << p << "] ";
310 }
311 os << std::endl;
312 // print entries
313 for (int w=0; w<weeks(); w++) {
314 os << "\tW[";
315 os.width(2);
316 os << w+1 << "]: ";
317 for (int p=0; p<periods(); p++) {
318 os.width(2);
319 os << h(p,w).val() << '-';
320 os.width(2);
321 os << a(p,w).val() << " ";
322 }
323 os << std::endl;
324 }
325 }
326};
327
328
329/** \brief Main-function
330 * \relates SportsLeague
331 */
332int
333main(int argc, char* argv[]) {
334 SizeOptions opt("Sports League Scheduling");
335 opt.ipl(IPL_DOM);
336 opt.size(18);
337 opt.parse(argc,argv);
338 if (opt.size() < 5) {
339 std::cerr<< "No Solution for less than 5 teams!" << std::endl;
340 return 1;
341 }
342 if (opt.size() % 2 != 0) {
343 std::cerr << "Number of teams has to be even!" << std::endl;
344 return 1;
345 }
346 Script::run<SportsLeague, DFS,SizeOptions>(opt);
347 return 0;
348}
349
350// STATISTICS: example-any