8. Backtracking, Branch-and-Bound and Constraint Search

Introduction and Context

Many algorithmic problems are easy to state but difficult to solve because the number of possible solutions grows exponentially with input size. Scheduling jobs, assigning frequencies, routing vehicles, placing queens on a chessboard, selecting projects under constraints, and constructing interpretable machine-learning models are examples in which choices interact with one another. A direct enumeration of all possibilities may be correct, but it is usually computationally impractical.

State-space search provides a systematic way to explore such possibilities. Instead of generating complete solutions without structure, the algorithm represents partial decisions as nodes in a search tree. It then uses problem knowledge to avoid exploring branches that cannot lead to useful solutions. Backtracking eliminates partial assignments that violate constraints. Branch-and-bound eliminates branches that cannot improve the best solution already found. Constraint search combines systematic exploration with propagation, variable-ordering heuristics, and domain reduction.

These methods do not generally remove worst-case exponential behaviour. Their value lies in reducing the effective search space and making difficult instances solvable in practice. For postgraduate work in artificial intelligence and machine learning, this distinction is important: pruning is not a proof that a problem has become polynomial; it is a principled way of exploiting structure, bounds, and domain knowledge.

Learning Objectives

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

1. Explain state-space trees, partial solutions, feasibility, pruning, bounds, and incumbents.

2. Design recursive backtracking algorithms for constraint satisfaction problems.

3. Distinguish backtracking from branch-and-bound and constraint-propagation methods.

4. Construct admissible upper and lower bounds for combinatorial optimization.

5. Select variable-ordering, value-ordering, and node-selection heuristics.

6. Analyse time, space, and worst-case exponential behaviour.

7. Apply these methods to practical optimization and AI-related problems.

8. Evaluate limitations, implementation risks, and ethical implications of automated search.

The State-Space View of Difficult Problems

A state-space tree represents a sequence of decisions. The root denotes an empty decision, an internal node denotes a partial solution, and a leaf denotes either a complete solution or a state from which no further decision is possible. If a problem has variables X1, X2, ..., Xn, assigning a value to one variable creates children corresponding to alternative values.

For example, in the n-queens problem, a node at depth k represents a placement of queens in the first k rows. Its children place a queen in row k+1 in each column not attacked by an earlier queen. A branch is feasible only if no two placed queens share a column or diagonal.

Three classifications are useful:

• A feasible state satisfies all constraints imposed so far.
• A complete state assigns every required decision.
• A promising state may still lead to a feasible or improving complete solution.

Search is effective when the algorithm can identify non-promising states cheaply. This gives the general pattern:

1. Select an unassigned decision.

2. Generate candidate values or actions.

3. Test feasibility or compute a bound.

4. Recurse on promising children.

5. Undo the decision when returning from recursion.

The undo operation is the source of the name backtracking. It restores the data structures to the state they had before the recursive call.

Backtracking: Feasibility-Driven Search

Backtracking is most natural for problems in which the primary question is whether a feasible assignment exists, or in which every feasible assignment must be enumerated. Its pruning rule is a feasibility test: if a partial assignment already violates a constraint, none of its descendants can repair that violation.

A generic form is:

```text

SEARCH(partial):

if partial is complete:

process partial

return

choose an unassigned variable

for value in ordered domain(variable):

if value is consistent with partial:

assign value

SEARCH(partial)

undo value

```

The procedure is correct when every legal complete assignment can be generated and every rejected partial assignment has no legal completion. The choice of variable and the order of values affect performance but not correctness, provided the search remains complete.

Example: Graph Colouring

Given a graph G=(V,E) and at most m colours, the task is to assign a colour to each vertex so that adjacent vertices receive different colours. A backtracking algorithm assigns colours to vertices one at a time. Before assigning colour c to vertex v, it checks whether any already-coloured neighbour has c. If so, the choice is rejected.

