Runners

<easylocal/runners.hpp>; runners/runner.hpp, runners/search_run.hpp, runners/run_control.hpp, one header per algorithm

A runner couples a search algorithm with the recipes of the services. The algorithm describes the search; the framework owns its execution.

Composing a runner

auto runner = make_runner<Algorithm>({...})            // the algorithm's parameters
            | sm_recipe | nhe_recipe;                  // or .with_solution_manager(sm).with_neighborhood(nhe)

auto search = runner.bind(input);                      // materializes the services
auto result = search.run(solution, algorithm_args..., with(control, tracer));

When the algorithm's parameters_type is a parameter block (a schema and validate()), the runner holds the parameters and builds the algorithm when it is bound: make_runner<Algorithm>(parameters) creates it, and Runner{Algorithm{...}} is rejected at compile time. Any other algorithm is held as an object: make_runner<Algorithm>(args...) or Runner{Algorithm{...}}.

Invalid parameters throw std::invalid_argument, in Release builds as in Debug ones, wherever they enter: the constructors of the built-in algorithms and of their policies (temperature schedules, tabu lists), make_runner, and bind after a change through parameters(). The message names the field, temperature.cooling_rate: expected a value in (0, 1), got 2, or gives the requirement that does not hold. A real parameter with no upper bound (a temperature, a water level, a factor of the best cost) excludes infinity, (0, unlimited), so its domain rejects it as any other value out of range. A custom algorithm gets the same check from config::require_valid(parameters). Inside a run, the remaining contracts are asserts.

Member	Purpose
parameters()	the algorithm's parameters, to read or change (parameterized algorithms)
bind(const Input&)	build the services and the algorithm for an Input, a BoundRunner (temporaries are rejected)
configuration()	the parameters of the algorithm (search), the cost (cost), the SolutionManager (solution_manager) and the neighborhood (neighborhood), as a config::parameter_set
with_hard_cost()	the same runner on the hard branch of a hierarchical cost
BoundRunner: run(solution, args..., [with(...)])	run the algorithm
BoundRunner: initial_solution(), random_solution(rng), input(), better(a, b)	helpers

Built-in algorithms

Algorithm	Needs	Parameters	iterations counts
runners::FirstImprovement	moves or cursor, better	max_evaluations (unlimited: until a local optimum)	committed moves
runners::BestImprovement	moves or cursor, better	max_evaluations (unlimited: until a local optimum)	committed moves
runners::HillClimbing	random_move, better, better_or_equivalent	max_idle_iterations, max_evaluations	proposed moves
runners::LateAcceptanceHillClimbing	random_move, better, better_or_equivalent	history_length, max_idle_iterations, max_evaluations	proposed moves
runners::ParetoLateAcceptanceHillClimbing	random_move, better, a cost::pareto cost, random_solution	history_length, min_iterations, idle_ratio, second_chance, max_evaluations	proposed moves
runners::GreatDeluge	random_move, better, an arithmetic cost	initial_level, min_level, level_rate, neighbors_sampled, max_evaluations	proposed moves
runners::TabuSearch<List, Aspiration>	moves or cursor, better, inverse	max_idle_iterations, max_iterations, max_evaluations, tabu_list: the list's	committed moves
runners::FirstImprovementTabuSearch<List, Aspiration>	as TabuSearch	as TabuSearch, plus candidates: improve_on_best	committed moves
runners::AspirationPlusTabuSearch<List, Aspiration>	as TabuSearch, an arithmetic cost	as TabuSearch, plus candidates: min_moves, max_moves, plus, aspiration_level	committed moves
runners::EliteCandidateTabuSearch<List, Aspiration>	as TabuSearch, an arithmetic cost	as TabuSearch, plus candidates: elite_size, quality	committed moves
runners::SimulatedAnnealing<Temperature, Acceptance>	random_move, better, an acceptance-compatible cost	a temperature policy (temperature), an acceptance policy, max_evaluations	proposed moves

