Backtracking, Branch-and-Bound and Constraint Search

Introduction

Many computational problems are easy to state but difficult to solve efficiently because their solution spaces grow exponentially. Scheduling, routing, resource allocation, configuration, theorem proving and combinatorial optimization commonly have this property. Exhaustively examining every candidate is usually impractical. Backtracking, branch-and-bound, and constraint search address this difficulty by exploring a structured search space while eliminating candidates that cannot lead to useful or feasible solutions.

These methods are not identical. Backtracking is primarily a feasibility and enumeration technique: it abandons a partial solution as soon as a constraint is violated. Branch-and-bound is primarily an optimization technique: it abandons a subproblem when a bound proves that it cannot improve the best known solution. Constraint search provides a broader modeling framework in which variables, domains and constraints are combined with propagation, ordering heuristics and systematic search.

Their worst-case running times are often exponential. Their practical value comes from reducing the explored portion of the search tree, producing solutions early, exploiting problem structure and using mathematically valid bounds.

Learning Objectives

After completing this chapter, the reader should be able to:

1. Model combinatorial problems as search trees and constraint satisfaction problems.
2. Design and analyze recursive backtracking algorithms.
3. Distinguish feasibility pruning from bound-based pruning.
4. Construct valid upper and lower bounds for branch-and-bound.
5. Explain constraint propagation, consistency and variable/value ordering.
6. Apply these methods to problems such as N-Queens, 0/1 knapsack and scheduling.
7. Evaluate correctness, complexity, memory use and practical performance.
8. Recognize limitations, implementation risks and responsible uses in AI systems.

1. Search Spaces and Partial Solutions

A search problem can be represented by a rooted tree. The root represents an empty decision sequence. Each edge adds a decision, and each node represents a partial solution. A leaf is either a complete solution or a terminal failure.

If decision level i has bᵢ possible choices, the number of complete decision sequences is, in the general nonuniform case,

where n is the number of decision levels. If every level has at most b choices, then N ≤ bⁿ. This exponential growth explains why pruning is central.

A pruning rule is safe only if it cannot remove a partial solution that could lead to an acceptable or optimal answer. This distinction is fundamental: an aggressive but invalid rule may make an algorithm fast while destroying correctness.

2. Backtracking

2.1 Principle

Backtracking constructs a solution incrementally. At each stage it selects a candidate decision, checks whether the partial assignment remains promising, and recursively continues. If no continuation is possible, the algorithm undoes the last decision and tries another choice.

A generic template is:

SEARCH(partial)
    if partial is complete:
        record or return partial
    else:
        for choice in ordered_choices(partial):
            if feasible(partial, choice):
                apply(choice)
                SEARCH(partial)
                undo(choice)

The procedure is correct for enumeration when every legal choice is considered and feasible rejects only assignments that cannot be extended to a valid solution. For optimization, the procedure must additionally compare objective values or use a valid bound.

2.2 N-Queens Example

In the N-Queens problem, n queens must be placed on an n × n board so that no two share a row, column or diagonal. A convenient representation places exactly one queen in each row. A partial solution is an array q[1..k], where q[i] is the column selected for row i.

A candidate column c for row k + 1 is safe when it is not already occupied and does not share a diagonal with any earlier queen:

The diagonal condition follows because two squares lie on a common diagonal exactly when their row and column differences have equal absolute value.

PLACE(row)
    if row > n:
        output one solution
    else:
        for col = 1 to n:
            if col is unused and both diagonals are unused:
                mark col and both diagonals
                PLACE(row + 1)
                unmark col and both diagonals

With Boolean arrays for columns and diagonals, testing and undoing a choice take O(1) time. The worst-case search remains exponential; a loose bound is O(n!), because row-by-row placement considers permutations of columns. The actual tree is much smaller because diagonal conflicts prune many nodes. The recursion stack and marker arrays require O(n) auxiliary space, excluding stored solutions.

2.3 Enumeration, Decision and Optimization

Backtracking may solve three related tasks:

The same search tree can support all three, but termination and pruning conditions differ.

3. Branch-and-Bound

3.1 Principle

Branch-and-bound explores alternatives by branching and uses an optimistic bound to eliminate subproblems. It maintains an incumbent, the best complete solution found so far. A maximization node with upper bound U can be discarded when

where V* is the incumbent objective value. For minimization, a node with lower bound L is discarded when

The bound must be optimistic: for maximization it must satisfy U ≥ the best value achievable in that subtree; for minimization it must satisfy L ≤ the best achievable value. A non-optimistic bound can incorrectly prune the optimum.

3.2 Search Strategies

Depth-first branch-and-bound uses little memory and often finds a good incumbent quickly. Best-bound search stores live nodes in a priority queue and expands the node with the most promising bound. Breadth-first search expands by depth but may require substantial memory. The choice affects time, memory and the speed at which a strong incumbent is obtained.

