Propagation Algorithms for the Minimum-Distance Constraint

display math
min_distance(D,x,z,R)\texttt{min\_distance}(D, \mathbf{x}, z, R)
paragraph

Mikael Z. Lagerkvist · ModRef 2026

1 / 14

Choose five sites.

figureEight hollow candidate sites A through H in a two-dimensional Euclidean field, beside a z ruler drawn at the same scale
Maximise the shortest distance among the five selected sites.
2 / 14

Modelling min distance problems

layout: grid

Direct decomposition

display math
yij=D[xi,xj]z=min⁡i<j(yij)y_{ij}=D[x_i,x_j] \qquad z=\min_{i<j}(y_{ij})
unordered list
  • one distance variable per selected pair
  • quadratic count of yy variables
  • quadratic number of propagators
  • (potentially) quadratic domain sizes

Dedicated constraint

display math
min_distance(D,x,z)min⁡i<j\mathsf{min\_distance}(D, \mathbf{x}, z)\phantom{\min_{i<j}}
unordered list
  • single constraint
  • global view of problem
  • smarter propagation choices
3 / 14

Pair-check checks on assignment

figureA and E are strongly selected, their true Euclidean separation is five, and z maximum is lowered from seven to five on the same-scale ruler
A–E is 5, so z≤5z\leq 5. Another selected pair may still lower zz.
4 / 14

Forward-bound scans on assignment

figureA is selected; a radius-four circle crosses out B and D while C, E, F, G, and H remain hollow possibilities; z ranges from four to five
At T = 4, B and D are strictly too close to A. Equality stays feasible.
5 / 14

Pair support starts on the site graph

figureOn the standard site graph, violet diamonds mark A and E for x i; orange squares mark B, C, D, and F for x j. No supports are drawn.
Can every value of xⱼ find a partner at distance at least 4?
6 / 14

Pair support removes D

figureCurved arrows show E supporting B and A supporting C and F. The x j glyph at D is crossed out, but site D remains.
Thin curves witness B, C, and F; remove the unsupported xⱼ = D.
7 / 14

Detail: one relation, four kernels

table
KernelWhen it can actWhat it does
Pair-checkboth endpoints fixedmeasures the selected pair
Forward-boundone endpoint fixedprunes inside the active radius
Full pair supportbefore either is fixedfinds a partner for every value
Advisorsafter relevant domain eventsrevisits affected pairs and witnesses
quote

Pairwise and global variants package these kernels differently. Matching is a separate upper-bound pass.

8 / 14

Detail: one relation, three model views

table
Model viewDecision variablesWhat the propagator sees
Indexedp site-valued variablesone current site domain per position
Site-booleann selection booleansselected and possible sites
Assignment-booleanp × n assignment booleansa Boolean encoding of each position domain
paragraph

The pictures use the indexed view. The matching graph uses the union of its
current position domains.

9 / 14

Distance four solution

figureA, C, E, F, and G are selected; C to E and F to G are true segments of length four, while B, D, and H are no longer possible
Sites A,C,E,F,G{A,C,E,F,G} reach distance 4. The next distance level is 5.
10 / 14

Build the conflicts for z = 5

figureThe conflict graph joins every pair of sites that cannot coexist in a distance-five solution; no matching is marked
Join two sites when selecting both would interfere with z=5z=5.
11 / 14

A matching proves z < 5

figureThe same conflict graph stays fixed while AB, CD, EH, and FG are highlighted as a matching, proving that at most four sites can remain and z is below five
Four matched conflicts leave at most four sites, proving z<5z<5.
12 / 14

Advisors and matching are useful

figureNine bars rank exact variants from 904 to 235; a separate footer lists aggressive and safe heuristics at 80 and 52.
13 / 14

Parting remarks

unordered list
  • Some propagators are easy to implement
  • Advisors are useful
  • Avoid quadratic numbers of propagators and variables
  • Matching gives a useful upper bound for min_distance\mathsf{min\_distance}
14 / 14