Local Search for CSP

Hill climbing is a fundamental local search metaheuristic that iteratively moves to a neighboring state with a lower cost (fewer constraint violations). It gets stuck in local minima—states where no immediate neighbor is better, even if a superior global solution exists. Variants like stochastic hill climbing randomly choose among improving moves to escape some plateaus.

• Mechanism: Evaluate all neighbors of the current state. Move to the neighbor with the highest evaluation (lowest cost).
• Limitation: Prone to getting trapped in local optima, not global ones.
• Use Case: Simple, fast optimization for problems where a 'good enough' solution is acceptable.

The min-conflicts heuristic is a specialized, highly effective algorithm for constraint satisfaction, famously used to solve the million-queens problem. At each step, it selects a variable that is currently involved in a conflict (violating a constraint) and assigns it the value that results in the minimum number of conflicts with other variables.

• Key Feature: Does not require a gradient; only needs to count conflicts.
• Efficiency: Often finds solutions for large CSPs in roughly linear time, far faster than systematic search.
• Application: Central to scheduling and configuration problems (e.g., class timetabling).

Simulated annealing probabilistically allows moves to worse states to escape local minima, inspired by the annealing process in metallurgy. The probability of accepting a worse move is controlled by a temperature parameter that gradually decreases according to a cooling schedule.

• Algorithm: Start with a high temperature (high probability of accepting bad moves). Randomly select a neighbor. Always move if it's better; if worse, move with probability e^(-ΔE/T).
• Cooling: Slowly reduce temperature, making the search more greedy over time.
• Advantage: Asymptotically converges to a global optimum given a slow enough cooling schedule.

Tabu search enhances local search by using memory to avoid cycling and explore new regions of the search space. It maintains a tabu list—a short-term memory of recently visited states or moves—which are forbidden for a certain number of iterations.

• Core Mechanism: Even if a move is the best available, it is prohibited if it's on the tabu list (unless it meets an aspiration criterion, like finding a new global best).
• Memory Structures: Can include long-term memory to intensify search in promising areas or diversify into unexplored ones.
• Use Case: Effective for complex combinatorial optimization problems like vehicle routing and job-shop scheduling.

Genetic algorithms are a population-based metaheuristic inspired by natural selection. They maintain a set of candidate solutions (a population) and evolve them over generations using selection, crossover (recombination), and mutation operators.

• Process: 1) Evaluate fitness (e.g., inverse of conflict count). 2) Select parent solutions biased by fitness. 3) Crossover parents to produce offspring. 4) Mutate offspring randomly. 5) Form new population.
• Strength: Explores multiple areas of the search space in parallel, good for rugged landscapes.
• Representation: Requires encoding a CSP assignment as a chromosome (e.g., a string of values).

WalkSAT is a prominent local search algorithm specifically for the Boolean Satisfiability Problem (SAT). It combines a greedy hill-climbing component with random walks. At each step, it picks an unsatisfied clause and flips the truth value of a variable within that clause.

• Variable Choice: With probability p, flip a random variable in the clause. With probability 1-p, flip the variable in the clause that minimizes the number of newly unsatisfied clauses (the break count).
• Noise Parameter: The p parameter balances greediness and randomness.
• Performance: One of the most effective stochastic algorithms for hard random SAT instances and real-world benchmarks.

A Constraint Satisfaction Problem (CSP) is the formal framework that local search algorithms aim to solve. It is defined by:

• A set of variables {X₁, X₂, ..., Xₙ}.
• A domain Dᵢ for each variable, listing its possible values.
• A set of constraints that specify allowable or forbidden combinations of values for subsets of variables.

The goal is to find a complete assignment of values to all variables that satisfies every constraint. This abstract model directly represents real-world problems like scheduling, configuration, and routing.

The min-conflicts heuristic is the core decision rule within many local search algorithms for CSPs, including the famous Min-Conflicts algorithm. At each iteration, it:

1. Selects a variable that is currently violating one or more constraints (a conflicted variable).
2. Evaluates all possible values in that variable's domain.
3. Assigns the value that results in the minimum number of conflicts with neighboring variables. This greedy, local optimization step is what drives the search toward a valid solution, making it the defining mechanism for hill-climbing in constraint spaces.

Hill climbing is the foundational optimization paradigm that underpins local search for CSPs. It operates as follows:

• Start with a complete, random assignment (which likely violates constraints).
• Iteratively make a small, local change to the assignment (e.g., changing one variable's value).
• Accept the change only if it improves the objective function (e.g., reduces the total number of constraint violations). The algorithm gets stuck in local optima—states where no single change yields improvement, but a better global solution may exist. Advanced techniques like random restarts or simulated annealing are used to escape these plateaus.

Backtracking search is a complete search algorithm that contrasts sharply with local search. It is a systematic, depth-first exploration of the search space:

• It builds assignments incrementally, one variable at a time.
• Before assigning a value, it checks consistency with existing assignments (constraint propagation).
• If a variable has no legal values left, it backtracks to the previous variable and tries a different value. While guaranteed to find a solution if one exists, it can be slow for large problems. Local search is often preferred when an approximate or 'good enough' solution is acceptable and runtime is critical.

A Constraint Optimization Problem (COP) generalizes a CSP by adding an objective function to be minimized or maximized. The goal is no longer just to find a feasible solution, but the best feasible solution according to a metric (e.g., cost, profit, distance). Local search is exceptionally well-suited for COPs. Algorithms like hill climbing or simulated annealing can directly use the objective function to guide improvements. For example, in a vehicle routing problem, a local search would iteratively tweak routes to minimize total travel distance while respecting all delivery constraints.

Simulated annealing is a probabilistic local search algorithm designed to escape local optima, making it more robust than basic hill climbing for complex CSPs and COPs. It is inspired by the annealing process in metallurgy.

• It occasionally accepts moves that worsen the objective function (increase conflicts).
• The probability of accepting a bad move is controlled by a temperature parameter, which gradually decreases over time.
• Early in the search, with high temperature, it explores the search space widely.
• As temperature cools, it converges to a (hopefully global) optimum, behaving more like greedy hill climbing. This provides a principled trade-off between exploration and exploitation.