118 views

Skip to first unread message

Jun 8, 2008, 3:57:04 PM6/8/08

to

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

combination. I realize not everyone can play together. Anyone with

help? Thanks

Jun 8, 2008, 6:45:02 PM6/8/08

to

gilber...@comcast.net wrote:

> I have 28 golfers playing over four days in foursomes.

> I have 28 golfers playing over four days in foursomes.

Four day tournament (everyone plays each day) or each foursome plays

just one day (and only one foursome per day)?

> I want the best combination.

Best in terms of what criterion?

> I realize not everyone can play together.

Because some of them might swing their clubs at each other rather than

at the balls? Or as a matter of scheduling?

/Paul

Jun 9, 2008, 8:33:03 AM6/9/08

to

I suggest you start by grouping golfers with similar handicaps. There

may be other criteria required - e.g. one company representative for

every three customers - in which case put the strongest

representatives with the strongest customers.

Also, it would be worthwhile to avoid grouping stuffy "must follow

every rule to the letter" types with people who want to enjoy their

game.

Might get more (and better) suggestions by going to a golf forum.

Jun 9, 2008, 6:12:53 PM6/9/08

to er...@gams.com

See also the social golfer problem http://www.cs.brown.edu/~sello/golf.html.

The difficult problem mentioned there has been solved using some

alternative 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

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 day'

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 day

*

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 n=maxmeet times

*

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 the 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

---- 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

----------------------------------------------------------------

Erwin Kalvelagen

Amsterdam Optimization Modeling Group

erwin.ka...@gmail.com, http://www.gams.com/~erwin

http://amsterdamoptimization.com

----------------------------------------------------------------

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu