Local search

Local search repeatedly improves a feasible solution within a specified neighborhood until no improving move remains. For an allocation, neighbors can transfer an item or exchange items between bidders while preserving the partition. A local optimum need not be a global optimum; restarting from several initial solutions can explore different basins.

An optimization neighborhood assigns to each feasible solution $x$ a set $N(x)$ of candidates reachable by the chosen elementary moves. It need not be a neighborhood in a previously chosen geometric metric, nor must reachability be symmetric. For minimization, a solution is locally optimal under these moves whenChanging $N$ can change that conclusion while leaving the objective function unchanged. Specifying the embedded local search is therefore part of specifying an iterated local search method.^[ref]

For a complete binary string example, let the feasible set contain all eight strings of length three. Assign $f(000)=0$, $f(111)=-1$, and $f(x)=1$ for the other six strings. With one-bit flips,so $000$ is a strict local optimum. Allowing flips of one or two bits adds $110,101,011$, but all six neighbors still cost $1$. Allowing three-bit flips finally reaches $111$, so $000$ ceases to be locally optimal. The best value in the entire feasible set is $-1$ throughout; the move rule changes what the local procedure can see.

For length $n$, the one-bit-flip neighborhood has $n$ members, while including all two-bit flips adds $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ members. A larger neighborhood may expose an improving move but cost more to examine. The corresponding directed graph has feasible solutions as vertices and a directed edge from $x$ to each member of $N(x)$. If this graph cannot reach a region from the initial solution, even repeated local moves cannot explore that region without a different move or a restart.

Iterated local search is a metaheuristic that alternates perturbation, local search and acceptance decisions. The local search improves candidates within a declared optimization neighborhood; perturbation helps reach other locally optimal solutions.^[ref]

For minimization, start with $s=\mathcal{L}(s_0)$ and generate $q=\mathcal{L}(P(s))$, where $\mathcal{L}$ performs local search and $P$ perturbs its input. Accepting only $f(q)<f(s)$ or accepting every candidate are two possible rules.^[ref]

For an original complete example, let feasible solutions be the integers $0$ through $6$, with neighbors differing by one and objective valuesStrictly improving local search starting at $0$ moves to $1$ and stops: its two neighbors have costs $4$ and $3$, both worse than $2$. Perturb the solution from $1$ to $4$, allowing a temporary rise to cost $4$. Local improvement then follows $4\to 5\to 6$, reaching cost $0$, which is the global minimum by inspection of the complete list. The perturbation escaped the first local minimum without requiring the local improvement rule itself to cross an uphill edge.

Perturbation and acceptance must work together: weak changes can return to the same local minimum. The authors’ travelling salesman problem comparison used ten runs of 120 seconds on a Pentium 266 MHz PC, illustrating why evaluation must specify the embedded search and computational budget.^[ref]

An iterated local search acceptance rule chooses the next current solution after a perturbation has been followed by local search. Let the current locally improved solution be $s$ and the new locally improved candidate be $q$, with a minimized objective function $f$. The decision concerns these search states, not just the potentially poor intermediate output of the local-search perturbation.^[ref]

One rule accepts only improvement:The paper calls this policy Better. Its current costs cannot increase, which follows immediately from the two cases. That property does not establish that the search will reach a global minimum. The RW rule instead retains the latest candidate regardless of cost, allowing movement among locally improved solutions.^[ref]

For an original numerical comparison, suppose $f(s)=10$. A perturbation temporarily raises the cost to18, and subsequent local search lowers it to12. Better rejects the candidate with cost12, while RW accepts it; neither decision is made by comparing10 with the intermediate18. If the same procedure instead reaches cost8, both accept.

A simulated annealing-type option accepts a worse candidate with probability $\exp [-(f(q)-f(s))/T]$, with $T>0$. At cost difference2 and $T=2$, this probability is $e^{-1}\simeq 0.368$. The temperature is a parameter of the rule, not a guarantee that a particular finite run escapes every trap.^[ref]

A permissive current-state rule can retain a candidate worse than an earlier result. Keeping a separate best-so-far solution preserves that result while allowing exploration. Report both the current-state acceptance policy and the best-result bookkeeping when comparing search runs.

A local-search perturbation deliberately changes the current solution before local search resumes. In iterated local search, the perturbation and improvement form a composite step: $s\mapsto \mathcal{L}(P(s))$, where $P$ changes the candidate and $\mathcal{L}$ applies the chosen local improvement procedure. The perturbation need not improve the objective function; a later iterated local search acceptance rule decides which improved candidate becomes current.^[ref]

A fully specified example shows why a weak perturbation can be ineffective. Let feasible solutions be the integers $0$ through $5$, with neighbors differing by one, and costsUse strictly improving, best-neighbor local search. Starting at5 is locally optimal: its only neighbor4 has cost3, above the current cost1. A one-step kick to4 is immediately undone by local improvement, which returns to5.

A different kick from5 to2 temporarily raises the cost to4, but the subsequent improving path is $2\to 1\to 0$, with costs $4\to 2\to 0$. The resulting candidate beats the old stopping point. These values are an original constructed example; they show how changing the perturbation can change which solution the same local search reaches.

Perturbation strength therefore concerns more than accepting a single worse local move. Too little change may repeatedly return to the same solution, while a nearly independent redraw can discard useful structure from the current candidate. Feasibility must also be handled explicitly: either the perturbation stays within the feasible set or the method specifies how an infeasible intermediate is repaired. Problem-specific moves and acceptance decisions must be evaluated together.^[ref]

A local search method that retains one current candidate and repeatedly chooses an improving neighbor of its objective. For a conflict-minimization constraint satisfaction problem, a candidate can assign all variables within their constraint domains while violating some inter-variable constraints; the objective counts those violations. Zero conflicts certifies a solution, while a positive-conflict local minimum need not certify impossibility. Plateaus and local minima motivate sideways moves, randomized choices and restarting. Prescribed variables must remain fixed in every initialization and move.

A repair method for a constraint satisfaction problem: choose a currently conflicted, movable variable, and assign a permitted value minimizing its number of violated constraints with the other variables held fixed. Tie handling can permit sideways moves. For the queens completion problem, keep prescribed rows fixed, select a conflicted unfixed row, and choose a column minimizing attacks. Never interpret failure to improve as proof that no solution exists.