main page modules namespaces classes files
Gecode home

search for 

golf.cc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Guido Tack <tack@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2004
 *     Guido Tack, 2004
 *
 *  Last modified:
 *     $Date: 2006-08-04 16:06:52 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
 *     $Revision: 3517 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

#include "gecode/set.hh"
#include "examples/support.hh"


struct Tournament {
  int groups;
  int playersInGroup;
  int weeks;
};
static const Tournament t[]=
  { {8,4,9},
    {5,3,7},
    {4,3,2}
  };
static const unsigned int n_examples = sizeof(t) / sizeof(Tournament);

class Golf : public Example {
public:
  int groups;
  int playersInGroup;
  int weeks;
  int players;

  SetVarArray groupsS;
  IntVarArray groupsSInv;

  SetVar& group(int w, int g) {
    return groupsS[w*groups+g];
  }
  IntVar& groupInv(int w, int p) {
    return groupsSInv[w*players+p];
  }

  Golf(const Options& o) :
    groups(t[o.size].groups),
    playersInGroup(t[o.size].playersInGroup),
    weeks(t[o.size].weeks),
    players(groups*playersInGroup),
    groupsS(this,groups*weeks,IntSet::empty,0,players-1,
            playersInGroup,playersInGroup),
    groupsSInv(this, weeks*players, 0, groups-1) {

    SetVar allPlayers(this, 0, players-1, 0, players-1);

    // Groups in one week must be disjoint
    for (int w=0; w<weeks; w++) {
      SetVarArgs p(groups);
      for (int g=0; g < groups; g++)
        p[g] = group(w,g);

      rel(this,SOT_DUNION,p,allPlayers);
    }

    // No two golfers play in the same group more than once
    for (int w=0; w<weeks; w++) {
      for (int g=0; g<groups; g++) {
        SetVar v = group(w,g);
        for (int i=(w+1)*groups; i<weeks*groups; i++) {
          SetVar atMostOne(this,IntSet::empty,0,players-1,0,1);
          rel(this, v, SOT_INTER, groupsS[i], SRT_EQ, atMostOne);
        }
      }
    }

    if (!o.naive) {

      //      atmostOne(this, groupsS, playersInGroup);

      /*
       * Redundant constraints and static symmetry breaking from
       * "Solving Kirkman's Schoolgirl Problem in a Few Seconds"
       * Nicolas Barnier, Pascal Brisset, Constraints, 10, 7-21, 2005
       *
       */

      // Redundant constraint:
      // in each week, one player plays in only one group
      for (int w=0; w < weeks; w++) {
        for (int p=0; p < players; p++) {
          BoolVarArgs bs(groups);
          for (int g=0; g<groups; g++) {
            BoolVar b(this,0,1);
            dom(this, group(w,g), SRT_SUP, p, b);
            bs[g] = b;
          }
          linear(this, bs, IRT_EQ, 1);
        }
       }

      // Redundant constraint:
      // any two groups has at most one player in common
      atmostOne(this, groupsS, playersInGroup);

      // Symmetry breaking: order groups
      for (int w=0; w<weeks; w++) {
        for (int g=0; g<groups-1; g++) {
          IntVar minG1(this, 0, players-1);
          IntVar minG2(this, 0, players-1);
          SetVar g1 = group(w,g);
          SetVar g2 = group(w,g+1);
          min(this, g1, minG1);
          min(this, g2, minG2);
          rel(this, minG1, IRT_LE, minG2);
        }
      }

      // Symmetry breaking: order weeks
      // minElem(group(w,0)\{0}) < minElem(group(w+1,0)\{0})
      for (int w=0; w<weeks-1; w++) {
        SetVar g1(this, IntSet::empty, 1, players-1);
        SetVar g2(this, IntSet::empty, 1, players-1);
        SetVar zero1(this, IntSet::empty,0,0);
        SetVar zero2(this, IntSet::empty,0,0);
        rel(this, g1, SOT_DUNION, zero1, SRT_EQ, group(w,0));
        rel(this, g2, SOT_DUNION, zero2, SRT_EQ, group(w+1,0));
        IntVar minG1(this, 0, players-1);
        IntVar minG2(this, 0, players-1);
        min(this, g1, minG1);
        min(this, g2, minG2);
        rel(this, minG1, IRT_LE, minG2);
      }

      // Initialize the dual variables:
      // groupInv(w,p) is player p's group in week w
      for (int w=0; w<weeks; w++) {
        for (int p=0; p<players; p++) {
          SetVar thisPlayer(this, p,p, 0, players-1);
          SetVarArgs thisWeek(groups);
          for (int g=0; g<groups; g++)
            thisWeek[g] = group(w,g);
          selectSet(this, thisWeek, groupInv(w,p), thisPlayer);
        }
      }

      // Symmetry breaking: order players
      // For all p<groups : groupInv(w,p) <= p
      for (int w=0; w<weeks; w++) {
        for (int p=0; p<groups; p++) {
          rel(this, groupInv(w,p), IRT_LQ, p);
        }
      }

    }

    branch(this, groupsS, SETBVAR_MIN_UNKNOWN_ELEM, SETBVAL_MIN);
  }

  Golf(bool share, Golf& s) : Example(share,s),
      groups(s.groups), playersInGroup(s.playersInGroup),
      weeks(s.weeks), players(s.players) {
    groupsS.update(this, share, s.groupsS);
  }

  virtual Space*
  copy(bool share) {
    return new Golf(share,*this);
  }

  virtual void
  print(void) {

    std::cout << "Tournament plan" << std::endl;

    for (int w=0; w<weeks; w++) {
      std::cout << "Week " << w << ": " << std::endl << "    ";
      for (int g=0; g<groups; g++) {
        SetVarGlbValues glb(group(w,g));
        std::cout << "(" << glb.val();
        ++glb;
        while(glb()) {
          std::cout << " " << glb.val();
          ++glb;
        }
        std::cout << ")";
        if (g < groups-1) std::cout << " ";
        if (g > 0 && g % 4 == 0) std::cout << std::endl << "    ";
      }
      std::cout << std::endl;
    }

  }
};

int
main(int argc, char** argv) {
  Options o("Golf");
  o.parse(argc,argv);
  o.solutions  = 1;
  if (o.size >= n_examples) {
    std::cerr << "Error: size must be between 0 and " << n_examples - 1
              << std::endl;
    return 1;
  }
  Example::run<Golf,DFS>(o);
  return 0;
}

// STATISTICS: example-any