Multilevel Local Search

Compress the problem, solve the small version, expand back, refine — like working with a zoomed-out then zoomed-in view.

Intuition

The big idea

For a 100-variable problem, a local-search swap touches only 1 variable at a time — that's tiny. If you instead group variables into clusters of 2 and toggle entire clusters, each "move" affects 2 variables. Group again into clusters of 4 — each move affects 4. This lets the search make large, coordinated moves at coarse levels (good for escaping local optima), then refine with small moves at the fine level.

The three phases

Coarsening — Merge variables into clusters. Cluster of clusters at the next level. Repeat until the problem is small.
Coarse optimization — Apply local search at the coarsest level (each "move" toggles an entire cluster).
Uncoarsening + refinement — Project the solution back to the next finer level. Run local search again. Repeat until you reach the original (level 0).

Worked example (graph coloring with 100 variables)

Two colors: Black (B) or Green (G). Constraint: neighboring variables must have different colors.

Level 0 — original problem

100 indices, 100 individual variables.

Reduction → Level 1 (50 clusters of 2)

Cluster #1 = (var 1, var 4)
Cluster #2 = (var 2, var 17)
…
Cluster #50 = (var 6, var 36)

Now the "solution" assigns one color to each cluster (both variables in the cluster get that color). 50 decisions instead of 100.

Reduction → Level 2 (25 clusters of 4)

Cluster #1 = ((1,4) ∪ (5,27))    → 4 vars
Cluster #2 = ((2,17) ∪ (4,15))   → 4 vars
…
Cluster #25 = ((45,13) ∪ (21,3))

Optimize at level 2

Random initial coloring at the cluster level. Apply local search:

while (not stop):
    pick random cluster i
    flip its color
    if (solution improves) accept else revert

Get something like: R B B G R G … B for 25 clusters. Each cluster's color applies to all 4 of its variables.

Uncoarsen to level 1, refine

Now we have 50 clusters with colors inherited from level 2. Run local search at this level — flipping a 2-variable cluster's color.

Uncoarsen to level 0, refine

Each variable gets its color. Run local search per individual variable.

Pseudocode

MULTILEVEL_LS(initial_problem, num_levels):
    P[0] = initial_problem
    for L = 1 .. num_levels:
        P[L] = coarsen(P[L-1])     // merge pairs of clusters

    solution[num_levels] = random
    for L = num_levels down to 0:
        solution[L] = local_search(P[L], solution[L])
        if L > 0:
            solution[L-1] = project(solution[L])    // inherit colors

    return solution[0]

Why this works:

At coarse levels, the search space is small → easy to find a good arrangement quickly.
Big coordinated moves (flipping a 16-variable cluster at level 4) can escape local optima that single-variable moves can't.
Fine levels just polish — most of the heavy lifting is done.

Exam tips

Frequently asked

"Describe coarsening" — random pairing of variables/clusters at each level.
"Why multilevel over plain local search?" — large coordinated moves at coarse levels escape local optima.
"What happens at the finest level?" — local search with single-variable moves (same as ordinary).
"Apply multilevel to CSP" — same recipe; the local search inside flips a cluster's color (or value) and re-counts violated constraints.