Does local search always find the best solution?

No. Guarantees depend on the method and assumptions, and practical finite runs commonly provide a good candidate without proving global optimality.

Must each move improve the score?

No. That is characteristic of strict hill climbing, while other methods may accept equal or worse scores to explore further.

What makes two solutions neighbors?

The move definition chosen for the problem, such as swapping two route stops or changing one variable's value.

AI Glossary / Graphs and symbolic AI / Beginner

Local search

Definition

Local search is a family of methods that looks for useful solutions by modifying current candidate solutions and evaluating nearby alternatives. It commonly focuses on the quality of a candidate rather than the path used to reach it. The meaning of “nearby” comes from a defined neighborhood, such as swapping two assignments or changing one parameter.

What it means

Many optimization problems have too many possible solutions to inspect individually. A schedule, for example, may have an enormous number of possible task arrangements. Local search starts with an arrangement and explores changes that might improve a chosen score.

“Local” describes the relationship between candidates, not where the computation runs or whether the data stays on a device. Two schedules are neighbors if the method's move rule connects them. Their physical locations are irrelevant. The choice of move rule strongly affects which improvements are easy to discover and which require crossing less attractive intermediate arrangements.

How it works

Specify a candidate representation, an objective or evaluation function, and a neighborhood. Choose an initial candidate, generate some neighboring candidates, and decide which move to accept. Repeat until a stopping condition is reached, such as a time budget, an acceptable score, or the absence of an allowed improvement.

Different methods use different acceptance rules. Hill climbing accepts improving moves. Simulated annealing can sometimes accept worse moves, while other approaches use memory or restart from new candidates. Many local-search methods retain a current candidate and the best candidate found, although some variants maintain larger collections.

Hard constraints also need explicit treatment. Moves may preserve feasibility, a repair procedure may restore it, or violations may receive penalties. A low penalty score is not automatically a feasible solution unless the constraint handling guarantees that interpretation.

Three practical examples

1. A delivery planner swaps stops in a proposed route and checks whether total modeled travel cost decreases, while preserving required visits and capacity rules.

2. A staff scheduler moves one shift assignment at a time to reduce preference penalties. Required coverage and qualification constraints still need separate enforcement.

3. A design tool adjusts a small number of settings and evaluates the resulting simulation score. The evaluation cost can determine how many neighboring designs it can realistically inspect.

Think of it this way

Think of improving a room layout by moving one item at a time. Each change is judged against a goal such as walking space or access to equipment. A convenient arrangement may emerge without drawing every possible layout.

The analogy also shows the limitation: a much better layout might require moving two heavy items together, even though moving either alone makes the room worse. A neighborhood restricted to single-item moves can hide that opportunity from a method that accepts only immediate improvements.

Worked example

Consider an invented minimization problem with five candidate states: A has cost 10, B cost 7, C cost 8, D cost 3, and E cost 2. Neighbor connections are undirected and consist only of A-B, A-C, C-D, and D-E.

A steepest-improvement search starting at A compares B and C, then chooses B because 7 is lower than 8. At B, its only neighbor is A with cost 10. The search stops at B, a local minimum under this neighborhood.

Yet E has the lowest cost, 2. Reaching it from B requires B-A-C-D-E, initially worsening the score from 7 to 10. An improving-only rule cannot take that first step. Starting instead at C allows the improving sequence C-D-E, with costs 8, 3, and 2.

This hand trace establishes the behavior on the stated graph. It illustrates why starting points and acceptance rules matter, without claiming that random restarts or occasional worse moves guarantee a global optimum within a fixed time budget.

Illustrative case study

Fictional case: Willow Events has a workable room allocation for a conference but wants to reduce walking between related sessions. Its prototype local search swaps two room assignments and scores the resulting attendee travel estimate.

The team first ensures that swaps respect room capacity and equipment needs. It then compares several starting allocations using the same evaluation budget. When the best score stops improving, staff describe it as the best arrangement found, not as a proven optimum. They review whether the travel estimate reflects actual attendee patterns. This hypothetical case reports no measured time saving or satisfaction improvement.

Common misconceptions and mistakes

Do not confuse a local optimum with a global optimum. A local optimum is defined relative to the chosen neighborhood; adding a different move can change that status.

Do not assume every local-search method uses gradients or continuous variables. Discrete swaps and reassignment moves are common. Conversely, a small numerical parameter change may be a neighborhood move in continuous optimization.

Finally, improvement in the encoded objective may not mean improvement in the real task. Missing constraints, inaccurate costs, and poorly chosen trade-offs can reward undesirable solutions. Search quality and model quality require separate examination.

Business use

Local search can be practical when a good candidate is valuable quickly and exhaustive optimization is difficult. Set a reproducible evaluation budget and compare against a simple baseline, such as the existing schedule or a straightforward construction rule.

Record the neighborhood, initialization, random seed where relevant, objective, and stopping reason. Report feasibility and the best observed objective separately. Where an independent lower bound or exact solution is available, use it to assess the remaining gap. Avoid treating a long run with no improvement as a mathematical certificate of optimality.

Check your understanding

Why does the worked example stop at B despite E having a lower cost?

Answer: B's only neighbor is worse, and the chosen rule accepts only improvements. The route to E requires an initial increase in cost that this rule forbids.

Related terms

Learn next

Compare hill climbing and simulated annealing on a small, explicitly drawn neighborhood graph. Track the current candidate separately from the best candidate found, and note how changing the move rule changes the local optima.

Sources

Carnegie Mellon University, local-search course notes and algorithm distinctions: https://www.cs.cmu.edu/~15281/coursenotes/localsearch/

The five-state graph and fictional conference case are original teaching examples. No optimization software run or business performance result is claimed.

Previous: Local regression Next: Local tangent space alignment