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.

## No comments:

## Post a Comment