Local search¶

skroute.local_search holds the improvement heuristics of the library: solvers that start from a tour (the nearest-neighbour construction by default, or the tour_/route_ of another solver through init=) and apply moves while they shorten it.

TwoOpt reverses tour segments (2-opt).
OrOpt relocates segments of one to three nodes (Or-opt).
LocalSearch alternates both descents until neither improves.
IteratedLocalSearch kicks a local optimum with a double bridge, descends again and keeps the best tour: the recommended default solver.

All four are budget-aware: under max_time_work= the search prices every move with the multi-trip objective, so the trips it returns are the ones it optimised. Asymmetric matrices are accepted everywhere; they and the multi-trip objective take the full-evaluation path (O(n) per candidate move: one descent is fine up to a few thousand nodes, but IteratedLocalSearch re-descends after every kick, so on those problems keep to a few hundred nodes at the default n_iter, or set time_limit), while a symmetric plain TSP uses O(1) move deltas, candidate lists and don't-look bits and scales to tens of thousands of nodes.

The three descents are deterministic and expose history_ (the cost after each outer iteration), n_iter_ and stop_reason_ ("converged" or "max_iter"). One outer iteration is one pass of each listed move; the buffers persist across passes, so max_passes bounds the work without changing the local optimum reached when the descent converges earlier. Because don't-look bits skip nodes scanned earlier, a descent is declared converged only when a pass that started with every node active changes nothing — the same confirming sweep closes every iteration of the iterated search.

>>> from skroute import IteratedLocalSearch, LocalSearch
>>> from skroute.datasets import load_tsp
>>> dj = load_tsp("dj38")  # Djibouti, optimum 6656
>>> C = dj.distance_matrix()
>>> ls = LocalSearch().fit(C, labels=dj.labels)
>>> ls.cost_ / dj.optimal_tour_length < 1.12
True
>>> ils = IteratedLocalSearch(random_state=0).fit(C, labels=dj.labels)
>>> ils.cost_ <= ls.cost_ and ils.stop_reason_ in {"patience", "max_iter"}
True
>>> polished = LocalSearch(init=ils.tour_).fit(C, labels=dj.labels)  # warm start: already a local optimum
>>> polished.n_iter_, polished.stop_reason_
(1, 'converged')

TwoOpt ¶

TwoOpt(first_improvement: bool = True, init: Any = 'nearest_neighbour', n_candidates: int | None = 10, max_passes: int = 50, verbose: int = 0)

Bases: BaseRouter

2-opt descent: repeatedly reverse a tour segment while that shortens the tour.

Starts from init and applies Bentley's neighbour-list 2-opt with don't-look bits: for every active node a and each of its two tour edges, the candidates c of a are scanned in ascending order of C[a, c] while C[a, c] is below the edge being removed, and the reversal that creates the edge (a, c) is applied when it improves.

Parameters:

Name	Type	Description	Default
`first_improvement`	`bool`	Apply the first improving move found for a node (`True`) or scan the node's whole candidate neighbourhood and apply the best (`False`). Honoured only on the symmetric plain-TSP path; the generic path (asymmetric or multi-trip) is always first-improvement.	`True`
`init`	`'nearest_neighbour'`	Starting tour: the nearest-neighbour construction from the depot, or the `tour_`/ `route_` of another solver (labels; the depot may repeat).	`"nearest_neighbour"`
`n_candidates`	`int or None`	Size of the candidate lists (the `k` nearest neighbours of every node); `None` scans the full neighbourhood (`n - 1` nodes), a markedly better local optimum at small `n` for a higher cost per pass.	`10`
`max_passes`	`int`	Maximum number of outer iterations (one sweep over the active nodes each).	`50`
`verbose`	`int`	0 is silent; 1 logs every `max(1, max_passes // 10)` iterations and the stop; 2 logs every iteration. Records go to the `skroute` logger at INFO; enable them with `logging.basicConfig(level=logging.INFO)` or `skroute.set_log_level("INFO")`.	`0`

Attributes:

Name	Type	Description
`history_`	`ndarray of shape (n_iter_,), float64`	Cost after each outer iteration (non-increasing, never above the cost of `init`).
`n_iter_`	`int`	Outer iterations run.
`stop_reason_`	`{'converged', 'max_iter', 'callback'}`	`"converged"` when a sweep that started with every node active changed nothing, `"max_iter"` after `max_passes` sweeps, `"callback"` when the `callback` of `fit` returned `True`.

Notes