The parameters follow one naming rule. A max_<count> of the run (max_evaluations, max_iterations, max_idle_iterations, FixedTemperature's max_accepted) is a cap that ends the run when it is reached, of type easylocal::limit: a number, or easylocal::unlimited (a tag of type unlimited_t, which converts to the unlimited limit), written unlimited in a configuration file, on the command line and in the TextUI; 0 is a limit of zero, not "no limit". The size of a schedule, which shapes the search rather than stopping it, is allowed_<x> (allowed_iterations of the annealing schedules, allowed_reheats, allowed_running_time), and a threshold the search must pass first is min_<x> (min_iterations of Pareto Late Acceptance). The bounds of a value, such as min_tenure and max_tenure, keep their names. The caps are unlimited by default, except the ones whose value belongs to the problem, which have no default and must be set: max_idle_iterations, allowed_iterations, allowed_running_time and min_iterations.

The budget is checked only before evaluating a move, so an empty neighborhood is a local optimum even when the budget is exhausted.

Best Improvement applies the first of the best moves in the order of moves(): its ties are broken deterministically, where EasyLocal 3's SteepestDescent drew among them at random. An explorer that wants random ties shuffles its moves.

Hill Climbing accepts a random move when its cost is better or equivalent to the current one, so it moves across plateaus where a descent stops. It ends with idle_limit_reached after max_idle_iterations consecutive proposals without a strict improvement, or with local_optimum when the neighborhood proposes no move. Its cost never worsens, so the final solution is the best. Every runner that draws random moves (Late Acceptance, Great Deluge, Simulated Annealing, Pareto Late Acceptance) also ends with local_optimum when the neighborhood proposes none.

Late Acceptance Hill Climbing (Burke and Bykov) also accepts a move whose cost is better than or equivalent to the cost the current solution had history_length proposals earlier; the history starts filled with the initial cost, and with history_length 1 it accepts the moves Hill Climbing accepts. Its idle count runs from the last improvement of the best cost, and it returns the best solution found. EasyLocal 3 recorded the best cost in the history; EasyLocal 4 records the current cost, as in the original algorithm.

Pareto Late Acceptance Hill Climbing (Da Ros and Di Gaspero) is the multi-objective variant, for a cost::pareto cost: its history holds solutions, the initial one and history_length - 1 drawn with the solution manager's random_solution, visited in a circle. A random move of the current solution replaces it in the history when the candidate dominates it, and the search moves on to the next solution of the history. Otherwise, with second_chance, a candidate that dominates the next solution replaces it, and the search goes on from the solution it replaced, two positions on; else it moves on to the next solution. Past min_iterations the search ends with idle_limit_reached as soon as more than idle_ratio of the iterations went without a replacement. Its result is the run's front, with the first solution by objectives as solution.

Tabu Search applies at each iteration the best admissible move of the whole neighborhood, even a worsening one, ties broken uniformly at random. A move is admissible unless the tabu list forbids it, through the neighborhood's inverse (see NeighborhoodExplorer), and the aspiration criterion does not lift the prohibition: aspiration::ByObjective (the default) admits a tabu move that would improve the best cost, aspiration::None never does and then skips evaluating tabu moves. Another criterion is a value with overrides(run, candidate, best) -> bool and static constexpr bool needs_cost, which aspiration_for<A, Run> checks. When every move is tabu, the least tabu one (the shortest remaining tenure) is applied. The search ends with idle_limit_reached after max_idle_iterations iterations without improving the best cost, and returns the best solution found. FirstImprovementTabuSearch stops the scan at the first admissible move that improves the current cost (with improve_on_best, the best cost); without one it applies the best admissible move. Both take the RNG as a run argument, for the ties.

The four tabu searches share one parameter block, TabuSearchParameters<ListParameters, CandidateParameters>: the limits of the run, the list's parameters as the group tabu_list, and those of the candidate strategy, the scan of each iteration, as the group candidates (search.candidates.* in a configuration): candidates::FirstImprovementParameters, AspirationPlusParameters and EliteListParameters. The full scan of TabuSearch, candidates::FullParameters, has none, and no group:

make_runner<AspirationPlusTabuSearch<tabu::RandomTenure>>(
    {.max_idle_iterations = 500,
     .tabu_list = {.min_tenure = 5, .max_tenure = 15},
     .candidates = {.min_moves = 10, .max_moves = 40}})

Two runners implement Glover's candidate list strategies, whose levels are values of the cost (an arithmetic cost):

• AspirationPlusTabuSearch examines admissible moves until plus more after the first one under the aspiration level, but at least min_moves and at most max_moves, and applies the best examined.
• EliteCandidateTabuSearch keeps, from a full scan, the elite_size best admissible moves besides the one applied; the next iterations evaluate only the kept moves still valid and apply the best admissible one while its cost is at most the quality level, otherwise a full scan builds a new list.

Both levels are a factor f (aspiration_level, quality) of the best cost b, kept on the worse side of it whatever its sign: b + (f - 1) * |b|, which is f * b for a positive best cost.

Tabu lists in runners::tabu; their parameters are the group tabu_list:

List	Parameters	A move stays tabu
FixedLength (TS1)	tenure	for tenure iterations after the move it would undo
RandomTenure (TS2)	min_tenure, max_tenure	for a tenure drawn uniformly in [min_tenure, max_tenure]
Cyclic (TS3)	period, tenures	for the current tenure, which takes the tenures in turn every period iterations
Reactive (TS4)	increase, decrease, repetitions, chaos, cycle_length, max_tenure, verify_equality	for a tenure that reacts to revisited solutions; needs the solution hash and random_move
Frequency (TS5)	threshold	while its attribute was applied in more than threshold of the iterations; needs tabu_attribute, not inverse
ObjectiveBased	tenure	while its cost is equivalent to one reached in the last tenure iterations, by the cost semantics (equivalent); needs neither inverse nor attribute
LimDynamic (limited dynamic)	min_tenure, max_tenure, idle_threshold	for a tenure that grows by one after idle_threshold idle iterations and falls back to min_tenure on an improvement or at max_tenure
Foo (FOO, Fluctuation Of the Objective)	window, increment, fluctuation	for a tenure that grows by increment when the costs of the last window iterations spread less than fluctuation, and shrinks by one otherwise; needs cost::delta, whose spread across two hard levels of a cost::hierarchical is infinite, so a window that changes the hard cost shrinks the tenure
RandomFoo (randomized FOO)	ranges of the three	as Foo, drawing them again at each window

Most lists forbid moves through the neighborhood's inverse, Frequency through its tabu_attribute, ObjectiveBased through the candidate's cost, evaluating each move before the tabu check (see NeighborhoodExplorer); each requires only what it uses. Reactive (Battiti and Tecchiolli) starts with tenure 1 and recognizes solutions by solution_hash (see SolutionManager); a hash collision counts as a revisit, unless verify_equality keeps a copy of each visited solution and compares those with the same hash, which needs solution equality (has_solution_equality, otherwise the run throws std::invalid_argument). A solution revisited within cycle_length iterations multiplies the tenure by increase (up to max_tenure) and updates the average cycle length; without such cycles for longer than the average, the tenure is multiplied by decrease. A solution visited more than repetitions times counts as chaos; after more than chaos counts the memory is reset and the search escapes with 1 + (1 + r) * average / 2 random moves (r uniform in [0, 1)), applied whatever their cost, counted as iterations and recorded in the list like the others.

The names of the lists are those of Da Ros, Di Gaspero and Schaerf's performance analysis of tabu list strategies: LimDynamic is a limited dynamic tenure, Foo the Fluctuation Of the Objective scheme of Blöchliger and Zufferey, and RandomFoo its variant that draws the parameters again at each window.

The lists with one tenure for all moves (Reactive, LimDynamic, Foo, RandomFoo) apply the current tenure to every move they hold: a move is tabu while it is younger than the tenure, so a growth also makes tabu again the older moves it covers. Each list keeps the moves that the next growth can reach: those of the last tenure + increment - 1 iterations before a Foo window ends, of the tenure that increase would bring for Reactive.

A tabu list is a value with its parameters that makes, for each run, a state with make_state<Run>(). tabu_tenure(candidate) gives the iterations left before a candidate move is admissible, nothing when it is (tabu_candidate: move(), forbidden_by(tabu_move) through the inverse, attribute(), and, when the state declares static constexpr bool needs_cost = true, cost() and equivalent_cost(other), members of tabu_candidate<Run, true> only, so a list that reads the cost without declaring it does not compile); update(step, rng) records an applied move (tabu_step: move(), solution(), cost(), iteration(), improved_best(), attribute(), solution_hash(), the last two when the problem has them). A state with escape_moves() asks for that many random moves, and one with current_tenure(), a tenure for all its moves, has it traced as tabu_tenure_changed at the start of the run and whenever it changes. tabu_list_for checks a custom list.

Great Deluge accepts a move that improves the current cost or whose cost does not exceed the water level. The level starts at initial_level times the initial cost and is multiplied by level_rate every neighbors_sampled proposals; the search ends, completed, when the level falls below min_level times the best cost, and returns the best solution found. The level is a value of the cost, so Great Deluge requires an arithmetic cost (cost::arithmetic), and positive, since the levels are factors of it: a best cost of zero ends the search.

Simulated Annealing returns the best solution found. Temperature policies in runners::temperature, all configurable:

Policy	Parameters	Stops when
Classic	initial/final temperature, cooling rate, samples per temperature	the final temperature is reached
FixedLength	initial/final temperature, cooling rate, allowed_iterations	the allowed iterations are spent, spread over the levels
Cutoff	as FixedLength, plus accepted_ratio	the allowed iterations are spent; cools only after accepted_ratio of a level's share of them have been accepted, never on samples
Hybrid	as Cutoff	the allowed iterations are spent; cools on samples or acceptances (samples_per_temperature(), accepted_limit())
FixedTemperature	temperature, allowed_iterations, max_accepted (unlimited by default)	the allowed iterations are spent, or max_accepted moves are accepted; never cools
TimeBased	initial/final temperature, cooling rate, running time, accepted per temperature (unlimited: cools only on time)	the running time is over or the final temperature is reached; levels share the time
Reheating<Descent>	descent: the schedule's, plus allowed_reheats, reheat ratio, first-descent share	the last descent ends; each reheat restarts from reheat_ratio times T0

The levels of a schedule are counted once, from its temperatures: the smallest k with initial_temperature * cooling_rate^k <= final_temperature, a count within rounding of an integer being that integer, so that 1 to 0.001 by 0.1 is three levels. Classic and TimeBased end after that many levels, and the schedules with a budget spread it over them.

TimeBased reads the clock (std::chrono::steady_clock; BasicTimeBased<Clock> takes another one) as a run checks its time limit: at an interval of proposals that adapts so that readings come about a millisecond apart, and at each early cooling. Its trajectory depends on the speed of the machine, so equal seeds do not give equal runs.

Reheating<Descent> reheats any schedule whose parameters have an initial_temperature (all but FixedTemperature): a first descent, then up to allowed_reheats descents that restart from reheat_ratio times the initial temperature. When the schedule has a budget, allowed_iterations or allowed_running_time, the first descent spends first_descent_share of it and the reheats divide the rest evenly, at least one iteration each, so allowed_reheats may not exceed the iterations the first descent leaves (a requirement of the block); Classic, which has none, runs whole at every descent. The schedule's parameters are the group descent: {.temperature = {.descent = {...}, .allowed_reheats = 2}}, search.temperature.descent.* in a configuration. It calibrates when the schedule does, keeping the reheat temperature above the final one. Reheating<Hybrid> is EasyLocal 3's annealing with reheating.

For a complete extension example, see Customizing Simulated Annealing. It walks through the library's run implementation, configures this wrapper and writes a temperature policy that reheats after consecutive rejections.

Every built-in policy can estimate its initial temperature (the constant one for FixedTemperature) with calibration_samples > 0: before the run, Simulated Annealing evaluates that many random moves at the initial solution, without applying them, and the policy starts from the temperature at which a worsening move of average size is accepted with probability initial_acceptance (0.5 by default; 0.2 suits a good initial solution), as in Johnson et al. (1989). Improving moves and infinite deltas (a hierarchical hard level) are ignored; without worsening moves, or when the deltas ask for a temperature that is not a representable number, initial_temperature stays, and the estimate is kept above the final temperature. The sampled moves count as evaluations, not as iterations. A custom policy opts in by modelling calibrating_temperature_policy: calibration_samples() and calibrate(std::span<const double> deltas).

runners::MetropolisAcceptance (the default) requires cost::delta (see Cost). On a cost::hard_soft cost the delta of a move that worsens the hard cost is infinite, so Simulated Annealing never accepts it, at any temperature, and cannot cross an infeasible region as EasyLocal 3's HARD_WEIGHT let it do. To cross one, write the cost as a single weighted sum, cost::sum(component<H>() * 1000, component<S>()), and check that the result is feasible. Another acceptance criterion is a value with accept(candidate, current, temperature, rng) -> bool, which acceptance_policy_for<Acceptance, Cost, RNG> checks. The parameters of SimulatedAnnealing<Policy> are SimulatedAnnealingParameters<Policy::parameters_type>, the policy's under the group temperature and the evaluation budget max_evaluations: make_runner<SimulatedAnnealing<Classic>>({.temperature = {...}}), search.temperature.* in a configuration. The temperatures have no default, since they live in the scale of the cost, and neither has the budget of a schedule that has one; the rest of each block does. A calibrating schedule with calibration_samples above 0 needs a cost with cost::delta; with any other cost the run throws std::invalid_argument.

Results

Built-in algorithms return search_result<Solution, Cost>: solution, cost, evaluations, iterations, termination (termination_reason::completed, local_optimum, evaluation_budget_exhausted, cancelled, target_reached, idle_limit_reached, time_limit_reached). With a cost::pareto cost they return pareto_search_result<Solution, Cost>, a search_result that adds front: the non-dominated solutions the run reached, as pareto_point{solution, cost}, ordered by their objectives. The search_run keeps them in a pareto_archive as the run starts, evaluates solutions and commits moves, so every algorithm has a front without doing anything. The archive compares costs with the run's relations (better, equivalent, so a root compare of the cost expression applies): a solution enters unless an archived one is better or has an equivalent cost, and removes those it is better than. So the front holds one point per non-dominated cost, the first reached.

The run options choose otherwise, for a run or a solve: options.keep_front({.keep_equivalent = true, .max_front_size = 100}) (a pareto_archive_parameters, the field front of run_options) keeps every distinct solution of an equivalent cost (by the problem's solution equality), and bounds the front: once it holds max_front_size points (at least 1, unlimited by default), a solution enters only by removing points it dominates. On a plateau, keeping every solution makes the front grow with the plateau and each offer scan it, so bound it. A reached target is the termination reason also when it coincides with a local optimum or the end of the algorithm; a cancellation takes precedence. Solvers and tools require only search_result_for<Result, Solution, Cost>: solution and cost.

Writing an algorithm

An algorithm is a class with a run member taking the search_run first:

class MySearch
{
public:
    using parameters_type = MyParameters;      // with a schema: configurable
    explicit MySearch(const MyParameters&);

    template<class Run>
    auto run(Run& run, typename Run::solution_type solution /*, extra args */) const;
};

With a schema and validate() on MyParameters, the runner holds them and builds MySearch at bind; they are configurable as search.* with no other member. Without one, parameters_type serves only app registration.

Extra run arguments (an RNG, for example) are passed through search.run(solution, extra...).

An algorithm may also declare what it asks of the services it searches with, so that a registration on a neighborhood it cannot use names the capability that is missing instead of the concepts that failed:

using search_requirements = easylocal::runners::requirements<
    easylocal::runners::needs::random_moves,
    easylocal::runners::needs::non_worsening>;

Capability	What the services must provide
needs::enumerated_moves	the explorer's moves(), or first_move() and next_move()
needs::random_moves	the explorer's random_move(solution, rng)
needs::random_solutions	the SolutionManager's random_solution(rng)
needs::strict_improvement	a cost with better()
needs::non_worsening	a cost with better_or_equivalent()

The capabilities are reported in the order they are declared, one message for the first the services do not provide; the neighborhood's before the cost's reads best. They only choose the message: an algorithm that runs is never rejected because of what it declares, and one that declares nothing keeps the generic message. The built-in algorithms declare theirs.

search_run

Member	Effect
limit_evaluations(n)	evaluation budget, including the initial evaluation: a count, or easylocal::unlimited
start(solution) -> evaluation	first evaluation, run_started, progress
evaluate_solution(solution) -> evaluation	another solution (a population, a history): counts, traced as visited, offered to the archive
front()	with a cost::pareto cost, the archive of the non-dominated solutions reached
should_stop() -> bool	cancellation, a reached target cost, an exhausted evaluation budget or a passed time limit; the reason is recorded
moves(solution), random_move(solution, rng)	neighborhood access; unions emit selection events
evaluate_move(solution, current, move) -> candidate	counts, move_evaluated, progress
commit(solution, current, candidate, move)	applies, move_accepted
next_iteration()	advances the iteration counter
incumbent_updated(previous, cost)	incumbent_updated event; the cost checked against the target
commit_improvement(solution, current, candidate, move)	commit, then incumbent_updated, for an algorithm whose current solution is its best (Hill Climbing, First and Best Improvement)
finish(solution, cost[, reason]) -> search_result	local_optimum (if that is the reason), run_finished
better, equivalent, better_or_equivalent	cost semantics
evaluations(), iterations(), target()	counters, the caller's target cost
context(), neighborhood_explorer(), input(), solution_manager()	the search context
evaluation(), emit(event), tracer(), control()	escape hatches (bypass counters and events)
with_evaluation(wrap)	a run that evaluates through wrap(evaluation()), a decorated facility (a delay, a cache), and shares the context, the cost relations, control, tracer, deadline, target and the budget left

evaluation / candidate expose cost(); finish without a reason uses the one recorded by should_stop(), or completed.

A decorated facility, the one wrap returns to with_evaluation, has the interface of the facility it wraps: the types evaluation_type and candidate_type, evaluate(solution) -> evaluation_type, evaluate_move(solution, current, move) -> candidate_type and commit(solution, current, candidate), the costs of an evaluation and of a candidate being cost() of the run's cost type. It forwards them, adding its own work (a delay, a count, a cache); the run keeps the counters, the events and the limits around it.

An algorithm that returns the best solution it visited, rather than the last, keeps it in a best_so_far{solution, cost}: best.update(run, solution, current) copies the solution when its evaluation is better than the best, emits incumbent_updated, and returns whether it did; at the end run.finish(std::move(best.solution), std::move(best.cost)). Late Acceptance, Great Deluge, Simulated Annealing and the tabu searches use it. An algorithm whose current solution is its best one applies an improving move with run.commit_improvement(...), which emits incumbent_updated too: so every built-in runner reports each new best cost.

Run options

Spelling	Effect
with(control)	cancellation (std::stop_token) and progress observer
with(tracer)	semantic trace events
with(control, tracer)	both
stop_at(target), with(...).stop_at(target)	stop as soon as the best cost is at least as good as target
options.without_target()	the same options without their target (a pipeline gives them to a stage that is not the last)
max_evaluations(n), with(...).max_evaluations(n)	stop once the run has made n evaluations, the initial one included; a runner's own max_evaluations, if smaller, still applies; termination evaluation_budget_exhausted
timeout(5s), timeout(2.5), with(...).timeout(...)	stop once the time limit has passed since the run started: a std::chrono duration or a number of seconds; termination time_limit_reached

run_control{stop_token, observer} calls observer(const run_progress&) with evaluations, iterations and evaluation_limit. A frontend that shows the progress from another thread stores it in a shared_run_progress from the observer and loads a copy when it draws, as the TextUI and the REST server do. control.stop_token() gives the token back, for a control of its own that shares it, and control.observing_progress(observer) a copy with another observer of the progress.

control.observe_best_cost<Cost>(best) adds an observer of the best costs: the run calls best(const Cost&) with its first cost, then with each cost better, by its cost semantics, than those it reported, the last one being the best the run found. It is called on a commit that improves, not on each evaluation; costs of another type than Cost are not reported. A shared_best_cost<Cost> keeps the last one for another thread, behind a mutex: the TextUI's progress line (best=) and REST's progress.best show it.

The options combine in any order: with(control).timeout(30s).max_evaluations(100000).stop_at(0). They are the fields control, tracer, target, timeout (none: no time limit) and max_evaluations (an easylocal::limit, unlimited by default) of run_options. A negative time limit, a NaN one (a number of seconds or a floating-point duration) and an infinite number of seconds throw std::invalid_argument; a duration beyond what the clock counts is the longest it can. search_run checks the deadline with the other stopping conditions, reading the clock at an interval of checks that adapts so that readings come about a millisecond apart: a loop that checks at every move reads it rarely, one that checks once per long iteration reads it every time. There is no timer thread.

The target converts to the runner's cost type and is compared with its cost semantics (better_or_equivalent). search_run checks the costs reached in start, commit and incumbent_updated, so every algorithm that checks should_stop() honours a target without further code. A run that ends with target_reached returns a solution that meets the target: with a partial order, such as a cost::pareto cost, the reaching cost need not dominate the best one, so best_so_far keeps the first cost that meets the target, and a run with a front returns a point of the front that meets it. A floating-point cost updated by deltas drifts from its full evaluation by rounding errors: when a committed cost misses the target only within cost::tolerance{}, the run evaluates the solution in full (not counted in the budget) before deciding, so a zero target, such as the one of until_feasible(), is reached by a cost that the deltas left at 1e-17. The same options are accepted by every solver's solve(input, options).

Design choices

• One run member. Algorithms describe their logic; counters, budget, cancellation, progress and events belong to search_run, so they behave the same in every algorithm. What the algorithm alone knows stays its own: counting an iteration, checking should_stop() and reporting a new incumbent (commit_improvement(), best_so_far).
• Every runner is cancellable. A run always carries a run_control; checking should_stop() is the whole contract. The cost of an inactive control is a null check.
• Tracing is compile-time. Without a tracer, events are not even constructed, nor the routes of the moves of a neighborhood union.
• Per-run state is local. BoundRunner::run is const, and each run starts from a new algorithm, built from the parameters or copied: a custom algorithm may keep state during a run, never from one run to the next.
• The algorithm class is its own key. No tag types: the class names the algorithm in make_runner and in app registrations.