010: Social Golfers Problem

In sci.op-research, bigwind777@aol.com (Bigwind777) writes:
>
> I have 32 golfers, individual play.
> We will golf for 16 weeks.
> I want to set up the foursomes so each person only golfs
> with the same person once.
> How many weeks can we do this before it starts to duplicate ?

The structure of the problem is similar to the `progressive party
problem' (see Smith et. al in "Constraints" Vol 1.), let's take a
similar approach for modeling it.

We can specify the problem using a 0-1 integer linear program which
uses the 0-1 variables P[i,f,t]=1 iff player i plays in foursome f in
week t. Then, we can post constraints on these variables that define
the problem.
    To formulate the meet-only-once restriction, one can use auxiliary
variables M[i,j,t]=1 if player i and j meet in week t (i.e. if they
play in the same foursome).

With these variables, one can state the problem using an algebraic
modeling language. For example, an AMPL model of the golf problem
looks like

  #   AMPL model of `Maximum socializing on the golf course'
  #   June 8, 1998, J.P. Walser, Programming Systems Lab

  set Players ordered := { 1..32 } ;
  set Foursomes ordered := { 1..card(Players)/4 };
  set Weeks ordered := { 1..8 } ;

  ### Variables

  # variable P[i,j,t] means i plays in foursome j in week t
  var P { Players, Foursomes, Weeks } binary;

  # auxiliary variable M[i,j,t] means i meets j in week t (i<j)
  var M { Players, Players, Weeks } binary;


  ### Constraints

  # each player is part of exactly one foursome in each week
  subject to OF { i in Players, t in Weeks }:
	  sum { f in Foursomes }  P[i,f,t] = 1;

  # each foursome has exactly four players
  subject to FP { f in Foursomes, t in Weeks }:
	  sum { i in Players }  P[i,f,t] = 4;


  # link the M and P variables
  subject to LMP { i in Players, j in Players, f in Foursomes, t in Weeks: i<j }:
	  P[i,f,t]+P[j,f,t] - M[i,j,t] <= 1;

  # each pair of players only meets once
  subject to MO { i in Players, j in Players: i<j }:
	  sum { t in Weeks } M[i,j,t] <= 1;

  # fix first round and some symmetry
  fix { p in Players } P[p,int((p-1)/4)+1,1] := 1;
  fix { p in Players, t in Weeks: t >= 2 and p <= 4 } P[p,p,t] := 1;

Spelled out, the above model has 5152 Boolean variables and 22652
constraints.


Having stated the problem, we can try to solve it.  From experience,
we know that these kind of timetabling problems are typically very
difficult for 0-1 integer programming solvers (see e.g. the
Progressive Party Problem study).  So let's approach the problem using
a local search heuristic (called Wsat(PB)) which can interface with
AMPL to solve the 0-1 problem. Wsat(PB) is described in a AAAI97 paper
"Solving Linear Pseudo-Boolean Constraint Problems with Local Search."

An 8 week solution is:

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

     foursome 5    foursome 6    foursome 7    foursome 8
    17 18 19 20   21 22 23 24   25 26 27 28   29 30 31 32
     5 11 28 29    9 16 20 32    7 14 18 22    8 10 21 27
    13 20 21 29    6 12 28 32    7 11 16 17    8 15 18 26
     7 10 19 26    5 17 21 25   11 13 18 31    6 20 24 30
     6 13 22 27   14 24 25 32    7 15 21 28    5 10 16 31
     8  9 28 31    7 12 23 27    5 13 24 26   16 18 21 30
    15 17 27 29    5 14 20 23   10 18 24 28   12 19 21 31
    10 22 25 29   13 19 28 30    6  9 17 23   11 14 21 26

I don't know if there exists a fast combintorial scheme to construct
such a plan.  I used a method that solves the problem from a
delcarative model.  It finds 7-week solutions quickly (around 30s),
and an 8-week solution after several hours.

(Even if there was an efficient scheme, the problem would become a
difficult search problem in the presence of additional side
constraints, e.g. "never play in a foursome with the two strogenst
players in two successive weeks".)

Local search can generally not tell us when there isn't a solution
(it's an `incomplete' strategy), but often it is efficient in finding
solutions when they exist.

As an upper bound, we know that there cannot be a timetable with more
than 10 weeks. This is because the initial set of possible player-
combinations contains (32 choose 2)=496 elements. With each foursome,
we remove exactly 6 player-combinations from this set. Since each week
has 8 foursomes there are at most 496/(6*8)=10.33 weeks that our
reservoir of player-combinations will have enough supply for.  (This
can also be proved autmatically: If one attempts to solve the LP
relaxation of the above integer program for 11 weeks, CPLEX returns
`infeasible' after 1000s.)

Using this fact, we know that can do almost as well by solving the
problem for 16 time periods such that no two players meet more than
_twice_.  It is interesting that dispite the size of this problem (11K
vars, 48K constraints), it is considerably easier to solve than the
8-weeks problem.  We can get a solution from integer local search
Wsat(PB) in about 40s. Of course, now two players might meet twice in
a row.

Joachim P. Walser ( http://www.ps.uni-sb.de/~walser )