Local Search for CSPs

Overview

Backtracking search is complete but can be slow on large problems. Local search trades completeness for speed: start with a complete (possibly inconsistent) assignment and iteratively repair constraint violations.

Key insight: For problems with many solutions densely distributed in the search space (like n-queens for large n), local search is dramatically faster than backtracking.

Min-Conflicts Algorithm

The canonical local search algorithm for CSPs.

function MIN-CONFLICTS(csp, max_steps) returns solution or failure
    current ← an initial complete assignment for csp  // random or greedy
    for i = 1 to max_steps do
        if current is a solution for csp then return current
        var ← a randomly chosen conflicted variable from csp
        value ← the value v in DOMAIN(var) that minimizes CONFLICTS(var, v, current, csp)
        set var = value in current
    return failure

How It Works

  1. Start: assign all variables randomly (or greedily).
  2. At each step: pick a conflicted variable (one that violates ≥ 1 constraint).
  3. Reassign it to the value that minimizes the total number of violated constraints.
  4. Repeat until no conflicts remain (solution found) or step limit exceeded.

Performance: The n-Queens Result

Minton et al. (1992) showed that min-conflicts solves n-queens in O(n) expected steps, independent of n. For n = 1,000,000, it finds a solution in under a second.

Why it works: The n-queens problem has an extraordinarily high density of solutions — roughly n!/3 solutions for large n — so local search rarely gets stuck. Almost every move reduces the conflict count.

Contrast: Backtracking on n-queens scales poorly — exponential in the worst case.

The Search Landscape

Local search navigates a landscape where: - States: complete assignments - Value (height): number of constraint violations (we minimize) - Moves: reassign one variable to a new value

Pathologies

Problem Description
Local minimum Every move increases violations, but current is not a solution
Plateau Many moves leave violation count unchanged; hard to make progress
Ridge Narrow path of low-violation states; hard to stay on it

Escape Strategies

Strategy How It Works Tradeoff
Random restart Restart from a new random assignment when stuck Simple; effective if solutions dense
Random walk With probability p, take a random move instead of min-conflict Escapes plateaus; p ≈ 0.1–0.3 works well
Tabu search Maintain a tabu list of recently visited states; forbid revisiting Prevents cycling; memory cost
Simulated annealing Accept worsening moves with probability e^(−Δ/T) Theoretically complete; slow convergence
Constraint weighting Increase weight of repeatedly violated constraints Guides search toward hard constraints

Min-Conflicts vs. Backtracking

Property Backtracking + MAC Min-Conflicts
Complete Yes No (may miss solution)
Optimal N/A N/A
Best for Sparse/tight problems, proofs of unsatisfiability Dense solution spaces, large n
Memory O(n·d) O(n)
n-queens (n=1M) Intractable < 1 second
Scheduling repair Slow (recomputes from scratch) Fast (local repair)

Rule of thumb: Use backtracking when you need completeness or need to prove UNSAT. Use min-conflicts when the problem is highly satisfiable and large.

Constraint Optimization Problems (COPs)

When constraints are soft (preferences with costs), the goal is to minimize total violation cost. Local search variants:

COPs arise naturally in scheduling (minimize makespan), timetabling (minimize preference violations), and configuration (minimize cost).

Application to DynamICCL

The NCCL parameter configuration problem (choosing numThreads, chunkSize, algorithm, etc.) can be framed as a COP: minimize observed collective communication latency subject to feasibility constraints. Min-conflicts style local search could be used for online repair — if a running configuration becomes suboptimal (e.g., GPU topology changes), incrementally repair it by adjusting one parameter at a time to reduce latency, rather than re-running full RL policy evaluation.