> 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;
* check
parameter 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 1
golfer1 .group5 1 1
golfer2 .group1 1 1
golfer2 .group3 1
golfer2 .group5 1
golfer3 .group1 1
golfer3 .group2 1
golfer3 .group4 1
golfer3 .group7 1
golfer4 .group1 1
golfer4 .group4 1
golfer4 .group6 1
golfer4 .group7 1
golfer5 .group2 1
golfer5 .group5 1
golfer5 .group7 1 1
golfer6 .group1 1
golfer6 .group2 1 1 1
golfer7 .group1 1
golfer7 .group2 1
golfer7 .group3 1
golfer7 .group6 1
golfer8 .group2 1
golfer8 .group4 1 1
golfer8 .group7 1
golfer9 .group3 1 1
golfer9 .group4 1
golfer9 .group7 1
golfer10.group1 1
golfer10.group2 1
golfer10.group3 1
golfer10.group7 1
golfer11.group3 1 1
golfer11.group6 1
golfer11.group7 1
golfer12.group3 1 1
golfer12.group4 1 1
golfer13.group4 1
golfer13.group6 1 1 1
golfer14.group3 1 1
golfer14.group4 1
golfer14.group7 1
golfer15.group1 1 1
golfer15.group4 1 1
golfer16.group2 1
golfer16.group4 1
golfer16.group5 1 1
golfer17.group3 1
golfer17.group4 1
golfer17.group5 1 1
golfer18.group1 1
golfer18.group3 1
golfer18.group5 1
golfer18.group6 1
golfer19.group2 1
golfer19.group4 1
golfer19.group5 1
golfer19.group6 1
golfer20.group2 1
golfer20.group5 1 1
golfer20.group7 1
golfer21.group2 1
golfer21.group3 1 1
golfer21.group6 1
golfer22.group2 1 1
golfer22.group6 1 1
golfer23.group1 1 1
golfer23.group4 1
golfer23.group6 1
golfer24.group4 1
golfer24.group5 1 1
golfer24.group6 1
golfer25.group3 1
golfer25.group5 1
golfer25.group6 1
golfer25.group7 1
golfer26.group1 1
golfer26.group5 1
golfer26.group6 1
golfer26.group7 1
golfer27.group1 1
golfer27.group7 1 1 1
golfer28.group2 1 1
golfer28.group6 1
golfer28.group7 1
No comments:
Post a Comment