Unit 4 Overview: Optimization and Constraint Satisfaction

Unit 4: Optimization and Constraint Satisfaction — Overview

Connection to Unit 3: Last week you mastered search algorithms that systematically explore state spaces — BFS, DFS, A*, and heuristic functions. This week we push further: what do you do when the state space is simply too large to explore, or when the problem has a special structure of variables and constraints you can exploit?

Review: Comparing Search Algorithms →

Welcome to Week 4

This week shifts from finding any solution to finding the best solution — or from finding one valid assignment among millions. You will master two powerful problem-solving paradigms that tackle different kinds of challenges:

Optimization: Finding the best configuration when there are too many possibilities to search exhaustively
Constraint Satisfaction: Finding valid solutions that satisfy multiple simultaneous requirements

A salesperson needs to visit 20 cities and return home, minimizing total distance. The state space contains 20! ≈ 2.4 × 10^18 possible routes — far more than any systematic search can handle. Local search techniques can find an excellent solution in seconds. Meanwhile, a university registrar must schedule hundreds of courses into rooms and time slots without conflicts. Constraint satisfaction algorithms can exploit that structure to find a valid schedule in milliseconds.

Part 1: Local Search and Optimization

Instead of systematically exploring all possibilities, local search algorithms start somewhere and move to neighboring states. Three major techniques stand out:

Algorithm	Strategy	Strength	Weakness
Hill Climbing	Always move to best neighbor	Fast, simple, O(1) memory	Gets stuck on local maxima
Simulated Annealing	Sometimes accept worse neighbors (probability decreasing with temperature)	Escapes local maxima	Slower, requires tuning
Genetic Algorithms	Evolve a population of solutions	Handles complex spaces	Many parameters

Algorithm

Strategy

Strength

Weakness

Hill Climbing

Always move to best neighbor

Fast, simple, O(1) memory

Gets stuck on local maxima

Simulated Annealing

Sometimes accept worse neighbors (probability decreasing with temperature)

Escapes local maxima

Slower, requires tuning

Genetic Algorithms

Evolve a population of solutions

Handles complex spaces

Many parameters

Local search trades completeness (a guarantee of finding a solution) for efficiency (finding good solutions fast). This is the right trade-off for large-scale optimization where "good enough" beats "perfect but computationally impossible."

Part 2: Constraint Satisfaction Problems

Some problems have a special structure: a set of variables that must receive values from specified domains, subject to constraints that restrict which combinations are valid. Exploiting this structure allows algorithms to prune enormous portions of the search space before trying anything.

A Sudoku puzzle is the classic example. Fill an 81-cell grid so that every row, column, and 3×3 box contains the digits 1 through 9 exactly once. Formulated as a CSP — 81 variables, domain {1–9} for each empty cell, all-different constraints — backtracking with arc consistency can solve hard Sudoku puzzles in under a second.

Three powerful CSP techniques build on one another:

Backtracking Search — systematically try assignments, undo when constraints are violated
Constraint Propagation (AC-3) — use constraints to shrink variable domains before and during search
Intelligent Ordering Heuristics — choose which variable to assign next (MRV, degree) and which value to try first (LCV)

Learning Objectives

By the end of this unit, you will be able to:

Apply local search methods (hill climbing, simulated annealing) to optimization problems
Formulate constraint satisfaction problems with variables, domains, and constraints
Implement backtracking search with constraint propagation using arc consistency (AC-3)
Use intelligent heuristics (MRV, degree, LCV) to dramatically speed up CSP solving
Recognize when to use optimization techniques versus CSP approaches for different problem types

Reading Assignments

Primary Reading:

Berkeley CS 188: Local Search — Hill climbing, simulated annealing, and beam search
Berkeley CS 188: Constraint Satisfaction Problems — Variables, domains, constraints, backtracking, and heuristics

Weekly Schedule

Section	Topic	Points
4.1	Local Search and Optimization	—
4.2	Simulated Annealing	—
4.3	Constraint Satisfaction Problems	—
4.4	Backtracking Search	—
4.5	Smart Heuristics for CSPs	—
4.6	Choosing the Right Tool	—
Lab SA	Simulated Annealing Lab	50
Lab CSP	Sudoku CSP Solver Lab	125
4.W	Wrap-Up and Self-Assessment	Midterm Quiz (cumulative)

Get a preview of the week’s two main themes — optimization landscapes and constraint graphs.

Introduction to Optimization Problems

Begin: 4.1 Local Search and Optimization →

This work is licensed under CC BY-SA 4.0.