If vertices are assigned in a poor order, the algorithm may explore a large tree before discovering that the final vertices cannot be coloured. A more effective order chooses a vertex with many constraints or a small remaining domain. This idea leads to constraint-search heuristics discussed later.

Example: Subset Sum

Given positive integers a1,...,an and target T, subset sum asks whether a subset totals T. At position i, the algorithm branches on including or excluding ai. If the current sum exceeds T, the branch can be pruned. If the current sum plus all remaining numbers is less than T, the branch can also be pruned. These tests illustrate that backtracking can use simple feasibility bounds in addition to direct constraint checking.

Branch-and-Bound: Objective-Driven Search

Branch-and-bound solves optimization problems. Each node represents a partial solution, and a bounding function estimates the best objective value that any descendant could achieve. The algorithm maintains an incumbent: the value of the best complete solution found so far.

For a maximization problem, let U(v) be an upper bound on the value achievable below node v. If U(v) is no greater than the incumbent value, node v can be discarded. For a minimization problem, let L(v) be a lower bound. If L(v) is no smaller than the incumbent cost, the node cannot improve the incumbent.

The essential correctness condition is admissibility:

• A maximization upper bound must never underestimate the possible descendant value.
• A minimization lower bound must never overestimate the possible descendant quality.

A weak bound remains correct but prunes little. A strong bound prunes more but may require greater computation. The design problem is therefore not simply to obtain the tightest bound, but to balance bound quality against the cost of calculating it.

Search Strategies

Depth-first branch-and-bound uses little memory and often finds a good incumbent early. A good incumbent increases pruning. Best-first branch-and-bound stores frontier nodes in a priority queue, usually ordered by their bound. It may discover an optimal solution efficiently, but memory can become exponential. Breadth-first search is less common for optimization because it may retain many nodes with weak prospects.

A practical algorithm often uses a hybrid strategy: depth-first exploration to obtain an incumbent, followed by priority-based exploration of promising nodes.

The Travelling Salesperson Problem

In the travelling salesperson problem (TSP), a tour must visit every city exactly once and return to the starting city while minimizing total distance. A partial tour has a current path and a set of unvisited cities. Branching selects the next city.

A simple lower bound can be constructed from the current path cost plus a minimum outgoing-edge estimate for each unvisited city, adjusted to avoid double counting. Another approach reduces a cost matrix by subtracting the minimum value in each row and column. The reduction cost provides a lower bound, while setting selected row and column entries to infinity prevents illegal revisits.

When a partial tour's lower bound is at least the cost of the best complete tour, that partial tour is pruned. The algorithm remains exact because the bound is optimistic for minimization: it may be lower than the true completion cost, but never higher.

Constraint Satisfaction and Constraint Search

A constraint satisfaction problem (CSP) is defined by variables, domains, and constraints. A CSP consists of variables X={X1,...,Xn}, a domain Di for each variable Xi, and constraints specifying permitted combinations of values. The objective may be to find one satisfying assignment, enumerate all assignments, or optimize a function subject to the constraints.

Backtracking alone checks constraints after each assignment. Constraint search goes further by reducing future domains before branching. This process is called propagation.

Constraint Propagation

Forward checking removes from the domain of every unassigned variable values that conflict with the latest assignment. If any domain becomes empty, the current branch is immediately rejected.

Arc consistency is stronger. For a binary constraint between Xi and Xj, every remaining value in Di must have at least one compatible supporting value in Dj. If not, that value is removed. Removing values can cause further removals in neighbouring domains. The AC-3 algorithm repeatedly processes arcs until no domain changes or a domain becomes empty.

Propagation can substantially reduce search, but it has a cost. Stronger consistency is not automatically better if it is repeatedly applied to large or dense constraint networks. The appropriate level depends on the structure of the problem.

Variable and Value Ordering

The minimum-remaining-values (MRV) heuristic selects the unassigned variable with the smallest current domain. It detects failure early, because a variable with few choices is likely to become impossible soon. The degree heuristic breaks ties by selecting the variable involved in the largest number of constraints on unassigned variables.

