Optimization vs. CSP: Choosing the Right Tool

A university schedule must assign every course to a time slot and room.

This is a textbook CSP. Every constraint is a hard requirement — a schedule with a single room conflict is invalid, not just "slightly worse." Backtracking with MRV and AC-3 can find valid schedules for hundreds of courses in seconds. A local search algorithm would struggle because moving a single class to fix one conflict might create another, and there is no smooth gradient to follow.

Sudoku’s all-different constraints, discrete domains, and rich constraint graph make it the ideal CSP. AC-3 preprocessing alone can solve easy puzzles by reducing all domains to single values. MRV + LCV + MAC handles hard puzzles efficiently. There is no "approximately solved" Sudoku — either all constraints are satisfied or the puzzle is unsolved.

Modern computers offer dozens of compatibility constraints: CPU socket type must match motherboard, total power draw must not exceed the power supply, RAM type must be supported. Selecting a valid combination of components is a CSP. Each constraint is hard (an incompatible build doesn’t work), and the goal is finding any valid configuration, possibly filtered by price afterward.

Finding the optimal tour through 100 cities is NP-hard — no known algorithm can guarantee the optimal in polynomial time. But finding a near-optimal tour is exactly what SA excels at. SA treats tour quality as a continuous objective, accepts small detours to escape local optima, and consistently finds tours within 1–3% of optimal.

There is no natural CSP formulation for TSP — there are no hard constraints beyond visiting each city exactly once, and satisfaction of that alone does not indicate a good solution.

Adjusting millions of weights to minimize prediction error is a continuous optimization problem. The objective function is differentiable, the state space is real-valued, and "good enough" accuracy is the goal. No constraint framework applies here — gradient-based optimization (or SA for non-differentiable functions) is the right tool.

Designing an antenna shape to maximize signal strength, or a bridge structure to minimize material while meeting safety specifications, involves continuous parameters and a quality metric. Local search or SA navigates the continuous design space effectively.

First, use CSP techniques to find any valid solution. Then, use local search to improve that solution by relaxing soft constraints or minimizing a secondary objective.

University scheduling uses this approach: first find a schedule with no hard violations, then optimize instructor preferences and student convenience.

Min-conflicts is a local search algorithm specifically designed for CSPs. It starts with a random (possibly invalid) assignment and repeatedly selects a variable that is involved in a constraint violation, reassigning it to the value that minimizes the total number of conflicts.

Min-conflicts solved million-variable n-queens problems that backtracking could not handle. It is the algorithm of choice for large, tightly constrained real-world scheduling.

Many real problems have both hard constraints (must satisfy) and soft constraints (prefer to satisfy, but can violate at a cost). Weighted CSPs assign a cost to each constraint violation; the goal becomes minimizing total cost rather than achieving zero violations. This blends CSP formulation with optimization objectives.