Supports: symmetric and asymmetric matrices, multi-trip objective; deterministic.

Callback events (D30): "start" carries the init tour with extra["moves"] (the listed descents, ["two_opt"]); each "iteration" event's tour is the working tour (also the best), with extra["moves_applied"] equal to ["two_opt"] when the sweep changed the tour ([] otherwise) and extra["gain"] the sweep's cost change.

One outer iteration = one call of the core's two_opt_descent with max_passes=1 (SPEC §4.3); the pos, candidate and don't-look-bit buffers persist across iterations. On a symmetric plain TSP a move is priced in O(1) and one sweep costs O(n k) evaluations plus O(n) per applied reversal; asymmetric matrices and the multi-trip objective use the full-evaluation kernel (local_search_generic with the 2-opt mask), O(n) per candidate move. Don't-look bits skip nodes scanned earlier, so the first sweep that changes nothing re-activates every node and the descent converges only when the following full sweep changes nothing either: a converged tour admits no improving 2-opt move among the candidate edges (every 2-opt move with n_candidates=None). The result is never worse than init.

References

.. [1] G. A. Croes, "A method for solving traveling-salesman problems", Operations Research 6 (1958) 791-812. .. [2] J. L. Bentley, "Fast algorithms for geometric traveling salesman problems", ORSA Journal on Computing 4 (1992) 387-411. .. [3] D. S. Johnson and L. A. McGeoch, "The traveling salesman problem: a case study in local optimization", in Local Search in Combinatorial Optimization, Wiley, 1997.

Examples:

>>> import numpy as np
>>> from skroute import TwoOpt
>>> from skroute.datasets import load_tsp
>>> wi = load_tsp("wi29")
>>> C = wi.distance_matrix()
>>> two = TwoOpt().fit(C, labels=wi.labels)
>>> two.cost_ / wi.optimal_tour_length < 1.20  # the fast-tier tolerance
True
>>> two.stop_reason_, two.n_iter_ == len(two.history_), bool(np.all(np.diff(two.history_) <= 0))
('converged', True, True)
>>> full = TwoOpt(n_candidates=None).fit(C, labels=wi.labels)  # full neighbourhood
>>> full.cost_ <= two.cost_
True
>>> TwoOpt(first_improvement=False, max_passes=10)
TwoOpt(first_improvement=False, max_passes=10)

OrOpt ¶

OrOpt(max_segment: int = 3, init: Any = 'nearest_neighbour', n_candidates: int | None = 10, max_passes: int = 50, verbose: int = 0)

Bases: BaseRouter

Or-opt descent: relocate segments of one to max_segment consecutive nodes.

Starts from init and, for every active node, tries to move each segment starting there (lengths 1..max_segment) next to one of the candidates of either segment end — after it or before it, forward or (on symmetric matrices) reversed — applying the first relocation that shortens the tour. Candidate lists and don't-look bits keep a sweep at O(n k).

Parameters:

Name	Type	Description	Default
`max_segment`	`int`	Longest segment relocated (Or-opt proper uses 3).	`3`
`init`	`'nearest_neighbour'`	Starting tour: the nearest-neighbour construction from the depot, or the `tour_`/ `route_` of another solver (labels; the depot may repeat).	`"nearest_neighbour"`
`n_candidates`	`int or None`	Size of the candidate lists (the `k` nearest neighbours of every node); `None` scans the full neighbourhood (`n - 1` nodes).	`10`
`max_passes`	`int`	Maximum number of outer iterations (one sweep over the active nodes each).	`50`
`verbose`	`int`	0 is silent; 1 logs every `max(1, max_passes // 10)` iterations and the stop; 2 logs every iteration. Records go to the `skroute` logger at INFO; enable them with `logging.basicConfig(level=logging.INFO)` or `skroute.set_log_level("INFO")`.	`0`

Attributes:

Name	Type	Description
`history_`	`ndarray of shape (n_iter_,), float64`	Cost after each outer iteration (non-increasing).
`n_iter_`	`int`	Outer iterations run.
`stop_reason_`	`{'converged', 'max_iter', 'callback'}`	`"converged"` when a sweep that started with every node active changed nothing, `"max_iter"` after `max_passes` sweeps, `"callback"` when the `callback` of `fit` returned `True`.

Notes

Supports: symmetric and asymmetric matrices, multi-trip objective; deterministic.

