Scott R. Schultz: Modified Social Golfer Templates

 

Formal Definition: Modified Social Golfer Problem

Given w rounds, develop a schedule that minimizes the number of missed pairings when m members of a set are divided into g groups of size s (m = g * s).

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.

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

Schedule g*s golfers into g groups of s players 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 numbers g and s we ask for the maximum number of weeks the golfers can play together.

See Sellman, M., http://www.cs.brown.edu/~sello/golf.html

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.

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

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
7-5-4
8-6-4
9-6-4
 

w-g-s
6-4-3

Best Schedule
12 3 7
9 2 6
5 1 4
10 11 8

4 9 7
12 8 1
11 6 5
2 3 10

9 10 5
6 1 3
2 7 8
4 12 11

2 4 3
12 10 6
5 11 7
9 1 8

2 1 11
5 3 8
9 12 6
7 10 4

8 6 4
3 9 11
7 10 1
2 5 12

Evaluation Matrix
0 1 1 1 1 1 1 2 1 1 1 1
1 0 2 1 1 1 1 1 1 1 1 1
1 2 0 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 2 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 2 1
1 1 1 1 1 0 0 1 2 1 1 2
1 1 1 2 1 0 0 1 1 2 1 1
2 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 2 1 1 0 1 1 1
1 1 1 1 1 1 2 1 1 0 1 1
1 1 1 1 2 1 1 1 1 1 0 1
1 1 1 1 1 2 1 1 1 1 1 0

Missed pairings = 1

 

w-g-s
7-5-3

Best Schedule
5 11 4
9 12 6
8 1 14
10 3 2
15 13 7

9 10 13
1 7 2
11 8 12
6 3 5
4 14 15

8 3 13
15 10 11
7 12 5
4 9 1
14 6 2

6 15 8
9 5 2
12 4 13
10 14 7
1 11 3

6 7 11
12 1 10
4 2 8
13 14 5
3 15 9

3 4 7
10 5 8
13 1 6
11 9 14
12 2 15

2 13 11
5 1 15
10 6 4
8 9 7
12 3 14

Evaluation Matrix

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

Missed pairings = 0

w-g-s
9-6-3

Best Schedule
18 13 7
8 10 15
6 17 9
1 16 14
4 5 12
11 2 3

1 9 15
6 11 12
2 18 5
16 8 13
4 17 7
3 14 10

3 4 1
17 5 11
9 10 13
7 16 6
2 15 14
18 12 8

17 14 13
18 3 8
9 12 5
10 15 6
4 2 16
7 11 1

3 17 15
13 5 1
7 12 14
2 8 6
16 9 18
10 11 4

1 10 12
18 14 11
15 7 5
4 13 6
16 3 17
9 8 2

11 15 13
1 18 6
8 14 4
3 7 9
17 2 12
10 16 5

1 8 17
18 15 4
3 13 12
7 2 10
14 5 6
16 9 11

13 1 2
15 16 12
3 5 6
8 11 7
17 10 18
4 14 9

Evaluation Matrix
0 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1
1 0 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1
1 1 1 0 1 1 1 1 1 1 1 1 1 2 1 1 1 1
1 1 1 1 0 2 1 0 1 1 1 2 1 1 1 1 1 1
1 1 1 1 2 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 2 1 1 1 1 1 1 1
1 2 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 2 1 1 1
1 1 1 1 1 1 2 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 2 1 1 1 1 1 1 0 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 2 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1
1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 0

Missed pairings = 1

w-g-s
4-3-4

Best Schedule
5 3 7 8
4 9 10 2
12 6 11 1

11 7 10 8
1 2 6 3
9 5 4 12

9 11 3 4
2 7 12 8
5 1 6 10

12 10 3 4
11 5 2 6
1 7 9 8

Evaluation Matrix
0 1 1 0 1 3 1 1 1 1 1 1
1 0 1 1 1 2 1 1 1 1 1 1
1 1 0 2 1 1 1 1 1 1 1 1
0 1 2 0 1 0 0 0 3 2 1 2
1 1 1 1 0 2 1 1 1 1 1 1
3 2 1 0 2 0 0 0 0 1 2 1
1 1 1 0 1 0 0 4 1 1 1 1
1 1 1 0 1 0 4 0 1 1 1 1
1 1 1 3 1 0 1 1 0 1 1 1
1 1 1 2 1 1 1 1 1 0 1 1
1 1 1 1 1 2 1 1 1 1 0 1
1 1 1 2 1 1 1 1 1 1 1 0

Missed pairings = 7

w-g-s
5-3-4

Best Schedule
5 6 3 7
11 12 4 10
9 8 2 1

4 5 8 1
7 11 2 3
9 12 6 10

9 7 8 11
4 1 3 6
5 10 12 2

8 9 3 6
5 2 4 11
7 1 12 10

2 11 1 6
5 4 9 7
8 12 10 3

Evaluation Matrix
0 2 1 2 1 2 1 2 1 1 1 1
2 0 1 1 2 1 1 1 1 1 3 1
1 1 0 1 1 3 2 2 1 1 1 1
2 1 1 0 3 1 1 1 1 1 2 1
1 2 1 3 0 1 2 1 1 1 1 1
2 1 3 1 1 0 1 1 2 1 1 1
1 1 2 1 2 1 0 1 2 1 2 1
2 1 2 1 1 1 1 0 3 1 1 1
1 1 1 1 1 2 2 3 0 1 1 1
1 1 1 1 1 1 1 1 1 0 1 5
1 3 1 2 1 1 2 1 1 1 0 1
1 1 1 1 1 1 1 1 1 5 1 0

