Propagating the minimum distance between selected pointsDRAFT

Selecting well-spaced points has a compact mathematical statement, but its straightforward CP model creates a distance variable for every selected pair. My ModRef 2026 paper Propagation Algorithms for the Minimum-Distance Constraint over Selected Points studies what happens when Gecode handles that relation directly.

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

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.

This selection gives us a lower bound of 4. The next larger pair-distance level is 5, so proving optimality means ruling out every selection whose minimum distance is at least 5. The matching bound below does exactly that.

Propagator variants#

Some variants change the inference itself. Others perform similar inference but differ in how they organise and remember the work.

The advisor-backed variants change how the work is scheduled and remembered. The matching suffix adds a separate upper-bound argument.

The figure adapts the main experimental table from the paper. All 100 imported p-dispersion instances 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. 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 must be an independent set in this graph. The propagator then computes a greedy maximal matching in the conflict graph.

Any matching gives a sound upper bound on the size of such an independent set; the propagator builds one greedily until it is maximal. Each matching edge has disjoint endpoints, and an independent set can contain at most one endpoint from each edge. If the active graph has n vertices and the matching has m edges, then the largest independent set, written α(Gₜ), satisfies

α(Gₜ) ≤ n − m.

For the eight-site instance, the conflict edges at threshold 5 are AB, AD, BG, CD, DE, EH, and FG. The four highlighted edges below form one greedy maximal matching: AB, CD, EH, and FG.

The matching proves that an independent set contains at most 8 − 4 = 4 sites. We need five, so a minimum distance of 5 is impossible and the propagator can lower z.max to the preceding distance level, 4. The selection in the first figure attains 4, so the lower and upper bounds meet: its minimum distance is optimal.

This is only an upper-bound certificate. A greedy maximal matching may fail to find a certificate even when the threshold is impossible, and passing the test does not prove that the threshold is feasible. Different maximal matchings can also have different sizes, so propagation may depend on which edges the greedy algorithm encounters first.¹ The strict conflict test matters as well: points exactly 4 apart, such as F and G, remain compatible when testing t = 4.

The custom constraint avoids the auxiliary distance variables and lets the propagators use information specific to this problem. Advisors remember which pairs changed, while the matching pass supplies an additional upper-bound certificate. In this comparison, the advisor-backed forward-bound variant with matching has the best anytime score. The simpler pairwise forward-bound propagator remains competitive and is considerably easier to implement. These preliminary experiments do not identify one implementation as universally best. The paper contains the details and complete comparison, and the implementations are available as code.

Extended comparison#

The paper compared selected combinations of propagators and matching propagation using Gecode’s Accumulated Failure Count heuristic.² The extension tests all six custom propagators and the extensional tuple-set (table) variant, with matching off and on under two search settings, AFC and Size: 28 configurations on the same 100 instances.

The added propagator is pair-support. It posts a support-maintaining propagator for each pair of selected positions. The global-support and advisor-support variants tested in the paper perform the same filtering inside a global propagator. The filtering is essentially the same pairwise ternary scheme as the DistanceGT constraint described by Panteleimon Iosif, Nikolaos Ploskas, Kostas Stergiou, and Dimos Tsouros in Modeling the p-Dispersion Problem with Distance Constraints at CP 2026.

Each configuration was run once with Gecode 6.4.0 and a 120-second limit on an M1 Max. The ranking uses the same MiniZinc Challenge area calculation as the paper, which measures how quickly a configuration finds good solutions and continues to improve them.

The controls in the table below filter by search and matching, then recalculate scores and ranks for the selected field. Each score counts pairwise anytime wins against the configurations in that field. The final column shows the change from the paper’s ranking; “New” marks configurations absent from it.

The first three columns describe the experiment matrix:

• Propagator selects one of seven propagators: six custom minimum-distance propagators and the general tuple-set propagator.
• Matching used shows whether the separate matching upper bound is active. Every propagator is tested both ways.
• Search heuristic selects AFC or Size. AFC uses accumulated failure count divided by domain size and tries the smallest value first. Size uses smallest-domain selection and a seeded random value order for predictable runs.

The 42-case columns use the paper’s subset that excludes the 58 instances whose virtual best was 2. Each view is ordered by its all-instance score. The paper’s experimental table provides the original ordering.

Four patterns stand out in the results:

• A forward-bound configuration leads every selectable view. Pairwise forward bound with AFC and matching leads the full table, while advisor forward bound leads several narrower views.
• Matching raises all fourteen full-set scores and thirteen of the fourteen harder-subset scores. The exception is tuple set under Size.
• The rank depends on the selected field. Pairwise forward bound with AFC and matching leads the full table, but ties advisor forward bound at 487 points and appears second after the tie-break in the AFC-with-matching view. Scores count pairwise anytime wins against the selected configurations, so filtering removes points unevenly without changing the runs. This field sensitivity is worth keeping in mind when comparing anytime results.
• Search changes the ordering. AFC scores higher for the pairwise and global variants, while the advisor variants score higher with Size. AFC also scores higher throughout the harder subset. The difference likely comes mainly from value ordering, but needs further research.

The 100-case corpus and fixed 42-case subset, benchmark script, and runs and selectable score views are available in the public repository.

Footnotes#

1. A maximum matching could strengthen the certificate by finding the largest possible m. The classical approach is Edmonds’ blossom algorithm, with complexity O(n²|E|) for n active sites and conflict-edge set E, compared with O(n²) for the simple greedy maximal matching used here. Blossom-style algorithms are also substantially harder to implement. Faster maximum-matching algorithms exist, but bring either more implementation complexity or significant constant factors. For this propagator, the greedy algorithm is a deliberate cost-strength tradeoff. ↩

2. Accumulated Failure Count is Gecode’s term for a measure that broadly corresponds to weighted degree. The INT_VAR_AFC_SIZE_MAX Gecode variable selector used here maximizes AFC divided by domain size and is Gecode’s counterpart to the heuristic usually called dom/wdeg in the literature. ↩