Introduction to Constraint Satisfaction and Local Search

Principles of Constraint Satisfaction Problems (CSP)

• The primary objective in a Constraint Satisfaction Problem (CSP) differs from traditional state-space or search problems. In standard search, the focus is on the path or sequence of steps taken to reach a goal. In CSP, the interest lies entirely in what the goal state looks like.

• A solution in CSP is defined as an assignment of specific values to the variables present in the problem such that all established constraints are satisfied.

• Standard search algorithms like Depth-First Search (DFS) form the core of backtracking algorithms used to solve CSPs.

Strategic Improvements to Backtracking

• The efficiency of backtracking can be enhanced through several methodologies focusing on memory and speed optimization:

  • Variable Ordering: Choosing the specific sequence in which variables are assigned.

  • Value Ordering: Selecting the order in which values from a domain are assigned to a variable.

  • Early Failure Detection: Algorithms like Forward Checking and the AC-3 (Arc Consistency Algorithm #3) improve efficiency by identifying inconsistent assignments before the search proceeds too deep.

Domain Splitting

• Domain splitting is a technique used to reduce search complexity by breaking a large search space into smaller, manageable subspaces.

• Process of Domain Splitting:

  • A variable is selected from the set.

  • The domain of that variable is split into two or more smaller ranges or subsets (typically two equal subdomains).

  • A new CSP instance is created for each resulting split.

  • Each sub-problem is solved separately.

• Advantages:

  • Enables parallel computation, effectively cutting the total time required to find a solution.

  • Allows for targeted pruning of search branches.

• Example Case: Given variables $x, y, z$ and a constraint involving all three. If the domain of $x$ is split, the root of the backtracking tree (empty assignment) generates child nodes representing the split domains. For instance, if $x \in \{1, 2, 3, 4\}$, one sub-problem might process $x \in \{1, 2\}$ while another processes $x \in \{3, 4\}$.

Variable Elimination Algorithm

• Variable elimination is an alternative approach to backtracking that simplifies a problem by removing variables one by one and building more complex constraints in their place.

• Core Logic: Eliminate a variable by joining all constraints where it appears and projecting that joined constraint onto the remaining variables. This continues until only one variable remains.

• Algorithmic Steps:

  1. If only one variable remains, return the intersection of its unary constraints.

  2. Select a variable (e.g., $x$) to eliminate.

  3. Join all constraints where $x$ appears to form a new temporary constraint (e.g., $R_1$).

  4. Project $R_1$ onto all variables involved in the constraint except $x$, forming a new constraint ($R_2$).

  5. Replace all original constraints containing $x$ with the new constraint $R_2$.

  6. Repeat the process iteratively.

• Backtracking for Solution Retrieval: Once the final constraint involving the last variable is solved, the algorithm works backward through the stored tables to infer the values for the eliminated variables. This method is capable of finding all possible solutions to a problem.

Detailed Example of Variable Elimination

• Problem Constraints:

  • $a \neq b$

  • $e \neq c$

  • $e \neq d$

  • c > d

  • $e - a = \text{odd}$

• Domains:

  • $c \in \{3, 4\}$

  • $d \in \{2, 3\}$

  • $e \in \{2, 3, 4\}$

• Elimination of Variable $c$:

  1. Identify constraints involving $c$: c > d and $c \neq e$.

  2. Create tables for valid combinations:

     • For c > d: $\{(3, 2), (4, 2), (4, 3)\}$.

     • For $c \neq e$: $\{(3, 2), (3, 4), (4, 2), (4, 3)\}$.

  3. Join these tables to form $R_1$ (combinations of $c, d, e$):

     • Row 1: $c=3, d=2, e=2$

     • Row 2: $c=3, d=2, e=4$

     • Row 3: $c=4, d=2, e=2$

     • Row 4: $c=4, d=2, e=3$

     • Row 5: $c=4, d=3, e=2$

     • Row 6: $c=4, d=3, e=3$

  4. Project onto $d, e$ (remove variable $c$): The resulting constraint on $(d, e)$ includes unique pairs: $(2, 2), (2, 4), (2, 3), (3, 2), (3, 3)$.

  5. The graph is updated by adding an arc between $d$ and $e$ representing this new complex constraint, while variable $c$ is removed.

Local Search Strategies and Optimization

• Local search is primarily used for optimization problems where the path to the solution is irrelevant, but the goal is to find a configuration that minimizes or maximizes a specific criterion.

• State Space: The set of all possible configurations of values assigned to variables.

• Characteristics:

  • Does not guarantee finding a solution (completeness).

  • Does not guarantee an optimal solution.

  • Operates "locally," meaning it only considers immediate neighbors rather than the global problem structure.

  • Beneficial for finding "good enough" solutions very quickly.

Generic Local Search Framework

• Input: Features (variables).

• Output: Assignment of values to variables.

• Workflow:

  1. Initialize: Start with a random initial assignment of values to all variables.

  2. Evaluate: Check the current state against a stopping criterion.

  3. Successor Selection: Generate neighbors by changing specific variable values.

  4. Update: Move to a successor state based on the selection logic.

  5. Loop: Continue until the stopping criteria are met, then return the best result found.

Iterative Best Improvement (IBI)

• IBI is a greedy local search strategy.

• Evaluation Function: Uses a heuristic function $h(n)$, which in CSP contexts typically represents the number of violated constraints.

• Greedy Choice: IBI evaluates all possible neighbors of the current state and selects the one that minimizes the number of conflicts (or maximizes happiness).

The n-Queens Problem as Optimization

• The n-Queens problem (e.g., a $4 \times 4$ board with 4 queens) can be converted from a CSP to an optimization problem.

• Constraints: Queens cannot attack each other vertically, horizontally, or diagonally.

• Optimization Goal: Minimize the number of attacks (conflicts).

• Local Search Application:

  • Start with a random placement of queens.

  • Count initial conflicts (e.g., 5 conflicts).

  • Move one queen at a time to different rows within its column and re-evaluate the heuristic.

  • Continue moving until reaching a state where $h(n) = 0$.

Hill Climbing Algorithms

• Simple Hill Climbing: Unlike Iterative Best Improvement, which evaluates all neighbors, Simple Hill Climbing selects the first successor that shows any improvement over the current state.

• Heuristic Calculation for 8-Queens Problem:

  • Successful outcomes: Solving the problem takes an average of 4 steps.

  • Failure outcomes: Hill climbing gets stuck in a local minimum 86% of the time, typically taking about 3 steps before failing.

  • Success Rate: Only 14% of random initializations lead to a solution.

  • Expected Total Moves with Random Restarts:         $3 \times \frac{0.86}{0.14} + 4 \approx 22 \text{ moves}$

Failures and Issues in Local Search

• Local Maxima/Minima: The algorithm reaches a point where all neighbors are worse than the current state, but it is not the global optimum.

• Plateaus (Shoulders): An area of the search space where the evaluation function is flat, providing no guidance on which direction to move.

• Ridges: A series of local maxima where the algorithm may need to temporarily move to a "worse" state before it can improve further.

Advanced Local Search Modifications

• Hill Climbing with Side Moves: To navigate plateaus, the algorithm is modified to accept transitions to neighbors even if the heuristic value is the same ($h(n_{next}) = h(n_{current})$).

  • In the 8-queens problem, allowing side moves increases the success rate to 94% (6% failure rate).

  • Cost of Side Moves: It takes 21 steps on average to succeed and 65 steps on average to determine the algorithm is stuck. The total average moves increase to approximately 25, meaning while the success rate is higher, it takes more time per instance.

• BFS-Integrated Local Search: This hybrid approach uses a small Breadth-First Search (BFS) to find better neighbors when Hill Climbing gets stuck in a local minimum. However, this reintroduces the memory inefficiency of BFS due to the need for a queue.

• Tabu Search: A refinement of local search that maintains a "Tabu list" (similar to a closed list). It records recently visited states and forbids returning to them for a set duration, effectively preventing the algorithm from cycling through the same configurations and helping it escape local minima.