Skip to content

OR-Tools CP-SAT

CP-SAT is Google's constraint-programming solver, and like every exact solver here it is not a diversity tool: you write a model, it proves an answer. What makes it worth a profile of its own is that one diversity objective suits it unusually well.

Max-min is a threshold question in disguise. Rather than maximizing a minimum, you ask whether a selection exists in which every pair is at least \(t\) apart — pure feasibility, which is what constraint propagation is built for — and then binary-search \(t\). That plays to CP-SAT's strengths in a way the mean-based objectives do not.

The catch is integrality. CP-SAT reasons over integers, so distances must be scaled and rounded before the model is built, and the scaling factor becomes a precision decision you own.

Problem targeted

Given \(n\) items, a distance \(d(i,j)\), and a target size \(k\), the max-min formulation is a sequence of feasibility problems parameterized by a threshold \(t\):

\[ \exists\, S \subseteq \{1,\dots,n\},\; |S| = k \quad\text{such that}\quad d(i,j) \ge t \;\; \forall\, i,j \in S,\; i \ne j. \]

The largest \(t\) for which this is satisfiable is the max-min optimum. In practice the search is driven by a binary search over \(t\) with each feasibility question handed to the solver.

Guarantee: proven optimum. Each feasibility answer is exact, so the resulting threshold is the true optimum rather than a bound on it.

Reference

At a glance
Guarantee proven optimum
License Apache-2.0
Version 9.15.6755
Released 2026-01-14
Determinism deterministic with a fixed worker count
Input a hand-built model
Source https://developers.google.com/optimization/cp/cp_solver
Last verified 2026-07-27

Capabilities

Support: ✔ built in · ◐ reachable, but you supply the model, transform or metric · — not available

Capability Support Notes
distance metrics · L1 (Manhattan) distance ◐ 1
distance metrics · L2 (Euclidean) distance ◐ 1
distance metrics · cosine distance ◐ 1
distance metrics · caller-supplied distances ✔ 2
diversity objectives · maximize the minimum separation ◐ 3
diversity objectives · maximize the mean nearest-neighbor separation ◐ 4
diversity objectives · maximize the geometric-mean nearest-neighbor separation ◐ 4
diversity objectives · maximize the mean pairwise distance ◐ 4
constraints beyond k · per-group counts over disjoint groups ◐ 5
constraints beyond k · per-group counts over overlapping groups ◐ 5
constraints beyond k · minimum and maximum counts per group ◐ 5
time budget · budget expressed as an iteration count ✔
time budget · budget expressed as wall-clock time ✔
time budget · the answer improves when given more budget ◐ 6
largest practical problem size n ≈ 103 7

  1. Reachable, but CP-SAT is an integer solver: distances must be scaled to integers before they enter the model, so the achievable precision is a modelling choice rather than a property of the metric. ↩↩↩

  2. Any distance you can compute and round to integers is usable, which in practice means any metric at all. ↩

  3. Reachable through a threshold feasibility search: ask whether a selection exists with every pair at least t apart, then binary-search t. It is a natural fit for CP-SAT and the reason this solver appears here at all. ↩

  4. No natural constraint-programming encoding. Expressing a nearest-neighbor mean needs the same auxiliary assignment structure a MILP would use, at which point a MILP solver is the better tool. ↩↩↩

  5. Reachable as linear constraints over the selection variables, which you write yourself. Any counting constraint expressible that way is available. ↩↩↩

  6. The incumbent improves as the branch-and-bound search proceeds, but that is a proof search rather than an anytime budget: progress is uneven, and time spent may go entirely into tightening the bound rather than improving the solution. ↩

  7. Max-min is solved by repeatedly asking a feasibility question — "can k items all be at least t apart?" — and each question is a fresh constraint-propagation search over O(n²) pairwise constraints. That stays tractable to around n ≈ 10³ and degrades sharply beyond it. ↩