Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
9.5 kB · 350 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351/* -*- 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 * * 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 scheduleclass 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 scheduleclass 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) : Script(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.ipl());
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.ipl()); }
/// 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.ipl()); }
// 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.ipl());
branch(*this, game, INT_VAR_NONE(), INT_VAL_SPLIT_MIN()); } /// Constructor for cloning \a s SportsLeague(SportsLeague& s) : Script(s), teams(s.teams) { home.update(*this, s.home); away.update(*this, s.away); game.update(*this, s.game); } /// Copy during cloning virtual Space* copy(void) { return new SportsLeague(*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 */intmain(int argc, char* argv[]) { SizeOptions opt("Sports League Scheduling"); opt.ipl(IPL_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