Missed pairings = 0

w-g-s
5-4-4

Best Schedule
5 15 7 11
10 12 13 8
6 16 2 9
4 1 3 14

15 8 2 4
11 1 12 16
10 9 5 14
13 6 7 3

10 11 4 6
1 15 13 9
12 2 5 3
16 7 14 8

4 9 7 12
2 13 11 14
6 5 8 1
10 3 15 16

2 7 1 10
5 4 16 13
3 9 8 11
15 14 12 6

Evaluation Matrix
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

Missed pairings = 0

w-g-s
7-5-4

Best Schedule
13 19 10 14
7 1 2 18
8 4 11 5
6 16 17 20
12 15 9 3

2 3 11 14
12 17 18 10
8 15 20 19
13 7 6 5
1 9 4 16

5 17 15 2
10 8 16 7
20 13 3 4
9 19 18 11
1 12 14 6

9 6 5 7
17 4 10 18
8 12 2 13
1 15 19 20
14 3 11 16

17 14 9 8
20 7 12 11
3 1 5 10
13 16 15 18
4 19 6 2

4 7 15 14
13 1 11 17
18 6 8 3
16 12 19 5
2 9 20 10

17 19 7 3
20 5 18 14
11 15 6 10
2 12 4 16
8 1 13 9

Evaluation Matrix
0 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 1 1 1 1
1 0 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 2 1 1 2 1 1 1 1 1 1
1 2 1 0 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1
1 1 1 1 0 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 2 0 2 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 2 2 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 2 1 1 1 2 1 1 1 1 1 1 1
2 1 1 1 1 1 1 2 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 2 2 1 1
1 1 2 1 1 1 1 1 1 1 0 1 1 2 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1 1 0 1 1 1 2 1 1 1 1
2 1 1 1 1 1 1 2 1 1 1 1 0 1 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1 2 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 2 2
1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 0 2 1 1
1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 0 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 0

Missed pairings = 0

w-g-s

w-g-s
9-6-4

Best Schedule
18 21 3 15
12 13 7 6
20 19 9 22
2 14 4 16
24 1 8 10
23 5 17 11

6 9 18 17
1 20 10 14
8 16 19 3
22 12 24 11
2 5 7 15
4 21 13 23

24 14 18 19
7 22 8 21
3 17 1 13
12 20 23 15
16 5 10 9
4 2 11 6

22 1 18 5
9 23 8 3
14 6 10 15
17 4 12 19
7 16 21 11
24 20 2 13

4 18 11 8
15 13 9 22
7 19 1 23
17 20 16 14
21 10 12 2
5 3 6 24

23 3 22 2
8 12 1 5
17 4 24 15
10 7 20 18
11 21 9 14
6 13 16 19

18 2 9 1
8 20 11 13
12 14 7 3
5 15 19 21
16 23 24 6
10 17 22 4

20 5 3 4
24 17 7 21
9 19 12 2
13 18 10 23
11 15 16 1
6 22 8 14

8 2 17 15
19 11 3 10
22 16 18 12
4 7 24 9
21 6 20 1
23 14 13 5

Evaluation Matrix
0 1 1 0 2 1 1 2 1 2 1 1 1 1 1 1 1 2 1 2 1 1 1 1
1 0 1 2 1 1 1 1 2 1 1 2 1 1 2 1 1 1 1 1 1 1 1 1
1 1 0 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1
0 2 1 0 1 1 1 1 1 1 2 1 1 1 1 1 3 1 1 1 1 1 1 2
2 1 2 1 0 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1
1 1 1 1 1 0 1 1 1 1 1 1 2 2 1 2 1 1 1 1 1 1 1 2
1 1 1 1 1 1 0 1 1 1 1 2 1 1 1 1 1 1 1 1 3 1 1 2
2 1 2 1 1 1 1 0 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1
1 2 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 2 2 1 1 2 1 1
2 1 1 1 1 1 1 1 1 0 1 1 1 2 1 1 1 2 1 2 1 1 1 1
1 1 1 2 1 1 1 2 1 1 0 1 1 1 1 2 1 1 1 1 2 1 1 1
1 2 1 1 1 1 2 1 1 1 1 0 1 1 1 1 1 1 2 1 1 2 1 1
1 1 1 1 1 2 1 1 1 1 1 1 0 1 1 1 1 1 1 2 1 1 3 1
1 1 1 1 1 2 1 1 1 2 1 1 1 0 1 2 1 1 1 2 1 1 1 1
1 2 1 1 2 1 1 1 1 1 1 1 1 1 0 1 2 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1 2 1 1 2 1 0 1 1 2 1 1 1 1 1
1 1 1 3 1 1 1 1 1 1 1 1 1 1 2 1 0 1 1 1 1 1 1 2
2 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 0 1 1 1 2 1 1
1 1 2 1 1 1 1 1 2 1 1 2 1 1 1 2 1 1 0 1 1 1 1 1
2 1 1 1 1 1 1 1 1 2 1 1 2 2 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 3 1 1 1 2 1 1 1 2 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 2 2 1 1 2 1 1 1 1 1 2 1 1 1 0 1 1
1 1 2 1 2 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 0 1
1 1 1 2 1 2 2 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 0

Missed pairings = 1