18. Social golfers — Modeling and Programming with Gecode

This chapter presents a case study on modeling problems using set variables and constraints.

18.1. Problem¶

The social golfers’ problem ( CSPLib problem 10 ) requires finding a schedule for a golf tournament. There are \(g\cdot s\) golfers who want to play a tournament in \(g\) groups of \(s\) golfers each over \(w\) weeks, such that no two golfers play against each other more than once during the tournament.

Here is a solution for the instance \(w=4\), \(g=3\), and \(s=3\), where the players are numbered from 0 to 8:

			Group 1			Group 2
Week 0	1	2	3	4	5	6	7	8
Week 1	3	6	1	4	7	2	5	8
Week 2	4	8	1	5	6	2	3	7
Week 3	5	7	1	3	8	2	4	6

18.2. Model¶

The model for the social golfers’ problem closely follows the above problem description. Its outline is shown in A script for the social golfers’ problem . The script defines an array of set variables groups of size \(\mathtt g\cdot \mathtt w\), where each group can contain the players \(0\dots \mathtt g\cdot \mathtt s-1\) and has cardinality \(\mathtt s\) (see Set variables ).

The script also defines a matrix schedule with \(g\) columns and \(w\) rows on top of the variable array, such that schedule(i,j) is the set of members of group \(\mathtt i\) in week \(\mathtt j\).

The constraints are straightforward. For each week, the union of all groups must be disjoint and contain all players. This can be expressed directly using a disjoint union constraint (see Expressions and relations ) on the rows of the schedule:

    SetVar allPlayers(*this, 0,g*s-1, 0,g*s-1);
    for (int i=0; i<w; i++)
      rel(*this, setdunion(schedule.row(i)) == allPlayers);

Each group can have at most one player in common with any other group. This can be expressed by a constraint that states that the cardinality of the intersection between any two groups must be at most \(1\):

    for (int i=0; i<groups.size()-1; i++)
      for (int j=i+1; j<groups.size(); j++)
        rel(*this, cardinality(groups[i] & groups[j]) <= 1);

Program 18.1 A script for the social golfers’ problem¶

...
class GolfOptions : public Options {
...
};

class Golf : public Script {
  int g, s, w;
  SetVarArray groups;
public:
  Golf(const GolfOptions& opt)
  : Script(opt), g(opt.g()), s(opt.s()), w(opt.w()),
    groups(*this,g*w,IntSet::empty,0,g*s-1,
           static_cast<unsigned int>(s),
           static_cast<unsigned int>(s)) {
    Matrix<SetVarArray> schedule(groups,g,w);
    // [golf:groups in a week]
    // [golf:overlap between groups]
    // [golf:break group symmetry]
    // [golf:break week symmetry]
    // [golf:break player symmetry]
    branch(*this, groups, SET_VAR_MIN_MIN(), SET_VAL_MIN_INC());
  }
  ...
};

...

Download: golf.cpp

18.2.1. Symmetry breaking.¶

Using set variables to model the groups already avoids introducing symmetry among the players in a group. For example, if we had modeled each group as \(s\) integer variables, any permutation of these variables would produce an equivalent solution.

But there are more symmetries in this problem, and some of them can be avoided easily by introducing additional symmetry breaking constraints.

Within a week, the order of the groups is irrelevant. Therefore, we can impose a static order requiring that all minimal elements of each group are ordered increasingly (see Constraints connecting set and integer variables for the minimal element constraint, Expressions and relations for the MiniModel support, and Simple relation constraints over integer variables for ordering integer variables):

    for (int j=0; j<w; j++) {
      IntVarArgs m(g);
      for (int i=0; i<g; i++)
        m[i] = expr(*this, min(schedule(i,j)));
      rel(*this, m, IRT_LE);
    }

Similarly to the group symmetry, the order of the weeks is irrelevant. Again, the symmetry can be broken by imposing an order on the group elements. The previous constraint made sure that player 0 will always be in schedule(0,j) for any week j. So imposing an order on the second smallest element of schedule(0,j) will do the trick:

    IntVarArgs m(w);
    for (int j=0; j<w; j++)
      m[j] = expr(*this, min(schedule(0,j)-IntSet(0,0)));
    rel(*this, m, IRT_LE);

Finally, the players can be permuted arbitrarily. For example, swapping the numbers \(2\) and \(6\) in the initial example produces a symmetric solution:

			Group 1			Group 2
Week 0	1	6	3	4	5	2	7	8
Week 1	3	2	1	4	7	6	5	8
Week 2	4	8	1	5	2	6	3	7
Week 3	5	7	1	3	8	6	4	2

This symmetry can be broken using the precede constraint (see Value precedence constraints ):

    precede(*this, groups, IntArgs::create(groups.size(),0));

It enforces for any pair of players \(s\) and \(t\) that \(t\) can only appear in a group without \(s\) if there is an earlier group where \(s\) appears without \(t\). This establishes an order that breaks the value symmetry between the players. In the example above, the constraint rules out that \(6\) appears in group 0, week 0, because that would require \(2\) to appear in an earlier group. The only solution that remains after symmetry breaking is the one in the initial table in Problem .

Note that these symmetry breaking constraints do not necessariyl break all symmetries of the problem completely. We mainly discussed them as additional examples of modeling with set variables and constraints.

18.3. More information¶

The case study is also available as a Gecode example, see golf . You can find a discussion of the symmetry breaking constraints presented here and a number of additional implied constraints in [3] .

18. Social golfers¶

18.1. Problem¶

18.2. Model¶

18.2.1. Symmetry breaking.¶

18.3. More information¶