The least-constraining-value heuristic tries first the value that eliminates the fewest options from other variables. This can preserve flexibility and is useful when the aim is to find a solution quickly. In contrast, a value that exposes contradiction early may be preferable when proving unsatisfiability. Thus heuristic selection should reflect the search objective.

Global Constraints

A global constraint expresses a structured relationship among several variables. The all-different constraint, for example, requires all variables to receive distinct values. A specialised propagator for all-different can be much stronger than repeatedly applying pairwise inequality constraints. Scheduling systems may use global constraints for cumulative resource capacity, precedence, and no-overlap requirements.

Modern constraint programming systems combine propagation, search heuristics, conflict learning, and specialized solvers. They are particularly effective when domain constraints are more informative than the objective function.

Backtracking and Branch-and-Bound Compared

Backtracking prunes because a partial assignment is infeasible. Branch-and-bound prunes because a feasible continuation cannot improve the incumbent. The two methods can be combined. For example, an optimization CSP may reject a node when propagation detects a contradiction and also reject it when its objective bound is insufficient.

Backtracking usually has a straightforward depth-first implementation and modest memory requirements. Branch-and-bound requires an objective, an incumbent, and a valid bound. Constraint search adds domain representation and propagation mechanisms. In practice, a powerful solver may use all three: branching generates alternatives, propagation removes infeasible values, and bounding eliminates noncompetitive feasible regions.

Designing Effective Bounds and Heuristics

A bound should be easy to compute, valid for every node, and sufficiently tight to support pruning. Common constructions include relaxation, aggregation, decomposition, and problem-specific estimates.

A relaxation removes some restrictions from the original problem. Its optimum is optimistic for a minimization problem and therefore supplies a lower bound. For example, allowing fractional rather than integral decisions can produce a linear-programming bound. The relaxed problem must be easier to solve than the original; otherwise the bound may cost more than the search it saves.

An incumbent is equally important. A bound only prunes against the incumbent, so obtaining a good complete solution early can reduce the tree dramatically. Greedy construction, local improvement, randomized restarts, or a domain-specific heuristic may be used to obtain an initial solution. Such a heuristic need not be optimal; it only needs to provide a valid feasible solution.

Symmetry is another source of unnecessary search. If exchanging two equivalent resources produces an equivalent solution, a symmetry-breaking constraint can require a canonical ordering. Care is essential: an incorrectly imposed symmetry rule may remove all representatives of an actual solution class.

Complexity and Practical Performance

The worst-case time of a search tree with branching factor b and depth d is O(b^d). If domains have size k and there are n variables, naïve enumeration may require O(k^n) assignments. Space for depth-first search is typically O(d), excluding storage for domains and constraints; best-first branch-and-bound can require O(number of frontier nodes).

These bounds describe worst cases, not typical performance. Effective pruning may reduce the explored nodes by orders of magnitude, but no universal guarantee follows unless the problem has additional structure. Many important problems, including general SAT, graph colouring, TSP, and scheduling variants, are NP-hard. Search algorithms are therefore evaluated using both theoretical complexity and empirical measures such as nodes expanded, propagation time, bound calculations, memory consumption, and time to first feasible or optimal solution.

A useful engineering practice is to instrument the solver. Record the number of generated nodes, rejected nodes by reason, maximum depth, incumbent improvements, and time spent in propagation and bounding. These measurements reveal whether a problem is limited by weak heuristics, expensive bounds, or excessive memory use.

Applied Case Study: Hospital Operating-Room Scheduling

Background

Consider an illustrative hospital that must schedule surgical procedures across operating rooms during a daily planning horizon. Each procedure has a duration, a surgeon, an equipment requirement, and a preferred or mandatory time window. Some procedures must precede others, and emergency capacity must remain available.

Situation and Problem

The hospital seeks to maximize a weighted value reflecting clinical priority and resource utilization. A schedule is feasible only if procedures do not overlap in the same room, surgeons and specialized equipment are not double-booked, precedence constraints are respected, and reserved emergency capacity is preserved.

