Branch and Bound

Exact tree search that prunes subproblems using bounds.

Also called: Branch and Bound · B&B · 분기-가격(확장)

An exact search that partitions the solution space into a tree of subproblems and, at each node, computes a bound (a limit on the best value that branch can reach) to prune any branch that cannot beat the incumbent — the stronger the bound, the more of the tree it cuts. It is the backbone of exact methods for cutting & packing such as 2D Bin Packing, and combined with column generation it becomes branch-and-price for integer programs with many variables.

Claims & evidence

Every relationship is a claim with an evidence grade; applicable problem-to-problem relationships also carry an equivalence level. See the evidence policy.

A–X describes evidence reliability; E0–E4 describes mathematical similarity between problems. The two axes are independent.

Relationships to this entry 9

uses method
1D Cutting Stock to Branch and Bound
Integer solutions to cutting stock have been reported with branch-and-price, combining column generation with branch and bound.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialBPPLIB: a library for bin packing and cutting stock problems
  Citation details
  Delorme, M., Iori, M., Martello, S. (2018). BPPLIB: a library for bin packing and cutting stock problems. Optimization Letters 12:235-250.
uses method
2D Bin Packing to Branch and Bound
Exact approaches to 2D bin packing have been reported with branch-and-bound (and branch-and-price) formulations.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method
2D Knapsack to Branch and Bound
Exact branch-and-bound algorithms have been proposed for the geometric 2D knapsack, using a one-dimensional knapsack relaxation (rectangle areas as weights) as a bound (Caprara & Monaci 2004).
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialOn the two-dimensional Knapsack Problem
  Citation details
  Caprara, A., Monaci, M. (2004). On the two-dimensional Knapsack Problem. Operations Research Letters 32(1):5-14. Exact branch-and-bound algorithms for the geometric 2D knapsack, using a one-dimensional knapsack relaxation on rectangle areas.
uses method
3D Bin Packing to Branch and Bound
Exact approaches to 3D bin packing / container loading have been reported with branch-and-bound formulations.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialConstraints in container loading – A state-of-the-art review
  Citation details
  Bortfeldt, A., Wäscher, G. (2013). Constraints in container loading – A state-of-the-art review. EJOR 229(1):1-20.
uses method
Guillotine Cutting to Branch and Bound
Exact approaches to guillotine cutting have been reported with branch and bound.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method
0/1 Knapsack Problem to Branch and Bound
Besides dynamic programming, the 0/1 knapsack problem is also solved exactly by branch and bound.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialKnapsack Problems
  Citation details
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
shares method with
Column Generation to Branch and Bound
Combining column generation with branch and bound yields branch-and-price, used for exact solutions to integer cutting & packing problems.
EvidenceA · Peer-reviewed / official
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem
  Citation details
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
- Source grade: A — Peer-reviewed / officialBranch-and-Price: Column Generation for Solving Huge Integer Programs
  Citation details
  Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., Vance, P.H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research 46(3):316-329. Formalizes combining column generation with branch-and-bound (branch-and-price).
shares method with
Integer Linear Programming to Branch and Bound
Integer linear programs are solved exactly by branch-and-bound — ILP is the model that states the problem, branch-and-bound the method that solves it.
EvidenceA · Peer-reviewed / official
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
shares method with
Lower Bounds to Branch and Bound
Lower-bound computation is the core component that drives pruning in branch-and-bound — the stronger the bound, the more of the search tree it cuts.
EvidenceA · Peer-reviewed / official
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.

Relationships to this entry
Relationship	Claim	Evidence	Equiv.	Sources
uses method 1D Cutting Stock to Branch and Bound	Integer solutions to cutting stock have been reported with branch-and-price, combining column generation with branch and bound.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialBPPLIB: a library for bin packing and cutting stock problems Citation details Delorme, M., Iori, M., Martello, S. (2018). BPPLIB: a library for bin packing and cutting stock problems. Optimization Letters 12:235-250.
uses method 2D Bin Packing to Branch and Bound	Exact approaches to 2D bin packing have been reported with branch-and-bound (and branch-and-price) formulations.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method 2D Knapsack to Branch and Bound	Exact branch-and-bound algorithms have been proposed for the geometric 2D knapsack, using a one-dimensional knapsack relaxation (rectangle areas as weights) as a bound (Caprara & Monaci 2004).	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialOn the two-dimensional Knapsack Problem Citation details Caprara, A., Monaci, M. (2004). On the two-dimensional Knapsack Problem. Operations Research Letters 32(1):5-14. Exact branch-and-bound algorithms for the geometric 2D knapsack, using a one-dimensional knapsack relaxation on rectangle areas.
uses method 3D Bin Packing to Branch and Bound	Exact approaches to 3D bin packing / container loading have been reported with branch-and-bound formulations.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialConstraints in container loading – A state-of-the-art review Citation details Bortfeldt, A., Wäscher, G. (2013). Constraints in container loading – A state-of-the-art review. EJOR 229(1):1-20.
uses method Guillotine Cutting to Branch and Bound	Exact approaches to guillotine cutting have been reported with branch and bound.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method 0/1 Knapsack Problem to Branch and Bound	Besides dynamic programming, the 0/1 knapsack problem is also solved exactly by branch and bound.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialKnapsack Problems Citation details Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
shares method with Column Generation to Branch and Bound	Combining column generation with branch and bound yields branch-and-price, used for exact solutions to integer cutting & packing problems.	A · Peer-reviewed / official	E2 · shared methodology	Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem Citation details Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach. Source grade: A — Peer-reviewed / officialBranch-and-Price: Column Generation for Solving Huge Integer Programs Citation details Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., Vance, P.H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research 46(3):316-329. Formalizes combining column generation with branch-and-bound (branch-and-price).
shares method with Integer Linear Programming to Branch and Bound	Integer linear programs are solved exactly by branch-and-bound — ILP is the model that states the problem, branch-and-bound the method that solves it.	A · Peer-reviewed / official	E2 · shared methodology	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
shares method with Lower Bounds to Branch and Bound	Lower-bound computation is the core component that drives pruning in branch-and-bound — the stronger the bound, the more of the search tree it cuts.	A · Peer-reviewed / official	E2 · shared methodology	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.