Sunday, January 18, 2009

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.