Analysis

A direct enumeration of assignments of procedures to rooms and time slots is enormous. The problem contains both hard constraints and a meaningful objective. It is therefore suitable for a hybrid constraint-search and branch-and-bound approach.

Variables represent the room and start time of each procedure. Domains contain feasible room-time pairs. Propagation removes pairs that conflict with already assigned procedures, surgeon availability, equipment availability, or precedence windows. A cumulative resource propagator checks whether total demand exceeds capacity during any interval.

For maximization, an optimistic bound can assume that every unscheduled procedure still fits into available capacity and contributes its full priority value. This bound is deliberately optimistic. If its value is no better than the incumbent schedule, the node is pruned. A greedy scheduler can provide an initial incumbent by placing high-priority procedures in the earliest compatible slots.

MRV selects the procedure with the fewest remaining room-time placements. A degree-based tie-breaker favours procedures sharing scarce equipment or surgeons. Values may be ordered by earliest deadline or by least disruption to other procedures, depending on whether rapid feasibility or objective quality is more important.

Approach and Solution

The solver first applies mandatory constraints and reserves emergency capacity. It then constructs a feasible schedule using a greedy heuristic. Branching assigns the most constrained procedure, propagation updates domains, and bounding evaluates the best possible priority value below the partial schedule. Search continues until all remaining nodes are pruned or a specified optimality gap is reached.

Outcome

The method produces either an optimal schedule for the model or a schedule accompanied by a mathematically justified bound on how far it may be from optimal. If exact optimality is too expensive within the planning deadline, the hospital can use a time limit and report the incumbent together with the best unresolved bound. This is more informative than reporting a schedule without evidence of quality.

Learning Points

The case demonstrates that modelling quality often matters more than recursion alone. Strong resource constraints improve propagation, a good initial schedule improves objective pruning, and valid bounds support transparent quality claims. It also illustrates that operational settings may prefer a high-quality schedule quickly over a proof of absolute optimality.

Challenges, Risks, and Common Mistakes

A frequent error is confusing a heuristic estimate with a valid bound. If a minimization lower bound accidentally overestimates the true achievable quality, the algorithm may prune an optimal solution and become incorrect. Bounds must be tested against known small instances and, where possible, proved mathematically.

Another mistake is checking constraints too late. Delayed detection increases the search tree. Conversely, propagation that is too aggressive or repeatedly recomputes unchanged information can dominate runtime. Mutable state must be restored exactly after recursion; stale domain values and incomplete undo operations cause subtle errors.

Poor variable ordering can overwhelm an otherwise sound algorithm. Similarly, best-first search may run out of memory even when it expands fewer nodes than depth-first search. Floating-point objective comparisons require tolerances, especially when bounds are derived from numerical relaxations.

A search algorithm may also appear successful because it finds a good solution early while silently failing to prove optimality. Applications must distinguish feasible, optimal, and bounded-quality outputs.

Professional, Ethical, and Governance Considerations

Search-based systems often allocate scarce resources: hospital capacity, delivery routes, energy, educational places, or credit and staffing opportunities. The objective function therefore embodies institutional values. A mathematically optimal solution may be unacceptable if it ignores fairness, accessibility, safety, or legally protected groups.

Constraints should distinguish hard requirements from preferences. Violating a safety constraint cannot be treated like a small penalty for inconvenience. Where soft constraints are used, penalty weights should be documented and reviewed by domain experts. Sensitive applications should preserve audit trails showing the model, bounds, incumbent solutions, and reasons for rejecting alternatives.

Human oversight remains important when input data are uncertain or when circumstances change. An optimal schedule based on inaccurate durations or unavailable resources is not operationally optimal. Governance should include validation, scenario testing, privacy protection, and procedures for overriding the automated recommendation.

AI, Automation, and Emerging Directions

