This article shows how to solve a hard
scheduling problem (scheduling a golf tournament), using Koalog Constraint
Solver, a Java library for constraint programming.

The social golfer problem

This article shows how to solve a hard

scheduling problem (scheduling a golf tournament), using Koalog Constraint

Solver, a Java library for constraint programming.

##

On May 1998, a post on the *sci.op-research* newsgroup

posed the following problem: suppose you have 32 golfers who organize

each week into groups of four. The original post said that the goal is

to select the foursomes so that each person only golfs with the same

person once. How many weeks before all of the options are exhausted?

This problem has since become a famous combinatorial problem and is

usually called the *social golfer* problem. It is a

generalization of a

round-robin

tournament . It helps to bound the problem. You can easily show that there is

no solution for a number of weeks strictly greater than ten. This

follows from the fact that each player plays with three other players

each week, and since there is a total of 31 other players, this means

a player runs out of opponents after (31)/3 weeks. In this article, we

will see how to construct a nine-week schedule. Constructing a ten-week schedule or proving that none exists remains an open problem!

To solve the nine-week schedule problem, we will use
href="http://www.koalog.com/php/jcs.php">Koalog Constraint Solver,

a Java library for constraint programming, to write the code.

Information about Koalog Constraint Solver (including its JavaDoc) is

available at
href="http://www.koalog.com/php/jcs.php">www.koalog.com/php/jcs.php. All

of the techniques presented in this article do not depend on the choice

of the solver, but could be implemented using many commercial or

open source solvers.

## Constraint Programming

Constraint programming (CP) is a technique for solving

combinatorial problems such as the social golfer problem.

It consists of modelling the problem using mathematical relations or

constraints (precisely, the term *constraint* denotes the implementation

of the mathematical relation).

Hence, a constraint satisfaction problem (CSP) is defined by:

- A set of variables.
- A set of domains (possible values) for the variables.
- A set of constraints/relations on the variables.

One has to define a strategy for enumerating the

different solutions. CP differs from naive enumeration methods by the

fact that constraints contain powerful filtering algorithms (usually

inspired by *operational research* techniques) that will

drastically reduce the search space by dynamically reducing the

domains of the variables during the enumeration.

## Modeling the Golfers Problem

Let's first create a problem object that will be the placeholder for the

problem modelization. Using Koalog Constraint Solver, this can be done by

subclassing a `BaseProblem`

:

```
[prettify]
public class GolfersProblem extends BaseProblem {
public static final int GROUP_NB = 8;
public static final int GROUP_CARD = 4;
public static final int GOLFERS_NB =
GROUP_NB*GROUP_CARD;
// the forthcoming model will come here
}
</pre>
<p>We have defined some constants to make the code more readable, but
also because the problem can be generalized to various group numbers
and sizes. In the following, the number of weeks (<code>n
```

) will
be a parameter of the problem.

An important step in constraint programming is defining
the problem variables. In our case, we want to find, for each week,
the set of golfers playing in each group. Fortunately, Koalog
Constraint Solver comes with set variables (in addition to Boolean and
integer variables). Thus, it is possible to write:

SetVariable[ ][ ] group;
[/prettify]
where the instance variable `group`

will be indexed by weeks

(from 1 to `n`

) and then by groups

(from 1 to `GROUP_NB`

).

Note that it would also be possible to model the problem using integers

(defining, each week, for each golfer, the number of its group) or Booleans

(deciding, each week, whether a golfer belongs to a given group or not).

But a set-based representation is much more compact and powerful, since it

eliminates most of the problem symmetries.

We can now model our problem and define a `GolfersProblem`

constructor:

`public GolfersProblem(int n) {`

super();

group = new SetVariable[n][GROUP_NB];

Collection golfers = new ArrayList();

for (int i=1; i<=GOLFERS_NB; i++) {

golfers.add(new Integer(i));

}

List vars = new ArrayList();

// to be continued

}

The collection `golfers`

is the collection of all golfers

(identified here by a number from 1 to `GOLFERS_NB`

).

The list `vars`

will contain all

problem variables.

Each group variable is a set of four golfers:

```
[prettify]
for (int i=0; i<n; i++) {
for (int j=0; j<GROUP_NB; j++) {
group[i][j] =
new SetVariable(new SetDomain(Collections
.EMPTY_SET,
golfers));
add(new ConstantCard(GROUP_CARD,
group[i][j]));
vars.add(group[i][j]);
}
}
</pre>
<p>The domain <code>new SetDomain(Collections.EMPTY_SET, golfers)
```

states that the group is a set containing at least the empty set and
at most the set of all golfers (previously defined).
More generally, set domains are defined by two sets:

- A set of values that will be contained in the set; this set increases
with time and it is the lower bound (
*LB*) of the domain.
- A set of values containing the set, this set decreases
with time and it is the upper bound (
*UB*) of the domain.

For example, the set domain {1, 2, 3} denotes the sets containing at
least 1 and at most 1, 2, and 3: these are {1}, {1,2}, {1,3}, {1, 2, 3}.
A set domain is instantiated when the upper bound is equal to the
lower bound.

The constraint `ConstantCard`

states that the cardinality of the group
should be constant (here equal to `GROUP_CARD`

).

Each week the groups of golfers form a partition of the set of all golfers:

