In a row of binary variables, we may want to know the distance from the left-most selected variable, to the right-most selected variable.
E.g. the max distance for visiting all the selected stores on a street, or selected controls on a factory line,
Left–right distance for a binary row using Big‑M
Given:
x[i] in {0,1}, i = 1..n
x[i] = 1 means position i is selected
Selections may be non‑contiguous
Decision variables
L : integer, leftmost selected index
R : integer, rightmost selected index
Choose big-M:
M >= n (e.g. M = n)
Big‑M linking constraints
For all i = 1..n:
L <= i + M * (1 - x[i])
R >= i - M * (1 - x[i])
How this works
If x[i] = 1:
L <= i
R >= i
If x[i] = 0:
Constraints are relaxed by big-M and have no effect
Therefore:
L is forced <= all selected indices
R is forced >= all selected indices
In an optimization objective:
L becomes the minimum selected index
R becomes the maximum selected index
Distance (span) definition
Distance = R - L
This distance:
Counts the full range from leftmost to rightmost 1
Includes all gaps inside the range
Does NOT require contiguity
Typical objective
Minimize:
R - L
Optionally with feasibility safeguard:
Sum_i x[i] >= 1 (to avoid empty selection)
Example
x = 0 1 0 0 1 0
Selected indices = {2,5}
Constraints force:
L = 2
R = 5
Distance = 3