Social Golfer Problem in OML

I am recently involved in a practical application of a scheduling problem related to the Social Golfer Problem. The particular application is somewhat more complicated, but we could use the GAMS/Cplex model described here as a starting point.

For smaller instances of the pure Social Golfer Problem, it is convenient to use a CSP approach. Here is a formulation in OML (Microsoft Solver Foundation):

Model[
 
// N : number of golfers
// NG : number of groups
// T : number of rounds
// GS : group size (N/NG)
 
 Parameters[Integers,N=16,NG=4,T=5,GS=4],
 // Would prefer: GS=N/NG but OML does not allow (constant) expressions
 // in parameter statements
 
 Decisions[
  Integers[0,1],
   Foreach[{i,N},{g,NG},{t,T},x[i,g,t]]
 ],
 
  
 Constraints[
     // each golfer has to play each round
     Foreach[{i,N},{t,T},Sum[{g,NG},x[i,g,t]] == 1],
 
     // form groups
     Foreach[{g,NG},{t,T},Sum[{i,N},x[i,g,t]] == GS],
 
     // golfer i and j meet at most one time
     // Foreach[{i,N}, FilteredForeach[{j,N},i!=j, Sum[{g,NG},{t,T},x[i,g,t]*x[j,g,t]] <= 1]],
     // We exploit symmetry here:
     Foreach[{i,N}, Foreach[{j,i+1,N}, Sum[{g,NG},{t,T},x[i,g,t]*x[j,g,t]] <= 1]],
 
 
     // fix first round
     Foreach[{g,NG},{k,GS},x[GS*g+k,g,0]==1],
 
     // fix first golfer
     Foreach[{t,1,T},x[0,0,t]==1]
 ]
 
]

The condition on number of times players can meet can be implemented quite straightforwardly. In the MIP model we needed to linearize this constraint, but in the CSP framework we can use the nonlinear formulation directly. A big advantage of CSP over MIP is that many constructs can be modeling in a more natural, straightforward fashion. Note that we added some exploitation of symmetry: once we have checked how many times golfer i meets golfer j we no longer need to check golfer j meeting golfer i.

The last two constraints fix the first round and first player. This (without loss of generality) reduces the size of the problem.

This instance solved easily:

Solver Foundation Report       
Report Overview       
Date Time    =    1/18/09 10:48 AM
Model Name    =    golf.xlsx
Solver Selected    =    CSP
Total Time (ms)    =    677
Solver Completion Status    =    Feasible
       
Solver Execution Details       
Algorithm    =    Tree Search
Variable Selection    =    Dynamic Weighting
Value Selection    =    Forward Order

Note that we changed the default solver algorithm settings to speed up the solution times.

The most interesting instance with 32 golfers, foursomes and T=10 is too large for my version to solve:

Parameters[Integers,N=32,NG=8,T=10,GS=4],
 
 
Error:
Model size limit has been exceeded for this version of the product. Please contact Microsoft Corporation for licensing options.