```
for (int i=0; i<n; i++) {
add(new Partition(group[i], golfers));
}
</pre>
<p>We want the golfers to be social. The intersection of two groups should
have at most one golfer in common:</p>
<pre> <code>
for (int i=0; i<n-1; i++) {
for (int l=i+1; l<n; l++) {
for (int j=0; j<GROUP_NB; j++) {
for (int k=0; k<GROUP_NB; k++) {
add(new IntersectionMaxSize(1,
group[i][j],
group[l][k]));
}
}
}
}
</pre>
<p>Finally, we define the array of variables to be displayed:</p>
<pre> <code>
setVariables((SetVariable[])vars
.toArray(new SetVariable[0]));
</pre>
<p>We are done with the modelling; the complete model can be found at
<a href="http://www.koalog.com/resources/samples/GolfersProblem.java">www.koalog.com/resources/samples/GolfersProblem.java</a>.</p>
<h2 id="solving">Solving the Golfers Problem</h2>
<p>Let's first create a solver object that will be the placeholder for the
strategy. Using Koalog Constraint Solver, this can be done by subclassing
a <code>BacktrackSolver
```

:
public class GolfersSolver extends BacktrackSolver {
SetVariable[][] group;
public GolfersSolver(GolfersProblem p) {
super(p);
this.group = p.group;
}
public boolean choice() {
// to be continued
}
}
[/prettify]
The `choice`

method will be responsible for making choices and thus build

a search tree, the nodes of which are called *choice points*. This method

will be called successively until all of the group variables are instantiated.

We add the golfers by numbers to the groups:

`for (int i=1; `

i<=GolfersProblem.GOLFERS_NB;

i++) {

Integer j = new Integer(i);

for (int d=0; d<group.length; d++) {

for (int g=0;

g<GolfersProblem.GROUP_NB;

g++) {

if (((SetDomain) group[d][g].getDomain())

.isPossibleElement(j)) {

choicePoints.push();

group[d][g]

.chooseMinByAdding(choicePoints,

constraintScheduler,

j);

return true;

}

}

}

}

return false;

If a golfer can be added to a group, a new node (choice point) is created

in the search tree and the method returns true. When no more golfers can be added, the method returns false.

The test `((SetDomain) group[d][g].getDomain()).isPossibleElement(j)`

returns true if golfer `j`

can be added to the group `group[d][g]`

.

Precisely, `isPossibleElement`

returns true if the element is contained

in the UB of the domain, but not in the LB. The method `chooseMinByAdding`

adds a new element to the set (increasing

its LB).

We are done with the strategy; the complete solver can be found at

www.koalog.com/resources/samples/GolfersSolver.java .

## Results

This strategy performs very well. Koalog Constraint Solver is able to find a

solution to the nine-week problem in 440ms (on a 1600Mhz PC with J2SE

1.4):

- Week 1: {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15,

16}, {17, 18, 19, 20}, {21, 22, 23, 24}, {25, 26, 27, 28}, {29, 30, 31, 32}
- Week 2: {1, 5, 9, 13}, {2, 6, 10, 14}, {3, 7, 11, 15}, {4, 8, 12, 16}, {17,

21, 25, 29}, {18, 22, 26, 30}, {19, 23, 27, 31}, {20, 24, 28, 32}
- Week 3: {1, 6, 11, 16}, {2, 5, 12, 15}, {3, 8, 9, 14}, {4, 7, 10, 13}, {17,

22, 27, 32}, {18, 21, 28, 31}, {19, 24, 25, 30}, {20, 23, 26, 29}
- Week 4: {1, 7, 17, 23}, {2, 8, 18, 24}, {3, 5, 19, 21}, {4, 6, 20, 22},

{9, 15, 25, 31}, {10, 16, 26, 32}, {11, 13, 27, 29}, {12, 14, 28, 30}
- Week 5: {1, 8, 19, 22}, {2, 7, 20, 21}, {3, 6, 17, 24}, {4, 5, 18, 23},

{9, 16, 27, 30}, {10, 15, 28, 29}, {11, 14, 25, 32}, {12, 13, 26, 31}
- Week 6: {1, 10, 18, 25}, {2, 9, 17, 26}, {3, 12, 20, 27}, {4, 11, 19, 28},

{5, 14, 22, 29}, {6, 13, 21, 30}, {7, 16, 24, 31}, {8, 15, 23, 32}
- Week 7: {1, 12, 21, 32}, {2, 11, 22, 31}, {3, 10, 23, 30}, {4, 9, 24, 29},

{5, 16, 17, 28}, {6, 15, 18, 27}, {7, 14, 19, 26}, {8, 13, 20, 25}
- Week 8: {1, 14, 20, 31}, {2, 13, 19, 32}, {3, 16, 18, 29}, {4, 15, 17, 30},

{5, 10, 24, 27}, {6, 9, 23, 28}, {7, 12, 22, 25}, {8, 11, 21, 26}
- Week 9: {1, 15, 24, 26}, {2, 16, 23, 25}, {3, 13, 22, 28}, {4, 14, 21, 27},

{5, 11, 20, 30}, {6, 12, 19, 29}, {7, 9, 18, 32}, {8, 10, 17, 31}

Precisely, only 32 nodes are explored in the search tree. This is to compare

with the huge size of the search tree (32!^9).

It is also interesting to notice that local search methods perform poorly on

this problem.

Of course, this model can be generalized to arbitrary numbers of groups and

golfers, and it is also possible to add side constraints such as *Golfer 1*

and Golfer 2 would like to golf together on week 1.

width="1" height="1" border="0" alt=" " /> |