Skip to content

HiGHS

HiGHS is an open-source linear and mixed-integer programming solver. Its profile here is close to SCIP's, for the same reason: both are general MILP engines, so the diversity problem has to be written as a model before either is involved, and the same linearizations apply to both.

Where it differs is licensing and footprint. HiGHS is MIT-licensed and comparatively light to install, which makes it the easier of the two to embed in a project that only occasionally needs an exact answer.

It is included as a second optimality reference rather than as a distinct approach. If the two disagree on a small instance, one of them has a bug — which is exactly why having two is useful.

Problem targeted

Identical in form to any MILP-based selection: given \(n\) items, a distance \(d(i,j)\) and a size \(k\),

\[ \max_{S \subseteq \{1,\dots,n\},\; |S| = k} f(S), \]

with \(f\) supplied in linearized form. For max-min that is the big-M threshold formulation:

\[ \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. On termination the reported selection is optimal for the model as written — which makes the modelling, not the solving, the place errors live.

Reference

At a glance
Guarantee proven optimum
License MIT
Version 1.15.1
Released 2026-07-02
Determinism deterministic
Input a hand-built model
Source https://ergo-code.github.io/HiGHS/
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 ◐ 3
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 you build the model: distances enter as precomputed objective coefficients, so the metric is whatever you computed before the solver ever sees it. ↩↩↩

  2. Distances are coefficients you supply, so an unusual metric costs no more than a common one. ↩

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

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

  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. The same big-M max-min formulation SCIP solves, and the same ceiling: the model carries a constraint per pair, so it grows quadratically and stops closing the gap in reasonable time around n ≈ 10³. ↩