Stochastic local search

⚠️ Curated Limitations & Negative Results

• This record selects the named combinatorial neighborhood-search framework in the inspected thesis and chapter. The bare term local search is often used more narrowly for perturbative search, and its use as the name of an arbitrary embedded optimization routine does not establish the same identity. Continuous-search conventions and the full generalized-local-search-machine model are outside this scoped definition.
• This is a configurable algorithm family, not a complete executable instance. A concrete procedure must specify its representation, neighborhood, initialization, step and memory rules, evaluation, stopping, tie handling and feasibility conventions. If no feasible solution has been encountered, a best-feasible-solution return is unavailable unless an additional failure or fallback convention is supplied.
• Current search positions can worsen or recur. Keeping the best encountered value of a fixed, consistently evaluated objective makes that recorded incumbent value non-worsening when an incumbent exists; it does not make every search step improving or prove global optimality. A changing guidance function need not have the same monotonicity.
• Randomization alone does not guarantee reachability of a solution, irreducibility, finite termination, probabilistic completeness or an approximation guarantee. Such conclusions require additional assumptions on the problem, neighborhood, transition probabilities, initialization and stopping rule. A run stopped by a resource budget can return without finding a feasible or optimal solution.
• The current search position alone need not be a Markov state when the procedure uses memory or time-dependent rules. An adequate state description may include memory and a clock; this representation does not by itself imply stationarity, detailed balance or sampling from a specified target distribution.
• Allowing partial solutions and population-valued positions is a formal inclusion, not an assertion that constructive search, evolutionary algorithms, ant-colony methods, strict hill climbing and their particular controllers are identical. The family boundary also differs from the looser term metaheuristic; individual mechanisms and named compositions retain separate identities.
• The 1998 dissertation supplies the underlying search-space, neighborhood and search-control distinctions; the 2015 author-hosted overview supplies explicit memory, stopping and representation exposition without establishing invention priority. Evidence assessment is limited to the inspected defining passages and selected visuals, not the full dissertation, an unread book definition, all GLSM proofs, author software or benchmark reproduction. No universal performance ranking follows from the framework.