/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ /* * Main authors: * Patrick Pekczynski <pekczynski@ps.uni-sb.de> * * Contributing authors: * Christian Schulte <schulte@gecode.org> * * Copyright: * Patrick Pekczynski, 2004 * Christian Schulte, 2007 * * Last modified: * $Date: 2011-06-17 00:13:18 +1000 (Fri, 17 Jun 2011) $ by $Author: schulte $ * $Revision: 12053 $ * * This file is part of Gecode, the generic constraint * development environment: * http://www.gecode.org * * Permission is hereby granted, free of charge, to any person obtaining * a copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sublicense, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. * */ #include <gecode/driver.hh> #include <gecode/int.hh> #include <gecode/minimodel.hh> #include <algorithm> #include <iomanip> using namespace Gecode; /// Entry in round robin schedule class Play { public: int h; ///< home team int a; ///< away team int g; ///< game number /// Default constructor Play(void) : h(0), a(0), g(0) {} }; /// Round robin schedule class RRS { protected: /// Number of teams const int teams; /// Play information Play* plays; /// Return number of weeks int weeks(void) const { return teams-1; } /// Return number of periods int periods(void) const { return teams/2; } /// Game number for game between home team \a h and away team \a a int gn(int h, int a) const { return teams*(h-1) + a; } /// Play for period \a p and week \a w Play& play(int p, int w) { return plays[p*weeks() + w]; } public: /** * \brief Build a feasible schedule * * The games of the first week are fixed as: * \f$ \langle 1,2 \rangle \cup * \{\langle p + 2, t - p + 1\rangle | p \geq 1\}\f$. \n * The remaining games are computed by transforming a game * \f$ \langle h, a, g \rangle \f$ from the previous week * in a new game \f$ \langle h', a'\rangle \f$, where: \n * \f$ h' = \left\{ * \begin{tabular}{l c l} * 1 & & if $h = 1$ \\ * 2 & & if $h = t$ \\ * $h + 1$ & & otherwise * \end{tabular}\right. * \f$ and * \f$ a' = \left\{ * \begin{tabular}{l c l} * 2 & & if $h = t$ \\ * a + 1 & & otherwise * \end{tabular}\right. * \f$ * * */ RRS(int t) : teams(t), plays(new Play[periods()*weeks()]) { // Determine the first game (week 0 period 0) play(0,0).h = 1; play(0,0).a = 2; play(0,0).g = 2; // Determine the other games of the first week for (int p=1; p<periods(); p++) { play(p,0).h = (p + 1) + 1; play(p,0).a = teams - (p + 1 - 2); play(p,0).g = gn(play(p,0).h,play(p,0).a); } // Compute the games for the subsequent weeks for (int w=1; w<weeks(); w++) { for (int p=0; p<periods(); p++) { if (play(p,w-1).h == teams) play(p,w).h = 2; else if (play(p,w-1).h == 1) play(p,w).h = 1; else play(p,w).h = play(p,w-1).h + 1; if (play(p,w-1).a == teams) play(p,w).a = 2; else play(p,w).a = play(p,w-1).a + 1; // maintain symmetry for (h,a): h < a if (play(p,w).h > play(p,w).a) std::swap(play(p,w).h,play(p,w).a); play(p,w).g = gn(play(p,w).h,play(p,w).a); } } } /// Home, away, and game information void hag(int w, IntArgs& h, IntArgs& a, IntArgs& g) { for (int p=0; p<periods(); p++) { h[p] = play(p,w).h; a[p] = play(p,w).a; g[p] = play(p,w).g; } } /// Delete schedule ~RRS(void) { delete [] plays; } }; /** * \brief %Example: %Sports league scheduling * * -# There are \f$ t \f$ teams (\f$ t \f$ even). * -# The season lasts \f$ t - 1 \f$ weeks. * -# Each game between two different teams occurs exactly once. * -# Every team plays one game in each week of the season. * -# There are \f$ \displaystyle\frac{t}{2} \f$ periods and each week * every period is scheduled for one game. * -# No team plays more than twice in the same period over * the course of the season. * * See also problem 26 at http://www.csplib.org/. * * \ingroup Example */ class SportsLeague : public Script { protected: const int teams; ///< number of teams IntVarArray home; ///< home teams IntVarArray away; ///< away teams IntVarArray game; ///< game numbers /// Return number of weeks int weeks(void) const { return teams-1; } /// Return number of periods int periods(void) const { return teams/2; } /// Home team in period \a p and week \a w IntVar& h(int p, int w) { return home[p*teams + w]; } /// Home team in period \a p and week \a w const IntVar& h(int p, int w) const { return home[p*teams + w]; } /// Away team in period \a p and week \a w IntVar& a(int p, int w) { return away[p*teams + w]; } /// Away team in period \a p and week \a w const IntVar& a(int p, int w) const { return away[p*teams + w]; } /// Return game number for game in period \a p and week \a w IntVar& g(int p, int w) { return game[p*weeks() + w]; } /// Return game number for game in period \a p and week \a w const IntVar& g(int p, int w) const { return game[p*weeks() + w]; } public: /// Setup model SportsLeague(const SizeOptions& opt) : teams(opt.size()), home(*this, periods() * teams, 1, weeks()), away(*this, periods() * teams, 2, weeks()+1), game(*this, weeks()*periods(), 2, teams*weeks()) { // Initialize round robin schedule RRS r(teams); // Domain for gamenumber of period for (int w=0; w<weeks(); w++) { IntArgs rh(periods()), ra(periods()), rg(periods()); IntVarArgs n(*this,periods(),0,periods()-1); distinct(*this, n, opt.icl()); r.hag(w,rh,ra,rg); for (int p=0; p<periods(); p++) { element(*this, rh, n[p], h(p,w)); element(*this, ra, n[p], a(p,w)); element(*this, rg, n[p], g(p,w)); } } /// (h,a) and (a,h) are the same game, focus on home (that is, h<a) for (int p=0; p<periods(); p++) for (int w=0; w<teams; w++) rel(*this, h(p,w), IRT_LE, a(p,w)); // Home teams in first week are ordered { IntVarArgs h0(periods()); for (int p=0; p<periods(); p++) h0[p] = h(p,0); rel(*this, h0, IRT_LE); } // Fix first pair rel(*this, h(0,0), IRT_EQ, 1); rel(*this, a(0,0), IRT_EQ, 2); /// Column constraint: each team occurs exactly once for (int w=0; w<teams; w++) { IntVarArgs c(teams); for (int p=0; p<periods(); p++) { c[2*p] = h(p,w); c[2*p+1] = a(p,w); } distinct(*this, c, opt.icl()); } /// Row constraint: no team appears more than twice for (int p=0; p<periods(); p++) { IntVarArgs r(2*teams); for (int t=0; t<teams; t++) { r[2*t] = h(p,t); r[2*t+1] = a(p,t); } IntArgs values(teams); for (int i=1; i<=teams; i++) values[i-1] = i; count(*this, r, IntSet(2,2), values, opt.icl()); } // Redundant constraint for (int p=0; p<periods(); p++) for (int w=0; w<weeks(); w ++) rel(*this, teams * h(p,w) + a(p,w) - g(p,w) == teams); distinct(*this, game, opt.icl()); branch(*this, game, INT_VAR_NONE, INT_VAL_SPLIT_MIN); } /// Constructor for cloning \a s SportsLeague(bool share, SportsLeague& s) : Script(share, s), teams(s.teams) { home.update(*this, share, s.home); away.update(*this, share, s.away); game.update(*this, share, s.game); } /// Copy during cloning virtual Space* copy(bool share) { return new SportsLeague(share, *this); } /// Print solution virtual void print(std::ostream& os) const { // print period index os << "\t "; for (int p=0; p<periods(); p++) { os << "P["; os.width(2); os << p << "] "; } os << std::endl; // print entries for (int w=0; w<weeks(); w++) { os << "\tW["; os.width(2); os << w+1 << "]: "; for (int p=0; p<periods(); p++) { os.width(2); os << h(p,w).val() << '-'; os.width(2); os << a(p,w).val() << " "; } os << std::endl; } } }; /** \brief Main-function * \relates SportsLeague */ int main(int argc, char* argv[]) { SizeOptions opt("Sports League Scheduling"); opt.icl(ICL_DOM); opt.size(18); opt.parse(argc,argv); if (opt.size() < 5) { std::cerr<< "No Solution for less than 5 teams!" << std::endl; return 1; } if (opt.size() % 2 != 0) { std::cerr << "Number of teams has to be even!" << std::endl; return 1; } Script::run<SportsLeague, DFS,SizeOptions>(opt); return 0; } // STATISTICS: example-any