Callback events (D30): "start" carries the init tour with extra["moves"] (the listed descents, ["or_opt"]); each "iteration" event's tour is the working tour (also the best), with extra["moves_applied"] equal to ["or_opt"] when the sweep changed the tour ([] otherwise) and extra["gain"] the sweep's cost change.

One outer iteration = one call of the core's or_opt_descent with max_passes=1 (SPEC §4.3); the pos, candidate and don't-look-bit buffers persist across iterations. On a symmetric plain TSP both orientations of the moved segment are tried with O(1) deltas and a segment is re-inserted only next to a candidate closer than the edge removed at that end (Bentley's pruning, a heuristic: a relocation whose whole gain comes from closing the gap it leaves is not generated); the first sweep that changes nothing re-activates every node and the descent converges only when the following full sweep changes nothing either. Asymmetric matrices and the multi-trip objective use the full-evaluation kernel (local_search_generic with the Or-opt mask, no reversal), O(n) per candidate move, which enumerates every forward relocation next to a candidate. Or-opt alone leaves crossing edges that 2-opt would remove: for a plain descent prefer LocalSearch, which alternates both.

References

.. [1] I. Or, "Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking", PhD thesis, Northwestern University, 1976. .. [2] J. L. Bentley, "Fast algorithms for geometric traveling salesman problems", ORSA Journal on Computing 4 (1992) 387-411.

Examples:

>>> import numpy as np
>>> from skroute import OrOpt
>>> from skroute.datasets import load_tsp
>>> wi = load_tsp("wi29")
>>> oo = OrOpt().fit(wi.distance_matrix(), labels=wi.labels)
>>> oo.cost_ / wi.optimal_tour_length < 1.25  # the fast-tier tolerance
True
>>> oo.stop_reason_, oo.n_iter_ == len(oo.history_), bool(np.all(np.diff(oo.history_) <= 0))
('converged', True, True)
>>> OrOpt(max_segment=2)
OrOpt(max_segment=2)

LocalSearch ¶

LocalSearch(moves: tuple[str, ...] | str = ('two_opt', 'or_opt'), first_improvement: bool = True, max_segment: int = 3, init: Any = 'nearest_neighbour', n_candidates: int | None = 10, max_passes: int = 50, verbose: int = 0)

Bases: BaseRouter

Alternating 2-opt / Or-opt descent with candidate lists and don't-look bits.

Starts from init and, in every outer iteration, runs one pass of each listed descent (moves, in order) with the pos, candidate and don't-look-bit buffers persisting across passes. Nodes whose tour neighbours were changed by one move are re-activated for the other, so the search stops only at a tour that no listed move improves.

Parameters:

Name	Type	Description	Default
`moves`	`tuple of {"two_opt", "or_opt"}`	Descents run in each outer iteration, in this order. A single name is accepted as a string. `"swap"` is not available here (it exists only in the generic kernel's mask).	`("two_opt", "or_opt")`
`first_improvement`	`bool`	2-opt applies the first improving move found for a node (`True`) or scans the node's whole candidate neighbourhood and applies the best (`False`). Honoured only on the symmetric plain-TSP path; the generic path (asymmetric or multi-trip) is always first-improvement.	`True`
`max_segment`	`int`	Longest segment relocated by Or-opt (segments of `1..max_segment` nodes).	`3`
`init`	`'nearest_neighbour'`	Starting tour: the nearest-neighbour construction from the depot, or the `tour_`/ `route_` of another solver (labels; the depot may repeat).	`"nearest_neighbour"`
`n_candidates`	`int or None`	Size of the candidate lists (the `k` nearest neighbours of every node); `None` scans the full neighbourhood (`n - 1` nodes), which gives a markedly better local optimum at small `n` for a higher cost per pass.	`10`
`max_passes`	`int`	Maximum number of outer iterations.	`50`
`verbose`	`int`	0 is silent; 1 logs every `max(1, max_passes // 10)` iterations and the stop; 2 logs every iteration. Records go to the `skroute` logger at INFO; enable them with `logging.basicConfig(level=logging.INFO)` or `skroute.set_log_level("INFO")`.	`0`

Attributes:

Name	Type	Description
`history_`	`ndarray of shape (n_iter_,), float64`	Cost after each outer iteration (non-increasing).
`n_iter_`	`int`	Outer iterations run.
`stop_reason_`	`{'converged', 'max_iter', 'callback'}`	`"converged"` when an iteration that started with every node active returned a zero gain for every listed move, `"max_iter"` after `max_passes` iterations, `"callback"` when the `callback` of `fit` returned `True`.

Notes

Supports: symmetric and asymmetric matrices, multi-trip objective; deterministic.

Callback events (D30): "start" carries the init tour with extra["moves"] (the listed descents, in order); each "iteration" event's tour is the working tour (also the best: a descent never goes uphill), with the extra keys moves_applied (the listed moves whose descent changed the tour in that iteration) and gain (the iteration's total cost change, <= 0).

One outer iteration = one call of each listed descent kernel with max_passes=1 (SPEC §4.3). Symmetric plain TSP uses Bentley's neighbour-list descents with O(1) move deltas: one pass is O(n k) delta evaluations plus O(n) per applied reversal. Because don't-look bits skip nodes scanned earlier, the first iteration that changes nothing re-activates every node and convergence is declared only when the following full sweep changes nothing either, so a converged tour admits no improving 2-opt move among the candidate edges (Or-opt's pruning is a heuristic: it re-inserts a segment only next to a candidate closer than the edge it removes). Asymmetric matrices and the multi-trip objective use the full-evaluation kernel (O(n) per candidate move, Or-opt without reversal): fine up to a few thousand nodes.

References

.. [1] G. A. Croes, "A method for solving traveling-salesman problems", Operations Research 6 (1958) 791-812. .. [2] I. Or, "Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking", PhD thesis, Northwestern University, 1976. .. [3] J. L. Bentley, "Fast algorithms for geometric traveling salesman problems", ORSA Journal on Computing 4 (1992) 387-411.

Examples:

>>> import numpy as np
>>> from skroute import LocalSearch
>>> from skroute.datasets import load_tsp
>>> wi = load_tsp("wi29")
>>> ls = LocalSearch().fit(wi.distance_matrix(), labels=wi.labels)
>>> ls.cost_ / wi.optimal_tour_length < 1.12  # the fast-tier tolerance
True
>>> ls.stop_reason_, ls.n_iter_ == len(ls.history_), bool(np.all(np.diff(ls.history_) <= 0))
('converged', True, True)
>>> LocalSearch(moves=("or_opt",), n_candidates=None)
LocalSearch(moves=('or_opt',), n_candidates=None)

IteratedLocalSearch ¶

IteratedLocalSearch(n_iter: int = 1000, patience: int | None = 100, perturbation_strength: int = 1, acceptance: str = 'better', temperature: float | None = None, local_search: tuple[str, ...] | str | None = ('two_opt', 'or_opt'), n_candidates: int | None = 10, init: Any = 'nearest_neighbour', time_limit: float | None = None, random_state: Any = None, verbose: int = 0)

Bases: BaseRouter

Iterated local search: double-bridge kicks over a 2-opt / Or-opt local optimum.

Descends from init to a local optimum, then repeats: copy the incumbent, apply perturbation_strength kicks, descend to a new local optimum, accept it when better (or by a Metropolis rule) and remember the best tour seen. The kick is a double bridge (A B C D -> A C B D), which no 2-opt or Or-opt move can undo, so every iteration explores a genuinely new basin. This is the recommended default solver.

Parameters:

Name	Type	Description	Default
`n_iter`	`int`	Maximum number of outer iterations (kick + descent).	`1000`
`patience`	`int or None`	Stop after this many iterations without improving the best tour; `None` disables.	`100`
`perturbation_strength`	`int`	Number of kicks applied per iteration.	`1`
`acceptance`	`('better', 'metropolis')`	`"better"` moves to the new local optimum only when it is strictly better; `"metropolis"` also accepts one that is not worse, and a worse one with probability `exp(-(new - current) / temperature)`.	`"better"`
`temperature`	`float or None`	Fixed temperature of the Metropolis rule; `None` uses 0.5 % of the absolute cost of the `init` tour, or `1.0` when that cost is zero (an all-zero matrix), so the rule is always defined. Ignored under `acceptance="better"`.	`None`
`local_search`	`tuple of {"two_opt", "or_opt"}, str or None`	Descents run in every iteration, in this order (a single name is accepted as a string); `None` disables the descent, leaving a random walk of kicks.	`("two_opt", "or_opt")`
`n_candidates`	`int or None`	Size of the candidate lists of the descents; `None` = the full neighbourhood.	`10`
`init`	`('nearest_neighbour', 'random')`	Starting tour: the nearest-neighbour construction from the depot, a random permutation, or the `tour_`/`route_` of another solver (labels; the depot may repeat).	`"nearest_neighbour"`
`time_limit`	`float or None`	Wall-clock budget in seconds, checked once per outer iteration; `None` disables. A run stopped by `time_limit` is not reproducible bit for bit.	`None`
`random_state`	`(int, Generator or None)`	Seed of the kicks (and of the Metropolis draws and `init="random"`). Two fits with the same integer seed on the same machine are bit-identical. A `Generator` is used in place and advanced.	`None`
`verbose`	`int`	0 is silent; 1 logs every `max(1, n_iter // 10)` iterations and the stop; 2 logs every iteration. Records go to the `skroute` logger at INFO; enable them with `logging.basicConfig(level=logging.INFO)` or `skroute.set_log_level("INFO")`.	`0`

Attributes:

Name	Type	Description
`history_`	`ndarray of shape (n_iter_,), float64`	Best cost seen after each outer iteration (non-increasing).
`n_iter_`	`int`	Outer iterations run (the initial descent is not counted).
`stop_reason_`	`{'max_iter', 'patience', 'time_limit', 'callback'}`	Why the search stopped (`"callback"`: the `callback` of `fit` returned `True`).

Notes

Supports: symmetric and asymmetric matrices, multi-trip objective; stochastic.

Callback events (D30): "start" carries the init tour before the initial descent; each "iteration" event's tour is the candidate that iteration produced (kick + descent) and its best_tour the incumbent best, with the extra keys kick (the cut positions of every kick applied, as tuples), accepted (whether the candidate replaced the current tour) and current_cost.

The descent is the alternating scheme of LocalSearch, run to convergence after every kick. On a symmetric plain TSP it uses O(1) move deltas, candidate lists and don't-look bits: only the nodes a kick touched start active, so the re-descent from the kick's endpoints is cheap, but convergence is declared only when a sweep that started with every node active changed nothing, so every iteration costs at least one full O(n k) sweep per listed move plus the O(n) copies — a fraction of a millisecond per iteration at n = 1000 with the default k = 10. Asymmetric matrices and the multi-trip objective use the full-evaluation kernel, O(n) per candidate move, so that confirming sweep is O(n² k) and is repeated after every kick: one descent is fine up to a few thousand nodes, but at the default n_iter/patience the iterated search is comfortable up to a few hundred nodes on those problems; above that, lower n_iter or set time_limit.

For n >= 8 the kick is a double bridge with cut positions 1 <= p1 < p2 < p3 <= n - 1 drawn without replacement. Below 8 nodes it is the reversal of a random segment tour[i..j] with (i, j) uniform over the pairs 1 <= i < j <= n - 1; on a symmetric matrix the whole-body reversal (1, n - 1) is left out, because it is the same closed tour driven backwards and changes no edge (at n = 3 the swap of positions 1 and 2 is the only kick). All randomness is drawn in Python from random_state before each iteration, so results are reproducible and independent of the platform's kernels.

References

.. [1] O. Martin, S. W. Otto and E. W. Felten, "Large-step Markov chains for the traveling salesman problem", Complex Systems 5 (1991) 299-326. .. [2] H. R. Lourenço, O. C. Martin and T. Stützle, "Iterated local search: framework and applications", in Handbook of Metaheuristics, Springer, 2010. .. [3] D. S. Johnson and L. A. McGeoch, "The traveling salesman problem: a case study in local optimization", in Local Search in Combinatorial Optimization, Wiley, 1997.

Examples:

>>> from skroute import IteratedLocalSearch
>>> from skroute.datasets import load_tsp
>>> wi = load_tsp("wi29")  # Western Sahara, optimum 27603; labels are the file's 1-based ids
>>> ils = IteratedLocalSearch(random_state=0).fit(wi.distance_matrix(), labels=wi.labels)
>>> ils.cost_ / wi.optimal_tour_length < 1.03  # the fast-tier tolerance
True
>>> int(ils.route_[0]) == int(ils.route_[-1]) == int(ils.depot_) == 1
True
>>> ils.n_iter_ == len(ils.history_) and ils.stop_reason_ in {"patience", "max_iter"}
True
>>> again = IteratedLocalSearch(random_state=0).fit(wi.distance_matrix(), labels=wi.labels)
>>> again.tour_.tolist() == ils.tour_.tolist()  # same seed, same machine: bit-identical
True
>>> IteratedLocalSearch(acceptance="metropolis", local_search=("two_opt",), random_state=3)
IteratedLocalSearch(acceptance='metropolis', local_search=('two_opt',), random_state=3)