🧩 Constraint Solving POTD:Social Golfer Problem

[github-actions[bot]]

Category: Classic CSP · Date: 2026-03-28

---

Problem Statement

The setup: A group of n = g × p golfers wants to play golf for w weeks. Each week, all n golfers are divided into g groups of exactly p players. The challenge: arrange the schedule so that no two golfers ever play together in the same group more than once across all w weeks.

Formally: Given integers g (groups per week), p (players per group), and w (weeks), find an assignment of golfers to groups for each week — or prove none exists.

A small concrete instance (4-3-3):

• g = 4 groups, p = 3 players each, so n = 12 golfers (label them 0–11)
• w = 3 weeks
• One valid schedule:

Week	Group 1	Group 2	Group 3	Group 4
1	{0,1,2}	{3,4,5}	{6,7,8}	{9,10,11}
2	{0,3,6}	{1,4,9}	{2,7,10}	{5,8,11}
3	{0,4,8}	{1,5,6}	{2,9,11}	{3,7,10}

Each pair of golfers shares a group in at most one week across all three weeks.

Input/Output specification:

• Input: (g, p, w)
• Output: A valid w-week schedule (a 3D assignment group[week][slot] ∈ {0..n-1}), or UNSAT if none exists
• Optimization variant: maximize w subject to the no-repeat-pair constraint

Theoretical upper bound: Each golfer plays with p-1 others per week. Over w weeks that's w(p-1) different partners. There are only n-1 = gp-1 other golfers, so w ≤ (gp-1)/(p-1). Achieving this bound corresponds to a resolvable design in combinatorics.

---

Why It Matters

Sports scheduling & round-robin tournaments. The social golfer pattern underpins any round-robin scheduling where diversity of matchups matters — tennis ladder leagues, bridge tournaments, and sports drafts all benefit from maximizing pairwise encounters without overrepetition.

Frequency assignment & experiment design. In antenna frequency planning, distinct "groups" represent spectrum slots and "golfers" are transmitters; the no-repeat-pair constraint prevents co-channel interference across time slots. In statistics, the problem maps onto balanced incomplete block designs (BIBDs), which ensure each experimental treatment pair appears together exactly once for unbiased comparisons.

Benchmark for CP solvers. The Social Golfer Problem is a standard CSP benchmark — instances like 5-3-7 (15 golfers, 7 weeks) have been used to stress-test propagation engines, symmetry-breaking techniques, and portfolio solvers since the early 2000s.

---

Modeling Approaches

Approach 1 — Constraint Programming (Set Variables)

Decision variables:

• S[w][g] = set of p golfers in group g during week w (set variable, cardinality p)

Constraints:

// Partition constraint: each week is a partition of all golfers
∀w: partition({S[w][1], ..., S[w][g]})

// No-repeat-pair constraint: any two groups from different weeks share at most 1 golfer
∀ w1 ≠ w2, ∀ g1, g2: |S[w1][g1] ∩ S[w2][g2]| ≤ 1
```

**Trade-offs:** Set variables with cardinality constraints give a very natural model. The `partition` global constraint is highly propagated. The intersection bound `≤ 1` can be encoded with a dedicated *intersection* global constraint or decomposed into element constraints. Symmetry is high — see Key Techniques below.

---

#### Approach 2 — Boolean / Integer Programming (Matrix Model)

**Decision variables:**  
- `x[w][i][j] ∈ {0,1}` — golfer `j` is in group `i` during week `w`

**Constraints:**
```
// Each golfer appears in exactly one group per week
∀w, ∀j: Σ_i x[w][i][j] = 1

// Each group has exactly p golfers
∀w, ∀i: Σ_j x[w][i][j] = p

// No two golfers j1 ≠ j2 share a group in more than one week
∀ j1<j2: Σ_w Σ_i ( x[w][i][j1] · x[w][i][j2] ) ≤ 1
```

The last constraint is **quadratic** in the binary variables; it linearizes to:

```
∀ w, i, j1<j2: y[w][i][j1][j2] ≥ x[w][i][j1] + x[w][i][j2] - 1
∀ j1<j2:       Σ_w Σ_i y[w][i][j1][j2] ≤ 1

Trade-offs: The MIP formulation is mechanically straightforward but introduces O(n²gw) auxiliary variables for the pair indicator, making it large even for modest instances. LP relaxations are weak. CP models with global constraints typically dominate on feasibility.

---

Approach 3 — SAT Encoding (Sparse at-most-one)

