Integer programming: branch and bound

Pure, mixed and binary integer programmes, LP-relaxation bounds, why rounding fails, branch and bound with fathoming rules, and cutting planes.

Drafted with Aria, reviewed by the AiCanCode.org team. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Many production decisions come in whole numbers: machines to buy, batches to run, trucks to send, whether to open a plant (yes/no). Rounding an LP answer can give a plan that is infeasible or far from optimal. Branch and bound is the systematic way to find the true integer optimum, and it is the method inside every commercial MILP solver used for scheduling and facility location.

Key ideas

Types of integer programmes.

  • Pure integer (IP): all variables integer.
  • Mixed integer (MILP): some integer, some continuous.
  • Binary (0-1): variables are yes/no decisions — project selection, fixed charges, plant opening, either-or constraints.

LP relaxation. Drop the integer requirement and solve the LP. Its optimum is a bound: for a maximisation the relaxation value Z_LP ≥ Z_IP (an upper bound); for minimisation it is a lower bound. If the LP optimum happens to be integer, it is the IP optimum.

Why rounding fails. Rounded points can violate constraints, and even feasible rounded points may be far from optimal because the integer optimum need not be near the LP vertex.

Branch and bound (maximisation).

  1. Solve the LP relaxation at the current node.
  2. Fathom (stop exploring) the node if: (a) the LP is infeasible, (b) its Z is no better than the incumbent (best integer solution found so far) — fathomed by bound, or (c) its solution is all-integer — record it as the new incumbent if better.
  3. Otherwise branch: pick a fractional variable xⱼ = v and create two sub-problems with xⱼ ≤ ⌊v⌋ and xⱼ ≥ ⌊v⌋ + 1. The strip ⌊v⌋ < xⱼ < ⌊v⌋ + 1 contains no integer point, so nothing is lost.
  4. Repeat until every node is fathomed. The incumbent is optimal. Each child's LP value is never better than its parent's, so bounds tighten down the tree. Depth-first search finds an incumbent quickly; best-bound search explores fewer nodes on average.

Cutting planes (Gomory). An alternative: add a constraint (cut) from a fractional row of the optimal simplex tableau that removes the current fractional vertex but no integer point, and re-solve. Modern solvers combine cuts with branching ("branch and cut").

Modelling with binaries. Fixed cost: cost = F·y + c·x with x ≤ U·y, y ∈ {0, 1}. Either-or constraints: g₁(x) ≤ b₁ + M·y and g₂(x) ≤ b₂ + M(1 − y). At most k of n projects: Σ yⱼ ≤ k.

Formulas

  • Integer programme: Max Z = cᵀx, A x ≤ b, x ≥ 0, xⱼ integer for j ∈ I
  • Bounding (Max): Z_IP ≤ Z_LP; (Min): Z_IP ≥ Z_LP
  • Branching on fractional xⱼ = v: xⱼ ≤ ⌊v⌋ or xⱼ ≥ ⌊v⌋ + 1
  • Fathoming by bound (Max): Z_node ≤ Z_incumbent
  • Gomory cut from a row with fractional RHS: Σ fᵢⱼ · xⱼ ≥ fᵢ (fᵢⱼ, fᵢ = fractional parts)
  • Fixed charge link: x ≤ U · y, y ∈ {0, 1}

Symbols: x = decision variables (units, number of machines); c = profit per unit (₹/unit); A, b = technology matrix and resources; ⌊v⌋ = largest integer ≤ v; U = upper limit on x; y = binary decision; fᵢⱼ = fractional part of a tableau coefficient.

Worked examples

Example 1 (standard branch and bound). Max Z = 7x₁ + 9x₂ subject to −x₁ + 3x₂ ≤ 6, 7x₁ + x₂ ≤ 35, x₁, x₂ ≥ 0 and integer.

  1. Root LP: solve −x₁ + 3x₂ = 6 and 7x₁ + x₂ = 35. From the second, x₂ = 35 − 7x₁; substitute: −x₁ + 105 − 21x₁ = 6 → x₁ = 4.5, x₂ = 3.5. Z = 31.5 + 31.5 = 63 (upper bound).
  2. Branch on x₁ = 4.5: node A (x₁ ≤ 4) and node B (x₁ ≥ 5).
  3. Node A: x₁ = 4, x₂ = min((6 + 4)/3, 35 − 28) = 10/3; Z = 28 + 30 = 58. Fractional, so branch on x₂: A1 (x₂ ≤ 3), A2 (x₂ ≥ 4).
  4. A1: x₁ = 4, x₂ = 3, Z = 28 + 27 = 55 — integer, incumbent = 55.
  5. A2: x₂ ≥ 4 needs −x₁ + 12 ≤ 6 → x₁ ≥ 6, contradicting x₁ ≤ 4 → infeasible, fathomed.
  6. Node B: 7x₁ + x₂ ≤ 35 with x₁ ≥ 5 forces x₁ = 5, x₂ = 0; Z = 35 < 55 → fathomed by bound.
  7. Optimum x₁ = 4, x₂ = 3, Z = 55. Rounding the LP point to (5, 4) or (4, 4) is infeasible.