Constraint search is closely connected with artificial intelligence. SAT, mixed-integer programming, constraint programming, and automated planning all use forms of branching, propagation, relaxation, and bounding. Machine learning can assist by predicting promising variables, ordering values, estimating node difficulty, or selecting among solver configurations.

Learned heuristics must not compromise correctness. A model may choose the next branch, but feasibility checks and admissible bounds must remain trustworthy if exactness is required. Neural guidance is especially useful in large repeated problem families, where experience from earlier instances can improve search ordering.

Conflict-directed backjumping and clause learning record explanations for failure and prevent repeated rediscovery of the same contradiction. Portfolio solvers run several strategies and allocate time according to observed performance. Parallel search divides the state space among processors, although load balancing and shared incumbent updates require care.

A continuing trend is hybrid optimization: exact search supplies guarantees while heuristics, local search, and learned policies provide speed. In many industrial settings, the desired result is not merely an answer but an answer with a transparent feasibility certificate, an optimality proof, or a defensible quality gap.

Best Practices for Implementation

Begin with a precise model. Identify variables, domains, hard constraints, soft objectives, and symmetries before writing search code. Implement a simple correct solver first, then add propagation and heuristics incrementally. Keep feasibility testing separate from objective evaluation so that each can be verified independently.

Use depth-first search when memory is limited or when a good incumbent is easy to construct. Use best-first methods when bounds are strong and memory is available. Select MRV and degree heuristics for constraint satisfaction, and use problem-specific branching for optimization. Prefer bounds based on proven relaxations over intuitive but unverified estimates.

Test on small instances for which exhaustive enumeration is possible. Compare node counts with and without each heuristic, verify that all returned solutions are feasible, and cross-check objective values against an independent solver or mathematical formulation. Report both solution quality and computational effort.

Chapter Summary

Backtracking, branch-and-bound, and constraint search are state-space techniques for managing combinatorial complexity. Backtracking explores partial assignments and prunes infeasible states. Branch-and-bound maintains an incumbent and uses admissible bounds to eliminate states that cannot improve the current solution. Constraint search strengthens backtracking through propagation, variable and value ordering, and global constraints.

Their worst-case complexity remains exponential for many important problems, but careful modelling and search control can make large practical instances tractable. Strong bounds, early feasible solutions, symmetry breaking, and informed branching are central design choices. Correctness depends on complete branching, sound pruning, accurate state restoration, and valid bounds. In professional applications, search must also provide transparent quality information and respect safety, fairness, privacy, and human oversight.

Key Terms

State-space tree: A tree representing sequences of decisions from an initial state to complete or terminal states.

Partial assignment: Values assigned to only some variables of a problem.

Backtracking: Depth-first search that reverses decisions when a partial state cannot lead to a solution.

Feasibility: The property of satisfying all required constraints.

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

Propagation: Removal of domain values that cannot participate in any valid completion.

Forward checking: Propagation that removes values conflicting with the latest assignment.

Arc consistency: A condition in which every domain value has compatible support in connected domains.

Branch-and-bound: Optimization search using branching and objective bounds to discard noncompetitive nodes.

Incumbent: The best complete solution found so far.

Admissible bound: A bound that is guaranteed not to exclude an optimal solution.

Relaxation: A simplified problem obtained by removing restrictions from the original problem.

Pruning: Eliminating a search node and all of its descendants.

MRV heuristic: Selection of the variable with the smallest remaining domain.

Degree heuristic: Selection based on the number of constraints involving an unassigned variable.

Least-constraining value: A value that leaves the greatest flexibility for other variables.

Global constraint: A constraint expressing a structured relationship among many variables.

Symmetry breaking: Adding restrictions that select one representative from equivalent solutions.

Optimality gap: A bound on the difference between a known solution and the best possible solution.

Conflict learning: Recording causes of failure to avoid repeating equivalent unsuccessful search.

Review Questions

Short Answer Questions

1. What is the difference between a feasible state and a complete state?

2. Why must an upper bound for a maximization problem be optimistic?

