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.
  1. Initially: X = {1,2}, Y = {1,2}.

  2. Solver chooses X to branch on.

    • Branch 1: X = 1.
    • Branch 2: X = 2.
  3. Inside Branch 1:

    • Constraint X β‰  Y prunes Y. Now Y = {2}.
    • Both variables are assigned β†’ solution found: (X=1, Y=2).
  4. 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).

  1. Start: all variables have 3 colors.

  2. Choose a variable to branch on: say B.

    • Branch 1: B = Red.
    • Branch 2: B = Green.
    • Branch 3: B = Blue.
  3. 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.
  4. 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.