Encode x[w][i][j] as Boolean literals. The at-most-one (AMO) "two golfers share group" constraints are encoded using commander variable or product encoding to keep clause count polynomial. A CDCL SAT solver then finds solutions or proves unsatisfiability. This is competitive on proving UNSAT for hard instances near the theoretical upper bound.

Example Model — MiniZinc (CP, set-based)

include "globals.mzn";

int: g;   % groups per week
int: p;   % players per group
int: w;   % weeks
int: n = g * p;

% group[wk, grp] = set of golfer IDs in that group
array[1..w, 1..g] of var set of 1..n: groups;

% Each week is a partition of all golfers
constraint forall(wk in 1..w)(
  partition_set([ groups[wk, gr] | gr in 1..g ], 1..n)
);

% Each group has exactly p members
constraint forall(wk in 1..w, gr in 1..g)(
  card(groups[wk, gr]) = p
);

% No pair of golfers shares a group in more than one week
constraint forall(w1 in 1..w, w2 in w1+1..w,
                  g1 in 1..g, g2 in 1..g)(
  card(groups[w1,g1] intersect groups[w2,g2]) <= 1
);

% Symmetry breaking: fix first week's groups
constraint forall(gr in 1..g)(
  groups[1, gr] = { (gr-1)*p + 1 .. gr*p }
);

solve satisfy;

---

Key Techniques

1. Symmetry Breaking (Critical for Tractability)

The Social Golfer Problem is riddled with symmetry:

• Week symmetry: any permutation of the w weeks gives an equivalent solution
• Group symmetry (within a week): any permutation of the g groups in a week is equivalent
• Golfer relabeling symmetry: renaming golfer IDs gives another valid solution

Without breaking these, the solver wastes enormous effort on equivalent subtrees. Standard breaks:

• Fix week 1's groups to {1..p}, {p+1..2p}, ... (breaks week symmetry + golfer relabeling)
• Order groups lexicographically within each week: min(S[w][1]) < min(S[w][2]) < ...
• Order weeks lexicographically by their canonical representation

Symmetry breaking alone can reduce search by factors of g! · (g!)^(w-1) · n! — often making otherwise intractable instances feasible.

2. Global Constraints & Propagation

The partition_set global constraint achieves strong consistency by ensuring the union covers all elements exactly once. The pairwise intersection constraint |S[w1][g1] ∩ S[w2][g2]| ≤ 1 benefits from bound consistency on set variable domains — if golfer j is forced into group g1 in week w1, the solver can immediately exclude j from any group in week w2 that already contains another member of g1.

3. Dual Modeling & Channeling

The problem admits both a group-based model (which group does golfer j go to?) and a pair-based model (which week does pair (j1, j2) meet?). Maintaining two models simultaneously with channeling constraints lets the solver exploit propagation in both directions — a technique that has proven highly effective in benchmarks.

---

Challenge Corner

Can you tighten the theoretical bound?
The upper bound w ≤ (gp−1)/(p−1) is necessary but not sufficient. For g = 5, p = 3, the bound gives w ≤ 7. The instance 5-3-7 is a famous open problem: it is unknown whether 7 weeks are achievable (the best known is 7 weeks, proved by exhaustive CP search in 2000). Can you identify which values of (g, p) allow the bound to be met? These correspond to Kirkman resolutions of combinatorial designs.

Extension — weighted social golfer:
Suppose some pairs of golfers are "rivals" who must never share a group, while other pairs are "friends" who should share a group at least twice. How would you encode these soft constraints, and what objective function would balance the conflicting preferences?

---

References

1. Harvey, W. & Winterer, T. (2001). "Solving the Social Golfer Problem via Symmetry Breaking." Proceedings of CP 2001. — The paper that introduced efficient symmetry-breaking for this benchmark.

2. Rossi, F., van Beek, P., & Walsh, T. (Eds., 2006). Handbook of Constraint Programming. Elsevier. — Chapter 4 covers global constraints (partition, intersection) used in set-based models.

3. Smith, B. M. (2000). "Modelling for Constraint Programming." CP 2000 Tutorial Slides. — Includes the Social Golfer Problem as a worked dual-modelling example.

4. Colbourn, C. J. & Dinitz, J. H. (Eds., 2007). Handbook of Combinatorial Designs. — Connects the problem to resolvable designs and Kirkman schoolgirl configurations.

AI generated by Constraint Solving — Problem of the Day · history

• expires on Apr 4, 2026, 12:54 PM UTC

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #23455.