A useful performance principle is that pruning improves when both the bound is tight and the incumbent is strong. Thus, a heuristic solution obtained before systematic search can substantially reduce work without affecting correctness.

3.3 0/1 Knapsack Worked Example

Consider items with weights and profits:

The capacity is 16. Each item is either selected or rejected. The objective is to maximize total profit subject to total weight not exceeding 16.

For a partial node, an upper bound can be computed by allowing fractional completion after the selected items. If the remaining capacity is C and the next items are considered in nonincreasing profit/weight order, the fractional bound is

Here P is the profit already selected. This is an upper bound because the fractional problem relaxes the 0/1 restriction; allowing fractions cannot produce a value smaller than the integral optimum in that subtree.

Suppose items are considered in the order 1, 2, 3, 4. Selecting items 1 and 3 gives weight 12 and profit 90. The remaining capacity is 4. The resulting incumbent can be improved by selecting item 2 instead of item 3: items 1 and 2 have weight 7 and profit 70, and item 4 can also be added, giving weight 12 and profit 80. The best feasible combination is items 1 and 3 with profit 90, or items 1, 2 and 4 with profit 80; in fact, items 2 and 3 have weight 15 and profit 80. No combination involving item 3 and item 4 with item 1 fits better than profit 90. Thus the optimum is profit 90, achieved by items 1 and 3.

A branch whose fractional upper bound is at most 90 can be discarded. Notice that the bound is not itself a feasible solution; it is only evidence about what the branch might achieve.

3.4 Complexity

If n binary decisions are made, the worst-case number of nodes is O(2ⁿ). A strong bound may reduce practical work dramatically, but worst-case exponential behavior generally remains. Space is O(n) for depth-first search, while best-bound search may require O(number of live nodes).

4. Constraint Satisfaction and Constraint Search

A constraint satisfaction problem (CSP) is commonly defined by a triple (X, D, C):

• X = {X₁, …, Xₙ} is a set of variables.
• D assigns a domain Dᵢ of possible values to each variable Xᵢ.
• C is a set of constraints restricting permitted combinations of values.

A solution assigns a value to every variable while satisfying every constraint. Examples include graph coloring, timetabling, Sudoku, resource allocation and configuration.

4.1 Constraint Graphs

A binary CSP can be represented by a graph whose vertices are variables and whose edges indicate constraints between pairs of variables. Sparse graphs often permit more effective local reasoning than dense graphs. The graph also supports decomposition: if it separates into independent components, those components can sometimes be solved independently.

4.2 Propagation and Consistency

Forward checking removes from the domains of unassigned variables values that conflict with a newly assigned value. If any domain becomes empty, the branch fails immediately.

Arc consistency is stronger. For a binary constraint between Xᵢ and Xⱼ, every value a ∈ Dᵢ must have a supporting value b ∈ Dⱼ such that (a,b) satisfies the constraint. If no support exists, a is removed. Algorithms such as AC-3 repeatedly revise arcs until no domain changes or a domain becomes empty.

For a CSP with e directed arcs and maximum domain size d, the commonly stated worst-case bound for AC-3 is O(e d³), under the standard revise implementation. The bound reflects up to O(ed) arc reinsertions and O(d²) support checking per revision; actual performance depends on implementation and constraint structure.

Consistency is not complete search. A constraint network may be arc-consistent yet have no global solution, so search may still be necessary.

4.3 Heuristics

The minimum-remaining-values (MRV) heuristic chooses the unassigned variable with the smallest current domain. It often detects failure early. The degree heuristic breaks ties by choosing the variable constraining the largest number of unassigned variables. The least-constraining-value heuristic tries first the value that removes the fewest values from neighboring domains.

These heuristics change the order of exploration, not the set of mathematically valid solutions. Their benefit is instance-dependent and should be evaluated experimentally.

5. A Unified View

Backtracking, branch-and-bound and CSP search can be integrated. A node may contain a partial assignment, reduced domains, an objective value and a bound. The general process is:

1. Select a variable or decision.
2. Order candidate values or branches.
3. Apply the decision.
4. Propagate constraints.
5. Compute a bound if optimization is required.
6. Recurse only if the node remains feasible and potentially useful.
7. Restore state on return.

This design separates correctness mechanisms from performance mechanisms. Constraint checks and valid bounds protect correctness; ordering heuristics, caching and data structures improve performance.

6. Implementation Engineering

State restoration is a frequent source of errors. A solver must undo every domain deletion, marker update and objective change made by a branch. Two standard approaches are copying state at each node or recording reversible changes on a trail stack. Copying is simpler but may cost O(n) or more per node; trailing is usually faster and more memory-efficient but more complex.

