Skip to content

SCIP (PySCIPOpt)

SCIP is a general-purpose mixed-integer programming solver, used here through its Python interface PySCIPOpt. It is not a diversity tool: it solves whatever model you hand it, which means the diversity problem has to be written as a MILP before SCIP is involved at all.

That framing explains most of its profile below. Distance metrics, objectives and constraints are all reachable rather than provided — reachable by writing the right model, at whatever size that model turns out to be tractable. What SCIP offers in exchange is the one thing no heuristic can: when it finishes, the answer is provably optimal.

In this comparison it serves as the optimality reference for the small instances, not as a competitor. Below roughly a thousand items it establishes what the best achievable objective value actually is; above that, it stops being able to answer in reasonable time.

Problem targeted

Given \(n\) items, a distance \(d(i,j)\) between them, and a target size \(k\), SCIP solves any selection problem whose objective and constraints you can linearize:

\[ \max_{S \subseteq \{1,\dots,n\},\; |S| = k} f(S) \quad\text{subject to your linear constraints,} \]

where \(f\) must be supplied in linearized form. For the max-min objective this is the standard threshold formulation, introducing \(t \le d(i,j)\) for every selected pair:

\[ \max\; t \qquad t \le d(i,j) + M\,(2 - x_i - x_j) \quad \forall\, i < j, \qquad \sum_i x_i = k, \qquad x_i \in \{0,1\}. \]

Guarantee: proven optimum. SCIP terminates with a certificate that no better selection exists, which is what distinguishes it from every heuristic in this comparison.

Reference

At a glance
Guarantee proven optimum
License Apache-2.0 (SCIP) 1
Version 6.2.1
Released 2026-05-16
Determinism deterministic
Input a hand-built model
Source https://www.scipopt.org/
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 ◐ 2
distance metrics · L2 (Euclidean) distance ◐ 2
distance metrics · cosine distance ◐ 2
distance metrics · caller-supplied distances ✔ 3
diversity objectives · maximize the minimum separation ◐ 4
diversity objectives · maximize the mean nearest-neighbor separation ◐ 5
diversity objectives · maximize the geometric-mean nearest-neighbor separation ◐ 5
diversity objectives · maximize the mean pairwise distance ◐ 4
constraints beyond k · per-group counts over disjoint groups ◐ 6
constraints beyond k · per-group counts over overlapping groups ◐ 6
constraints beyond k · minimum and maximum counts per group ◐ 6
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 ◐ 7
largest practical problem size n ≈ 103 8

  1. The two halves carry different licenses: the SCIP solver itself is Apache-2.0, while the PySCIPOpt binding installed from PyPI is MIT. Source ↩

  2. Reachable, but you build the model: distances enter as precomputed objective coefficients, so the metric is whatever you computed before the solver ever sees it. ↩↩↩

  3. Since every distance is a coefficient you supply, an arbitrary metric costs nothing extra — this is the one distance axis where a modelling solver is at no disadvantage. ↩

  4. Reachable, but the objective must be linearized by hand — for max-min, a threshold variable bounded below every selected pair via big-M constraints. ↩↩

  5. Reachable only through an assignment MILP that pairs each selected item with its nearest selected neighbor; the formulation is considerably larger than the max-min one and is what drives the practical size limit down. ↩↩

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

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

  8. The limit differs sharply by objective. A max-min model with big-M linearization is routinely solved to optimality around n ≈ 10³; the mean-of-NN objective needs an assignment MILP whose size grows far faster and which stops being tractable near n ≈ 60 — below the floor of the benchmark generators used here. The single value reported is the max-min one, because that is the formulation this comparison actually exercises. ↩