Example 2 (GATE-type: bounding in action). Max Z = 5x₁ + 4x₂ subject to x₁ + x₂ ≤ 5, 10x₁ + 6x₂ ≤ 45, x₁, x₂ ≥ 0 and integer.

  1. Root LP: x₁ + x₂ = 5 and 10x₁ + 6x₂ = 45 → 10x₁ + 6(5 − x₁) = 45 → 4x₁ = 15 → x₁ = 3.75, x₂ = 1.25. Z = 18.75 + 5 = 23.75.
  2. Rounding fails: (4, 1) gives 10(4) + 6(1) = 46 > 45 (infeasible); (3, 1) gives only Z = 19.
  3. Branch x₁ ≤ 3: optimum at x₁ = 3, x₂ = 2, Z = 15 + 8 = 23 — integer, incumbent = 23.
  4. Branch x₁ ≥ 4: x₂ ≤ (45 − 40)/6 = 5/6, so x₁ = 4, x₂ = 0.833, Z = 20 + 3.33 = 23.33 > 23 — cannot fathom; branch on x₂.
  5. x₂ ≥ 1: needs 10x₁ ≤ 39 → x₁ ≤ 3.9, contradicting x₁ ≥ 4 → infeasible.
  6. x₂ ≤ 0: x₁ = 4.5, x₂ = 0, Z = 22.5 < 23 → fathomed by bound (no need to branch further).
  7. Integer optimum x₁ = 3, x₂ = 2, Z = 23, against the LP bound 23.75.

Common mistakes

  • Rounding the LP solution and calling it optimal, or not checking that the rounded point is feasible.
  • Fathoming a node whose LP value is better than the incumbent; only "no better" nodes are fathomed by bound.
  • Getting the bound direction wrong in minimisation problems (there the LP value is a lower bound).
  • Branching with xⱼ ≤ v and xⱼ ≥ v using the fractional value itself instead of ⌊v⌋ and ⌊v⌋ + 1.
  • Stopping at the first integer solution found; every open node must be fathomed first.
  • Choosing a big-M so small that it cuts off feasible solutions in either-or models.

For GATE PI

  • Small two-variable branch-and-bound trees: the LP bound, the first branching constraints, the final integer optimum (NAT).
  • Concept MCQs: relaxation bounds, fathoming rules, why rounding fails, binary modelling of fixed charges and either-or choices.
  • Practise solving the node LPs graphically by adding one bound at a time.

Quick check

  1. A maximisation IP has LP-relaxation value 40.6. Can its integer optimum be 41?
  2. x₂ = 2.7 at a node. Write the two branches.
  3. A node's LP value is 18 and the incumbent is 20 (maximisation). What do you do?
  4. How do you model "produce product A only if machine A is bought"?

Answers: 1. No — Z_IP ≤ 40.6. 2. x₂ ≤ 2 and x₂ ≥ 3. 3. Fathom it by bound. 4. xA ≤ U·y with y ∈ {0, 1} the purchase decision.

Interview questions

All Operations Research interview questions

Try answering each one aloud before you open it.

  1. 1.Why can't you just round the LP solution to get an integer solution?Concept

    A rounded point can violate constraints — for example rounding (3.75, 1.25) to (4, 1) breaks 10x₁ + 6x₂ ≤ 45 — and even when it is feasible it can be far from optimal, because the integer optimum need not lie next to the LP vertex. Rounding is acceptable only when the variables are large (hundreds of units) and the error is negligible; for small counts and 0-1 decisions you need branch and bound or another exact method.

  2. 2.Explain the branch and bound method.Concept

    Solve the LP relaxation; its value bounds the integer optimum. If the solution is fractional, choose a fractional variable xⱼ = v and create two sub-problems with xⱼ ≤ ⌊v⌋ and xⱼ ≥ ⌊v⌋ + 1, which exclude the fractional point but no integer point. Solve each node's LP and fathom it if it is infeasible, integer (update the incumbent), or no better than the incumbent. When all nodes are fathomed, the incumbent is optimal.

  3. 3.What does it mean to fathom a node, and when do you do it?Concept

    Fathoming means no further branching from that node is needed. It happens when the node LP is infeasible, when its solution is already integer (it becomes the incumbent if it is better), or when its LP value is no better than the best integer solution found so far — since children can only be worse, nothing better can be found below it.

  4. 4.What is the relationship between the LP relaxation value and the integer optimum?Concept

    Relaxing integrality enlarges the feasible region, so the LP optimum is at least as good as the integer optimum: an upper bound for maximisation and a lower bound for minimisation. The gap between them, the integrality gap, shows how much the integer requirement costs and how much work branch and bound may need.

  5. 5.Give examples of where 0-1 variables are used in production engineering.Concept

    Plant or warehouse location (open or not), machine purchase decisions, project or capital-budgeting selection, fixed set-up costs where a product is made only if the machine is set up (x ≤ U·y), sequencing and either-or constraints, and assignment of jobs to machines. These create yes/no logic that ordinary LP cannot represent.

  6. 6.How does the cutting-plane method differ from branch and bound?Concept

    A cutting-plane method (Gomory) keeps a single LP and adds valid inequalities, derived from a fractional row of the optimal tableau, that slice off the current fractional vertex without removing any integer point; it re-solves until the LP optimum is integer. Branch and bound instead splits the problem into sub-problems. Pure cutting planes can converge slowly, so modern solvers combine both as branch and cut.

  7. 7.Which node do you explore next in branch and bound, and why does it matter?Concept

    Depth-first search follows one branch down, finds a feasible integer incumbent quickly and uses little memory, which helps prune other nodes early. Best-bound search always expands the open node with the best LP value, which tends to prove optimality with fewer nodes. The choice affects only computing effort, not the final optimum.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?

PreviousAssignment problemNext Network flow: shortest path, minimal spanning tree, maximal flow