π 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
.
- Branch 1:
-
Inside Branch 1:
- Constraint
X β Y
prunesY
. NowY = {2}
. - Both variables are assigned β solution found:
(X=1, Y=2)
.
- Constraint
-
Inside Branch 2:
- Constraint prunes
Y
. NowY = {1}
. - Solution found:
(X=2, Y=1)
.
- Constraint prunes
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
.
- Branch 1:
-
Inside Branch 1 (
B=Red
):- Constraint prunes Red from
A
andC
. - Now:
A = {Green, Blue}
,C = {Green, Blue}
. - Continue branching on
A
orC
.
- Constraint prunes Red from
-
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.