3. What role does the incumbent play in branch-and-bound?

4. How does forward checking reduce a CSP search tree?

5. Explain the purpose of the MRV heuristic.

Long Answer Questions

1. Describe the design of a recursive backtracking algorithm and explain the conditions required for correctness.

2. Compare backtracking and branch-and-bound with respect to pruning criteria, memory, and problem types.

3. Explain arc consistency, including how propagation can cause further domain reductions.

4. Discuss how relaxations can be used to construct bounds for combinatorial optimization.

5. Analyse the role of modelling, heuristics, and propagation in the operating-room scheduling case.

Analytical / Application Questions

1. Design a branch-and-bound strategy for a knapsack problem. Specify the branching rule, incumbent, bound, and pruning condition.

2. Given a graph-colouring instance, propose variable and value-ordering heuristics and explain how each could affect search performance.

3. A scheduling solver reports a feasible solution but cannot prove optimality before its deadline. Explain what information should be reported to decision-makers and why.

22. Multiple Choice Questions with Answers

Question 1

In a maximization branch-and-bound algorithm, when can a node be safely pruned?

A. When its upper bound is no greater than the incumbent value

B. When its lower bound is greater than zero

C. When it has more than one child

D. When its partial assignment is feasible

Correct Answer: A. When its upper bound is no greater than the incumbent value

Question 2

What is the principal pruning criterion in ordinary backtracking for a constraint satisfaction problem?

A. The node has a low objective value

B. The partial assignment violates a constraint

C. The node was generated after the incumbent

D. The domain contains more than two values

Correct Answer: B. The partial assignment violates a constraint

Question 3

The minimum-remaining-values heuristic selects:

A. The variable with the largest numerical value

B. The variable assigned most recently

C. The unassigned variable with the smallest current domain

D. The variable with the fewest constraints overall

Correct Answer: C. The unassigned variable with the smallest current domain

Question 4

For a minimization problem, a valid admissible bound at a partial node is generally a:

A. Lower bound on the cost of any completion

B. Guaranteed upper bound on every completion cost

C. Random estimate of completion cost

D. Cost of the first solution found

Correct Answer: A. Lower bound on the cost of any completion

Question 5

Why can a good initial feasible solution improve branch-and-bound performance?

A. It reduces the number of variables

B. It provides an incumbent against which more nodes can be pruned

C. It converts an NP-hard problem into a polynomial one

D. It removes the need for valid bounds

Correct Answer: B. It provides an incumbent against which more nodes can be pruned

Question 6

Which technique removes domain values that have no compatible supporting value in a neighbouring domain?

A. Depth-first traversal

B. Arc consistency

C. Symmetry breaking

D. Greedy completion

Correct Answer: B. Arc consistency

Question 7

In the hospital scheduling case, why must emergency capacity be modelled as a hard or protected constraint?

A. Because it guarantees the largest objective value

B. Because violating it may compromise operational safety and availability

C. Because it eliminates all branching

D. Because it makes every schedule optimal

Correct Answer: B. Because violating it may compromise operational safety and availability

Question 8

What is a principal risk of using an invalid bound in branch-and-bound?

A. The algorithm may prune an optimal solution

B. The search tree must always double in size

C. The incumbent becomes infeasible automatically

D. Propagation becomes logically stronger

Correct Answer: A. The algorithm may prune an optimal solution

Question 9

Which statement best describes symmetry breaking?

A. Replacing every constraint with a random constraint

B. Selecting a canonical representative among equivalent solutions

C. Removing all objective functions

D. Exploring symmetric branches in parallel

Correct Answer: B. Selecting a canonical representative among equivalent solutions

Question 10

If a solver returns a feasible solution but has not exhausted the search tree, what can it claim without further evidence?

A. The solution is necessarily optimal

B. The solution is feasible, but optimality may remain unproved

C. No better solution exists

D. The problem is polynomial-time solvable

Correct Answer: B. The solution is feasible, but optimality may remain unproved