Useful engineering practices include:

• Represent constraints with bitsets, adjacency lists or specialized propagators.
• Maintain incremental objective values rather than recomputing them.
• Obtain an incumbent using a fast heuristic before branch-and-bound search.
• Use deterministic tie-breaking when reproducibility matters.
• Instrument node counts, pruning counts, maximum depth and time per propagator.
• Test against small instances whose solutions can be verified by exhaustive enumeration.
• Distinguish timeout or resource exhaustion from proof of infeasibility.

Memoization can help when different paths reach equivalent states. It is effective only when the state representation captures all information relevant to future decisions. Symmetry breaking, such as fixing one representative among equivalent solutions, can also reduce duplicated work, but it must preserve at least one representative of every equivalence class.

7. Applied Case: University Examination Timetabling

The following is an illustrative case. A university must schedule examinations into timeslots and rooms. Each examination is a variable; its domain contains permitted timeslot-room pairs. Constraints include student conflicts, room capacity, room availability and restrictions on consecutive examinations. The objective may minimize student inconvenience and the number of used rooms.

Analysis. A CSP model handles hard constraints. A conflict graph connects examinations sharing students. High-degree examinations are assigned early using the degree heuristic, while MRV identifies examinations with few legal slots. Forward checking removes slots that conflict with already scheduled examinations.

Optimization. A branch-and-bound layer maintains the best timetable found. A lower bound on inconvenience can be obtained by summing unavoidable conflicts or minimum possible travel penalties for unassigned examinations. A node is pruned when its lower bound is no better than the incumbent.

Approach. A practical solver may first construct a feasible timetable greedily, improve it with local search, and then use constraint search for difficult residual decisions. Symmetry can be reduced by fixing an ordering of interchangeable rooms. The system should report whether the result is optimal, feasible but not proven optimal, or incomplete because a time limit was reached.

Outcome and learning points. Search quality depends not only on the algorithm but also on model quality, bounds, data structures and instance characteristics. A weak lower bound may explore too many nodes; an invalid bound may eliminate a better timetable. Human review remains important because a mathematically feasible schedule may impose unacceptable burdens on particular student groups.

8. Limitations, Ethics and Contemporary Developments

These methods can be computationally expensive, sensitive to heuristic choices and difficult to explain when thousands of pruning decisions interact. A solver may also encode institutional or social biases through its constraints and objective function. In scheduling or allocation, optimizing a numerical objective does not guarantee fairness. Constraints should therefore be audited, protected groups considered, and trade-offs documented.

In AI, constraint search is used in neuro-symbolic systems, planning, structured prediction, verification and hybrid optimization. Learned heuristics can predict promising variables, values or branching nodes, but they should guide search rather than replace correctness-preserving pruning unless formal guarantees are retained. Modern solvers increasingly combine propagation, conflict-directed learning, SAT/SMT techniques, integer programming relaxations and parallel search. Parallel implementations must coordinate incumbents and avoid unsafe assumptions about shared state.

Best-Practice Checklist

1. State the decision variables, domains, constraints and objective explicitly.
2. Prove that every pruning rule is safe.
3. Use a relaxation-based bound when possible.
4. Find a good feasible incumbent early for maximization or minimization.
5. Apply propagation before branching when its cost is justified.
6. Select variables with principled heuristics such as MRV and degree.
7. Record enough diagnostics to explain performance and termination status.
8. Validate results independently on small and adversarial instances.
9. Separate hard constraints from preferences and fairness requirements.
10. Report optimality gaps or incomplete-search status honestly.

Chapter Summary

Backtracking systematically constructs partial solutions and retreats when constraints make extension impossible. Branch-and-bound extends this idea to optimization by combining branching with optimistic upper or lower bounds and an incumbent solution. Constraint search provides a formal model based on variables, domains and constraints, enhanced by propagation and ordering heuristics. N-Queens illustrates feasibility pruning; 0/1 knapsack illustrates relaxation-based bounds; timetabling illustrates their integration in a realistic application. Although worst-case complexity is usually exponential, careful modeling, propagation, bounds, heuristics, symmetry handling and state management can make large practical instances tractable. Correctness, transparency and fairness are essential when these methods are used in AI and institutional decision systems.

Key Terms

Backtracking: Systematic search that abandons a partial assignment when it cannot lead to a valid completion.

Branch-and-bound: Optimization search using branching and objective bounds to prune subproblems.

Constraint satisfaction problem: A problem defined by variables, domains and constraints.

Partial assignment: Values assigned to only some variables.

Feasibility pruning: Eliminating a branch that violates a constraint or has no valid extension.

Incumbent: Best complete solution found so far.

Optimistic bound: A bound that does not underestimate the best possible value in maximization, or does not overestimate it in minimization.

