## Monday, June 9, 2008

### A variant of the social golfer problem

> I have 28 golfers playing over four days in foursomes. I want the best
> combination. I realize not everyone can play together. Anyone with
> help? Thanks

See also the social golfer problem http://www.cs.brown.edu/~sello/golf.html.The difficult problem mentioned there has been solved using somealternative mathematical method (I forgot the details).

Analog to this problem we can minimize the number of times player A can meet player B. If this becomes 1 no player meet another player more than once.

I formulated this quickly in GAMS:

``\$ontext  I have 28 golfers playing over four days in foursomes. I want the best combination. I realize not everyone can play together. Anyone with help? Thanks    References:     - problem 10 in CSPLIB (www.csplib.org)     - Barbara Smith, "Reducing Symmetry in a Combinatorial       Design Problem", Tech. Report, School of Computing and       Mathematics, University of Huddersfield, 2001.  \$offtext  set   t  'days'   /day1*day4/   i  'golfers' /golfer1*golfer28/   g  'group'   /group1*group7/; alias(i,j); binary variables    x(i,g,t)      'schedule';positive variable   meet(i,j,g,t) 'golfer i and j meet';free variables      maxmeet       'max number of times players meet'; equations    game(i,t)          'each golver plays one game per week'    fourplayer(g,t)    'four players per game'    multiply1(i,j,g,t) 'linearization of multiplication (not used)'    multiply2(i,j,g,t) 'linearization of multiplication (not used)'    multiply3(i,j,g,t) 'linearization of multiplication'    meetcount(i,j); set ij(i,j);ij(i,j)\$(ord(i)>ord(j)) = yes;  ** golfer plays one game per week*game(i,t).. sum(g, x(i,g,t)) =e= 1; ** four players per game*fourplayer(g,t).. sum(i, x(i,g,t)) =e= 4; ** linearization of x(i,g,t)*x(j,g,t)* Note: we can relax the first two equations multiply1, multiply2*multiply1(ij(i,j),g,t).. meet(ij,g,t) =l= x(i,g,t);multiply2(ij(i,j),g,t).. meet(ij,g,t) =l= x(j,g,t);multiply3(ij(i,j),g,t).. meet(ij,g,t) =g= x(i,g,t)+x(j,g,t)-1; meet.lo(ij,g,t) = 0;meet.up(ij,g,t) = 1; ** players i and j can meet only once*meetcount(ij(i,j)).. sum((g,t), meet(ij,g,t)) =l= maxmeet;   ** fix first round*set first(i,g) /  (golfer1*golfer4).group1  (golfer5*golfer8).group2  (golfer9*golfer12).group3  (golfer13*golfer16).group4  (golfer17*golfer20).group5  (golfer21*golfer24).group6  (golfer25*golfer28).group7/;x.fx(first,'day1') = 1; model m /game,fourplayer,multiply3,meetcount/;solve m minimizing maxmeet using mip; * checkparameter meetcount2(i,j) "sanity check";meetcount2(i,j)\$(not sameas(i,j)) = round(sum((g,t),x.l(i,g,t)*x.l(j,g,t)));option meetcount2:0:1:1;display meetcount2; options x:0:2:1;display x.l; ``

This gave a solution within 11 seconds using Cplex:

``              S O L V E      S U M M A R Y     MODEL   m                   OBJECTIVE  maxmeet    TYPE    MIP                 DIRECTION  MINIMIZE    SOLVER  CPLEX               FROM LINE  87 **** SOLVER STATUS     1 NORMAL COMPLETION**** MODEL STATUS      1 OPTIMAL**** OBJECTIVE VALUE                1.0000  RESOURCE USAGE, LIMIT         10.924      1000.000 ITERATION COUNT, LIMIT     28252         10000``

with the following schedule:

``----     96 VARIABLE x.L  schedule                       day1        day2        day3        day4 golfer1 .group1           1                                   1golfer1 .group5                       1           1golfer2 .group1           1           1golfer2 .group3                                   1golfer2 .group5                                               1golfer3 .group1           1golfer3 .group2                                               1golfer3 .group4                       1golfer3 .group7                                   1golfer4 .group1           1golfer4 .group4                                   1golfer4 .group6                       1golfer4 .group7                                               1golfer5 .group2           1golfer5 .group5                       1golfer5 .group7                                   1           1golfer6 .group1                                               1golfer6 .group2           1           1           1golfer7 .group1                       1golfer7 .group2           1golfer7 .group3                                               1golfer7 .group6                                   1golfer8 .group2           1golfer8 .group4                                   1           1golfer8 .group7                       1golfer9 .group3           1           1golfer9 .group4                                               1golfer9 .group7                                   1golfer10.group1                                   1golfer10.group2                       1golfer10.group3           1golfer10.group7                                               1golfer11.group3           1                       1golfer11.group6                                               1golfer11.group7                       1golfer12.group3           1                                   1golfer12.group4                       1           1golfer13.group4           1golfer13.group6                       1           1           1golfer14.group3                       1           1golfer14.group4           1golfer14.group7                                               1golfer15.group1                       1           1golfer15.group4           1                                   1golfer16.group2                       1golfer16.group4           1golfer16.group5                                   1           1golfer17.group3                                   1golfer17.group4                                               1golfer17.group5           1           1golfer18.group1                                   1golfer18.group3                                               1golfer18.group5           1golfer18.group6                       1golfer19.group2                                   1golfer19.group4                       1golfer19.group5           1golfer19.group6                                               1golfer20.group2                                               1golfer20.group5           1                       1golfer20.group7                       1golfer21.group2                                   1golfer21.group3                       1                       1golfer21.group6           1golfer22.group2                       1                       1golfer22.group6           1                       1golfer23.group1                                   1           1golfer23.group4                       1golfer23.group6           1golfer24.group4                                   1golfer24.group5                       1                       1golfer24.group6           1golfer25.group3                       1golfer25.group5                                               1golfer25.group6                                   1golfer25.group7           1golfer26.group1                       1golfer26.group5                                   1golfer26.group6                                               1golfer26.group7           1golfer27.group1                                               1golfer27.group7           1           1           1golfer28.group2                                   1           1golfer28.group6                       1golfer28.group7           1``