Formal Definition: Modified Social Golfer Problem
Givenwrounds, develop a schedule that minimizes the number of missed pairings whenmmembers of a set are divided intoggroups of sizes(m = g * s).
Secondary objective: Minimize the number of times members are paired overwrounds .
[ Our tug a war, have 90 days to do up to several rounds up to 10 per day, so my wis ?]
[my (m=g*s) is 54=9*6]
Practical Application:
Scheduling a golf outing with the objective of creating 4-somes which pair every golfer with every other golfer in the minimum number of rounds.[Tug a war is a 6-somes]
Scheduling pairings of couples in a dinner club. For example, schedule 15 couples where 3 couples are paired up and trade off hosting dinners. The pairings are then redone so that couples are paired with all other couples in the minimum number of re-pairings.
Related Problem: Social Golfer Problem
Scheduleg*sgolfers intoggroups ofsplayers over w weeks, such that no golfer plays in the same group with any other golfer more than just once. The problem can be looked at as an optimization problem if for two given numbersgandswe ask for the maximum number of weeks the golfers can play together.
Note:The Social Golfer problem is a maximization problem while the Modified Social Golfer problem is a minimization problem. If the modified social golfer problem results in a perfect pairing, this also solves the same solution as the equivalent social golfer problem.
Solution Representation
A solution to the modified social golfer problem can be depicted by identifying pairings of numbered golfers. For example, the optimal solution to the 4 round, 3 groups or size 3 problem is shown below with the pairings listed on each row, and rounds seperated by a blank line.
[Tug a Warhas g at 9, and the size at 6, so our W is not in weeks, but in days with multiple rounds in that day, we have max of 90 days with 7-10 rounds in each day. So what ever we need to achieve the w to go with our set g (9) and s (6).]
w-g-s
4-3-3
Best Schedule
6 4 8
3 9 7
5 1 2
1 8 3
4 2 9
5 7 6
1 9 6
4 3 5
8 7 2
9 5 8
4 7 1
6 3 2
The evaluation of a schedule can be presented as a symmetical matrix listing the pairings. The evaluation matrix for the 4-3-3 best solution is given below. Each golfer is paired with one and only one golfer each round. This is known as a perfect pairing.
0 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1
1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 0
Missed pairings = 0 Max pairing = 1
Missed pairings is the number of golfers which are never paired with another golfer - the Primary objective. This value is determined by counting the number of 0's in the evaluation matrix, not including the diaganol, then dividing by 2. In otherwords, the number of 0's in the upper right hand triangle, not including the diaganol.
Max pairing is the greatest number of rounds for which one golfer is paired with another specific golfer - the Secondary objective. This value is the maximum value in the evaluation matrix. Valid range [1,w]
Solutions to Common Problems
4-3-3
6-4-3
7-5-3
9-6-3
4-3-4
5-3-4
5-4-4
6-4-4
7-4-4
8-4-4
7-5-4
8-5-4
8-6-4
9-6-4