Constraint propagation: Deduction that removes values inconsistent with current assignments.

Forward checking: Removing incompatible future values immediately after an assignment.

Arc consistency: A condition in which every domain value has support in the domain of a neighboring variable.

MRV heuristic: Choosing the unassigned variable with the smallest remaining domain.

Degree heuristic: Choosing the variable involved in the largest number of relevant constraints.

Least-constraining value: A value that eliminates the fewest neighboring possibilities.

Constraint graph: Graph showing variables and relationships among them.

Relaxation: A problem obtained by weakening restrictions, often to derive a bound.

Symmetry breaking: Adding safe restrictions to avoid equivalent branches.

Memoization: Storing results for previously encountered equivalent states.

Optimality gap: Difference between an incumbent objective and a valid bound on the optimum.

Review Questions

Short Answer Questions

1. What is the difference between feasibility pruning and bound-based pruning?
2. Why must an upper bound for a maximization problem be optimistic?
3. Define a constraint satisfaction problem using its three components.
4. What does the MRV heuristic select?
5. Why is state restoration necessary in recursive search?

Long Answer Questions

1. Explain the design and correctness conditions of a generic backtracking algorithm.
2. Compare depth-first, breadth-first and best-bound branch-and-bound search.
3. Explain forward checking and arc consistency, including why consistency does not always prove global satisfiability.
4. Derive and discuss the fractional upper bound used for 0/1 knapsack.
5. Discuss how modeling, heuristics, propagation and symmetry breaking affect practical solver performance.

Analytical / Application Questions

1. Design a CSP model for assigning research presentations to rooms and timeslots, including variables, domains, hard constraints and one soft objective.
2. For a maximization problem, explain how an incumbent value of 120 and a node upper bound of 115 affect branch-and-bound search. What changes if the bound is 135?
3. Propose a combined backtracking and branch-and-bound strategy for examination timetabling and identify two fairness risks that should be audited.

Multiple Choice Questions with Answers

Question 1

Which condition safely prunes a node in a maximization branch-and-bound search?

A. Its upper bound is less than or equal to the incumbent value.

B. Its lower bound is less than the incumbent value.

C. Its depth is greater than the average depth.

D. Its first branch is infeasible.

Correct Answer: A. Its upper bound is less than or equal to the incumbent value.

Question 2

In the N-Queens problem, what does |q[i] − c| = |i − (k + 1)| indicate?

A. The queens share a column.

B. The queens share a diagonal.

C. The row is already empty.

D. The board has insufficient capacity.

Correct Answer: B. The queens share a diagonal.

Question 3

What is the primary purpose of forward checking in a CSP?

A. To enumerate every possible complete assignment.

B. To remove future values inconsistent with a new assignment.

C. To calculate an objective lower bound.

D. To sort all constraints alphabetically.

Correct Answer: B. To remove future values inconsistent with a new assignment.

Question 4

For a maximization problem, a valid optimistic upper bound must be:

A. No greater than every feasible value.

B. At least as large as the best value attainable in the subtree.

C. Equal to the incumbent in every node.

D. Computed only after a complete solution is found.

Correct Answer: B. At least as large as the best value attainable in the subtree.

Question 5

Which heuristic chooses the unassigned variable with the smallest current domain?

A. Degree heuristic

B. Least-constraining value

C. Minimum remaining values

D. Best-bound selection

Correct Answer: C. Minimum remaining values

Question 6

In the illustrative knapsack instance, selecting items 1 and 3 produces what total weight and profit?

A. Weight 7 and profit 70

B. Weight 12 and profit 90

C. Weight 15 and profit 80

D. Weight 16 and profit 100

Correct Answer: B. Weight 12 and profit 90

Question 7

Why can fractional knapsack reasoning provide an upper bound for 0/1 knapsack?

A. The fractional problem is more restricted than the 0/1 problem.

B. The fractional relaxation allows more choices, so its optimum cannot be smaller.

C. Fractions always produce an integral solution.

D. It ignores item profits.

Correct Answer: B. The fractional relaxation allows more choices, so its optimum cannot be smaller.

Question 8

What is the usual worst-case time bound stated for AC-3 with e directed arcs and maximum domain size d?

A. O(e + d)

B. O(e d)

C. O(e d²)

D. O(e d³)

Correct Answer: D. O(e d³)

Question 9

What is an incumbent in branch-and-bound?

A. The first infeasible partial assignment

B. The best complete solution found so far

C. The largest domain in the CSP

D. A constraint graph edge

Correct Answer: B. The best complete solution found so far

Question 10

Which statement about arc consistency is correct?

A. It always proves that a CSP has a global solution.

B. It removes unsupported domain values but may still require search.

C. It applies only to optimization problems.

D. It never changes domains.

Correct Answer: B. It removes unsupported domain values but may still require search.