Discrete Mathsfor Engineers

1. Problem Model & Search Space

Branch & Bound is often introduced informally as a method that explores possibilities and discards branches that cannot lead to the optimal solution.

That intuition is useful, but to understand the technique rigorously, we must first define the problem model and the search space it explores.

1.1 Why start with the model?

Branch & Bound is not tied to a single specific problem. It is a general strategy for solving combinatorial optimization problems.

Therefore, before discussing bounds, pruning, or implementation, we must answer:

• What is a candidate solution?
• How is a partial solution represented?
• What does it mean for a solution to be feasible?
• What exactly are we optimizing?

1.2 Candidate solutions

A candidate solution is typically constructed as a sequence of decisions:

Each variable xᵢ represents a choice made at step i, usually selected from a domain of possible values.

A complete assignment may represent a final solution, while a prefix (x₁, …, xᵢ) represents a partial solution.

1.3 The search space

The set of all candidate solutions defines the search space.

This space is naturally modeled as a tree:

• The root is the empty solution
• Each level corresponds to one additional decision
• Each edge represents a choice
• Each node represents a partial assignment

In abstract terms, a node can be written as (x₁, …, xᵢ).

1.4 Feasibility

Not every partial solution should be explored further.

A Branch & Bound problem includes constraints that determine whether a partial solution can still be extended into a valid full solution.

If the current assignment already violates the problem structure, that branch can be stopped immediately.

1.5 Objective function

Unlike classical backtracking, in Branch & Bound we are not satisfied with just any valid solution: we want the best feasible solution according to an objective function.

Formally, we want to find a solution x* such that:

where S is the set of feasible solutions and f(x) measures the value of a solution.

1.6 Maximization and minimization

Branch & Bound applies to two major types of problems:

• Maximization: maximize profit, value, or score
• Minimization: minimize cost, distance, or time

The structure of the search remains the same. What changes is how we compare solutions and interpret bounds.

1.7 Why this matters

The search space often grows exponentially with the size of the input. A brute-force method would examine all possibilities.

In real problems, this quickly becomes infeasible. That is why we need a strategy that preserves correctness while drastically reducing the number of explored branches.

1.8 Example problems

This model appears in many classical problems:

• 0/1 Knapsack
• Traveling Salesman Problem
• Scheduling
• Assignment problems
• Integer programming

In all of them, the core idea is the same: build solutions incrementally, evaluate feasibility and quality, and avoid exploring regions that cannot contain the optimal solution.