Intuition of the method
Linear programs can be solved efficiently with the simplex method. Integer linear programs add the extra condition that some variables must be integers. Branch and bound uses the LP solver as a subroutine.
The method repeatedly solves an LP relaxation: the same problem with the integrality restrictions removed. The relaxed optimum gives an upper bound for a maximization ILP because every integer-feasible solution is also feasible for the relaxation.
Two pieces of information
Lower bound A feasible integer solution gives a value that the optimum is at least as good as.
Upper bound An LP relaxation gives a value that no integer solution inside that part can exceed.
When can a part be discarded?
- The LP relaxation is infeasible.
- The LP optimum is already integer.
- The LP upper bound is no better than the best integer solution already found.
If none of these happens, branch on a variable whose LP value is fractional.
Developing the method by example
The chapter develops branch and bound with this integer linear program:
Start with the LP relaxation
Removing the integrality restriction gives an optimum near (x*,y*)=(4.7135,5.5787) with value z*≈46.7472. Since the objective coefficients are integers and integer solutions have integer objective values, this gives the stronger integer upper bound z ≤ 46.
Both variables are not integer, so we split the region. The chapter branches first on x:
x ≥ 5 or x ≤ 4.Outcome for the chapter instance
The left branch x ≥ 5 has LP optimum (5,3), value 35, so it is an integer incumbent.
The right branch x ≤ 4 has LP optimum (4,5.65), value 44.25, so it is split on y.
The sub-branch y ≥ 6 has upper bound 32, which cannot beat 35. The sub-branch y ≤ 5 gives the integer solution (4,5) with value 41, the final optimum.
Interactive branch-and-bound workbench
Edit a two-variable maximization ILP, then solve it one branch-and-bound node at a time. The default data is the chapter example.
Current node geometry
Branch-and-bound tree
Each node is one part of the feasible region. The label on an edge is the extra constraint used to create the child. Click a node in the tree to inspect its LP relaxation in the geometry panel above.
| Node | Added constraints | LP relaxation | Integer upper bound | Status |
|---|
Summary of branch and bound
0. Initialization
Start with 𝒫 = {F}, where F is the feasible region of the LP relaxation of the original ILP. There is no incumbent integer solution yet unless one is already known.
1. Solve one relaxation
Choose a set S from 𝒫, remove it from 𝒫, and solve the LP with the original objective over S.
- If the LP is infeasible, discard S.
- If the LP optimum is integer, update the incumbent if it improves the best known value, then discard S.
- If the LP upper bound is no better than the incumbent, discard S.
- Otherwise, choose a fractional variable xᵢ* and replace S by two children: xᵢ ≤ ⌊xᵢ*⌋ and xᵢ ≥ ⌈xᵢ*⌉.
2. Stop condition
When 𝒫 is empty, return the incumbent. Every part of the original feasible region has either been solved exactly, shown infeasible, or bounded away from improvement.
Different choices, same optimum
Branch and bound does not force one unique branching rule. If multiple LP variables are fractional, you may branch on any one of them. It also does not force one unique open-node order. These choices can change the number of LP relaxations solved, but they do not change the final optimum when the method is carried out correctly.
Why a good incumbent helps
A feasible integer solution gives a lower bound in a maximization problem. Once the incumbent is strong, many LP-relaxation nodes can be pruned because their upper bounds are not competitive.
Infeasible relaxations
A branch can add constraints that make even the LP relaxation infeasible. Then the integer-restricted version inside that branch is infeasible as well, so the branch can be discarded immediately.
