Monday, February 2, 2009

Social Golfer Problem in OML (2)

In the earlier post we used binary variables x[i,g,t] to model that golfer i plays in group g at round t. Here we show that using CSP constructs it is actually easy to use a different formulation:  x[i,t]=g. I.e. x[i,t] is an integer variable. In a MIP context this would be much more difficult to do.


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],
// Parameters[Integers,N=32,NG=8,T=10,GS=4],

Decisions[
Integers[0,NG-1],
Foreach[{i,N},{t,T},x[i,t]]
],


Constraints[

// form groups
Foreach[{g,NG},{t,T},Sum[{i,N},AsInt[x[i,t]==g]] == GS],

// golfer i and j meet at most one time
Foreach[{i,N}, {j,i+1,N}, Sum[{t,T},AsInt[x[i,t]==x[j,t]]] <= 1],

// fix first round
Foreach[{g,NG},{k,GS},x[GS*g+k,0]==g],

// fix first golfer
Foreach[{t,1,T},x[0,t]==0]
]

]