Implements the DropAdd-TS algorithm of Porumbel, Hao & Glover (2011) for
selecting a maximally-dispersed subset of m points from a distance
matrix. The procedure consists of a deterministic greedy construction
(Algorithm 1) followed by a FIFO drop-add tabu search (Algorithm 2) with
the streamlined neighbour-evaluation tricks of Algorithms 3 and 4.
Usage
DropAddTS(
d,
m,
max_no_improve = 5000L,
max_iter = NULL,
time_budget_s = Inf,
seed = NULL,
progress = getOption("MaxMin.progress", interactive()),
.verify = FALSE,
.trace = NULL
)Arguments
- d
A
distobject or square symmetric numeric matrix.- m
Integer; subset size, \(2 \le m \le n\).
- max_no_improve
Integer; stop after this many consecutive drop-add iterations that do not improve the best objective. The primary, deterministic stopping criterion. The search is RNG-free (ties broken by smallest index), so for a given instance the result is reproducible and machine-independent. Default 5000.
- max_iter
Optional integer hard cap on iterations (excluding construction).
NULL(default) leavesmax_no_improvein sole control.- time_budget_s
Optional wall-clock ceiling in seconds, checked at iteration boundaries. Default
Inf(no ceiling, fully reproducible). A finite value caps runtime but makes the result machine-dependent.- seed
Optional integer; if non-NULL,
set.seed(seed)is called at entry. The algorithm is deterministic up to ties (broken by smallest index), so the seed has no observable effect on the solution; it is exposed for API parity with stochastic methods.- progress
Logical; show a start/done status line. Default:
TRUEin interactive sessions,FALSEotherwise (getOption("MaxMin.progress", interactive())). No effect when.verify = TRUE(testing path).- .verify
Logical (testing only); if
TRUE, routes to the R reference loop and brute-force asserts the streamlined records at every iteration. DefaultFALSE(the C++ fast path).- .trace
Optional environment (testing only); if supplied, the dropped and added index sequences are written into it as
dropsandadds.
Value
List with elements
- indices
integer(m), 1-based selected indices sorted ascending.
- objective
numeric(1), achieved MaxMin objective \(\min_{i \ne j \in S} d_{ij}\).
- secondary
numeric(1), achieved sum of pairwise distances over \(S\) (upper-triangle sum).
- time_s
numeric(1), wall-clock seconds spent.
- iters
integer(1), main-loop iterations executed (excluding the construction phase).
Details
The MMDPo objective optimised is $$\min_{x,y \in X} d(x,y) + \epsilon \sum_{x,y \in X} d(x,y),$$ with \(\epsilon = 10^{-9}\), so the pairwise sum acts as a tie-break.
Tabu mechanics. The algorithm maintains an integer iter stamp for
every point, set to the iteration at which the point last entered or
left the selected set \(X\). At each main-loop iteration the point with
the smallest iter value (the oldest member, FIFO) is dropped, and
the point in \(Z \setminus X\) maximising lexicographically
\((\mathrm{min\_dist}, \mathrm{sum\_dist})\) is added. The FIFO
invariant guarantees that across any window of \(m\) iterations every
initially-selected point is dropped exactly once before any re-eviction.