Propagating the minimum distance between selected points - zayenz.seMenu

← Back to all blog posts← Newer<br>Older →

Propagating the minimum distance between selected pointsDRAFT<br>2026-07-16•4 min read•Cite<br>•researchconstraint programmingGecodepropagation

Part of the papers collection. Introductions to papers I have worked on, with some context for the research question and links to the paper and supporting material. See all 9 posts in the collection

_p]:my-0<br>[&_li_>_ul]:my-2<br>[&_li_>_ol]:my-2<br>[&_a]:text-primary [&_a]:hover:underline [&_a]:font-medium<br>[&_blockquote]:border-l-4 [&_blockquote]:border-accent [&_blockquote]:pl-4 [&_blockquote]:italic [&_blockquote]:text-muted-foreground [&_blockquote]:my-4<br>[&_pre]:bg-muted [&_pre]:p-4 [&_pre]:rounded-lg [&_pre]:overflow-x-auto [&_pre]:my-4<br>[&_pre_code]:bg-transparent [&_pre_code]:p-0<br>[&_code]:bg-muted [&_code]:text-foreground [&_code]:px-1.5 [&_code]:py-1 [&_code]:rounded<br>[&_hr]:border-t [&_hr]:border-accent [&_hr]:my-8<br>[&_section[data-footnotes]]:mt-12 [&_section[data-footnotes]]:pt-0<br>[&_section[data-footnotes]]:border-t [&_section[data-footnotes]]:border-accent/60<br>[&_section[data-footnotes]]:text-sm [&_section[data-footnotes]_ol]:mt-1<br>[&_section[data-footnotes]_p]:my-2<br>[&_strong]:font-bold<br>[&_em]:italic<br>[&_table]:w-full [&_table]:my-4 [&_table]:border-collapse<br>[&_th]:border [&_th]:border-accent [&_th]:p-2 [&_th]:text-left [&_th]:font-semibold<br>[&_td]:border [&_td]:border-accent [&_td]:p-2<br>[&_img]:rounded-lg [&_img]:my-4<br>">Writing a custom propagator is worth considering when one constraint carries much of a problem’s structure. My paper Propagation Algorithms for the Minimum-Distance Constraint over Selected Points, to be presented at ModRef 2026, works through one such case in Gecode.

Suppose we want to select five facility locations, spread out so that the closest pair is as far apart as possible. Let z denote that minimum distance. A straightforward CP model introduces a distance variable for every selected pair, then constrains z to be the minimum of those distances. This is a clear specification, but it creates quadratically many auxiliary variables and propagators.

I implemented several ways for Gecode to handle that relation directly: small pairwise propagators, global support scans, advisor-backed versions that remember which pairs need to be revisited, and an upper bound based on matchings in a conflict graph.

A small instance#

Consider the eight candidate sites below. We must choose five. The highlighted selection {A, C, E, F, G} has minimum distance 4, attained by F and G.

That gives us a lower bound of 4. The next larger pair-distance level in this instance is 5, so proving optimality amounts to ruling out every selection whose minimum distance is at least 5. We will return to that after introducing the propagators.

Propagator variants#

The variants differ in both the inference they perform and how they organise the work.

VariantWhat it doesTuple decompositionThe portable baseline: one distance variable and table constraint for each pair of selected positions.Pair checkWhen both endpoints are fixed, uses their exact distance to tighten the upper bound on z.Pairwise forward boundWhen one endpoint is fixed, removes values that are too close from the other endpoint and maintains an upper bound for the pair.Global forward boundPerforms the same forward-bound inference for every pair inside one global propagator.Global pair supportBefore either endpoint is fixed, checks that every value still has a supporting partner. This is stronger, but requires more scanning.Advisor-backed forward boundUses advisors to revisit only affected pairs for the lighter forward-bound kernel, retaining useful pairwise witnesses between rounds.Advisor-backed pair supportUses the same scheduling and witness reuse for the stronger full pair-support kernel.+ matchingAdds a separate conflict-graph pass that tightens z.max. It complements the other filtering; it does not replace it.

The advisor-backed rows in the results therefore change how work is scheduled and remembered, while the matching suffix adds another upper-bound argument.

The figure adapts the main experimental table from the paper. The 100 imported p-dispersion instances all ask the solver to select well-spaced points. The MiniZinc Challenge area score rewards variants that find useful solutions early and continue improving them; higher is better. In these tests, the advisor-backed forward-bound propagator with the matching bound performs best. The simpler pairwise forward-bound propagator remains competitive, while the global pair-support scan scores below the tuple decomposition in this comparison.

How the greedy maximal matching bound works#

Take a candidate threshold t. Let the active sites be the union of the current selected-position domains. Build a conflict graph on those sites, with an edge between two sites when their distance is strictly less than t. A selection with minimum distance at least t...