Branch‑and‑bound errors in Excel Solver appear when integer or binary constraints are mis‑defined, branching nodes become infeasible, the continuous relaxation is unbounded, or Solver cannot prune the search tree due to incorrect bounds or nonlinear expressions. This page explains how branch‑and‑bound works inside Solver, why errors occur, and how to fix them using multiple numerical examples.

1. Why branch‑and‑bound fails in Excel Solver

Branch‑and‑bound fails when:

• The continuous relaxation is infeasible or unbounded.
• Integer or binary variables are not defined correctly.
• Constraints eliminate all integer-feasible nodes.
• Nonlinear expressions prevent valid branching.
• Bounds are missing, causing infinite branching.
• Decision variable cells contain formulas instead of numbers.

Because branch‑and‑bound explores a tree of integer-feasible regions, even one incorrect constraint can cause the entire search to collapse.

2. Common branch‑and‑bound Solver errors

2.1 “Solver could not find a feasible integer solution”

Occurs when the continuous relaxation is feasible but no integer point satisfies all constraints.

2.2 “Branching stopped — no integer feasible solution found”

Usually caused by wrong inequality directions or missing bounds.

2.3 “Binary/integer variables take fractional values”

Means Solver was not told the variables are integer or binary.

2.4 “Objective does not converge”

Happens when the continuous relaxation is unbounded, so branch‑and‑bound cannot begin.

2.5 Solver freezes or takes extremely long

Occurs when the model is too large, nonlinear, or missing pruning constraints.

3. How to correctly set up branch‑and‑bound models

3.1 Step 1 — Define integer or binary variables cleanly

Cells must contain numbers (0 is fine). No formulas.

3.2 Step 2 — Add explicit bounds

Branch‑and‑bound requires finite bounds: \[ 0 \le x_i \le M \] If you omit upper bounds, Solver may branch indefinitely.

3.3 Step 3 — Ensure all constraints reference the integer cells

A single wrong reference (e.g., B5 instead of B4) can eliminate all feasible nodes.

3.4 Step 4 — Use linear expressions only

Nonlinear expressions like \(x_1 \cdot x_2\) break Simplex‑based branching.

3.5 Step 5 — Choose the correct solving method

Use:
Simplex LP + Integer constraints for linear models GRG Nonlinear + Integer constraints only if nonlinearities are unavoidable

4. Numerical example 1 — Integer knapsack with branching failure

A knapsack model fails because the continuous relaxation is unbounded.

4.1 Incorrect model

x1 = units of Product 1 (integer)
x2 = units of Product 2 (integer)

Profit: 6, 5
Weight: 3, 2
Capacity: 20

Incorrect constraint:

\[ 3x_1 + 2x_2 \le 20 \] but no upper bounds on \(x_1\) or \(x_2\).

Continuous relaxation pushes variables to infinity → branch‑and‑bound cannot start.

4.2 Fix

Add bounds: \[ 0 \le x_1 \le 20,\quad 0 \le x_2 \le 20 \]

Now the continuous relaxation is finite, and branch‑and‑bound finds:

• \(x_1 = 4\)
• \(x_2 = 2\)

5. Numerical example 2 — Binary selection with infeasible branching

A company must choose exactly two out of four projects.

5.1 Incorrect setup

Decision variables contain formulas instead of numbers:

B4 = "=B1"
C4 = "=C1"
D4 = "=D1"
E4 = "=E1"

Branch‑and‑bound cannot flip 0→1 or 1→0 because the cells are not editable.

5.2 Fix

Replace formulas with numbers (0). Declare B4:E4 as binary.

Constraint: \[ x_1 + x_2 + x_3 + x_4 = 2 \]

Branch‑and‑bound now finds a valid combination.

6. Numerical example 3 — Integer production with conflicting constraints

A factory produces two products. Integer constraints cause infeasibility.

6.1 Data

Profit: 40, 30
Machine hours: 2, 1
Labor hours: 1, 1.5
Machine cap = 10
Labor cap = 8

6.2 Incorrect constraints

Labor constraint mistakenly written as: \[ x_1 + 15x_2 \le 8 \] instead of: \[ x_1 + 1.5x_2 \le 8 \]

Continuous relaxation is feasible, but integer nodes are impossible → branch‑and‑bound fails.

6.3 Fix

Correct labor coefficient to 1.5. Add integer constraints on \(x_1, x_2\).

Solver returns:

• \(x_1 = 3\)
• \(x_2 = 2\)

7. Checklist for fixing branch‑and‑bound issues

• Ensure integer/binary cells contain numbers, not formulas.
• Add explicit upper bounds to all integer variables.
• Verify every constraint references the correct cells.
• Check feasibility of the continuous relaxation first.
• Remove nonlinear expressions unless using GRG Nonlinear.
• Use SUMPRODUCT for objective and resource constraints.
• Declare integer/binary constraints explicitly in Solver.