sports-league.cpp

Go to the documentation of this file.

/* -*- 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-16 16:13:18 +0200 (Thu, 16 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;

class Play {
public:
  int h; 
  int a; 
  int g; 

  Play(void) : h(0), a(0), g(0) {}
};

class RRS {
protected:
  const int teams;
  Play* plays;
  int weeks(void) const {
    return teams-1;
  }
  int periods(void) const {
    return teams/2;
  }
  int gn(int h, int a) const {
    return teams*(h-1) + a;
  }
  Play& play(int p, int w) {
    return plays[p*weeks() + w];
  }
public:
  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);
      }
    }

  }
  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;
    }
  }
  ~RRS(void) {
    delete [] plays;
  }
};



class SportsLeague : public Script {
protected:
  const int teams;  
  IntVarArray home; 
  IntVarArray away; 
  IntVarArray game; 

  int weeks(void) const {
    return teams-1;
  }
  int periods(void) const {
    return teams/2;
  }
  IntVar& h(int p, int w) {
    return home[p*teams + w];
  }
  const IntVar& h(int p, int w) const {
    return home[p*teams + w];
  }
  IntVar& a(int p, int w) {
    return away[p*teams + w];
  }
  const IntVar& a(int p, int w) const {
    return away[p*teams + w];
  }
  IntVar& g(int p, int w) {
    return game[p*weeks() + w];
  }
  const IntVar& g(int p, int w) const {
    return game[p*weeks() + w];
  }

public:
  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));
      }
    }

    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);

    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());
    }

    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);
  }
  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);
  }
  virtual Space*
  copy(bool share) {
    return new SportsLeague(share, *this);
  }
  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;
    }
  }
};


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