Branching in Solution Search

🎓 Branching in Solution Search

So far, we have seen how solvers use constraint propagation to reduce domains and simplify problems. But propagation alone rarely solves a full CSP. At some point, the solver must choose: which variable to assign next, and which value to try.

This process is called branching. It is the backbone of systematic search in constraint solvers.

🌳 What Is Branching?

Branching is the act of splitting the problem into subproblems, each representing a possible decision.

Each branch corresponds to giving a variable a specific value (or ruling out a value).
The solver then applies constraint propagation inside that branch.
If a contradiction appears, that branch is abandoned.
Otherwise, the solver continues branching recursively.

In this way, the solver explores a search tree of possibilities until it finds a complete solution.

🔎 A Tiny Example: Two Variables

Variables:

X ∈ {1,2}
Y ∈ {1,2} Constraint: X ≠ Y.

Initially: X = {1,2}, Y = {1,2}.
Solver chooses X to branch on.
- Branch 1: X = 1.
- Branch 2: X = 2.
Inside Branch 1:
- Constraint X ≠ Y prunes Y. Now Y = {2}.
- Both variables are assigned → solution found: (X=1, Y=2).
Inside Branch 2:
- Constraint prunes Y. Now Y = {1}.
- Solution found: (X=2, Y=1).

The search tree had two branches, each yielding a valid solution.

🧩 Branching Strategy

How the solver chooses where to branch makes a big difference in efficiency. There are two key decisions:

1. Variable Selection – Arrays (Which variable to branch on?)

Common strategies:

First unassigned variable: simplest approach.
Smallest domain first (a.k.a. “fail-first”): choose the variable with the fewest remaining values, to force contradictions early.
Most constrained variable: choose the variable that participates in the most constraints.
Domain/degree ratio: balance between domain size and number of constraints.

2. Value Selection (Which value to try first?)

Common strategies:

Ascending order: try values in numerical or lexical order.
Best-first heuristic: try values that seem promising (e.g., smallest cost, highest likelihood).
Randomized choice: explore diversity of paths in stochastic solvers.

Together, these heuristics shape the search tree and strongly affect performance.

🎨 Example: Map Coloring with Branching

Variables: A, B, C, each with domain {Red, Green, Blue}. Constraints: neighbors must have different colors (A ≠ B, B ≠ C).

Start: all variables have 3 colors.
Choose a variable to branch on: say B.
- Branch 1: B = Red.
- Branch 2: B = Green.
- Branch 3: B = Blue.
Inside Branch 1 (B=Red):
- Constraint prunes Red from A and C.
- Now: A = {Green, Blue}, C = {Green, Blue}.
- Continue branching on A or C.
Solver continues until complete assignments are found.

Note: branching decisions create a tree, and propagation shrinks domains inside each branch.

🧠 Branching vs. Propagation

Propagation = logical deduction, passive narrowing of possibilities.
Branching = active decision, speculative trial of one path at a time.

Both are essential:

Without propagation, branching would explode in size.
Without branching, propagation would stall before solving.

⚡ Advanced Branching

Modern solvers use sophisticated branching techniques:

Dynamic heuristics: variable/value selection adapts as the search evolves.
Restart strategies: periodically restart the search with different branching to escape “bad luck.”
Nogood recording: learn from failed branches to avoid repeating mistakes.
Symmetry breaking: avoid exploring branches that are equivalent by symmetry.

These enhancements allow solvers to handle problems with millions of potential assignments.

📌 Takeaway

Branching is the solver’s way of exploring choices systematically.
Each branch corresponds to a partial decision, leading to subproblems.
The order in which variables and values are chosen has a huge impact on performance.
Branching and propagation work together: one explores, the other prunes.