Lower Bounds
Bounding the optimum to prune exact search and certify solution quality.
Also called: Lower Bounds · lower bound · 하한값 · Martello-Toth bounds
Last verified: 2026-05-27
The bounding technique that underpins both the efficiency and the quality
guarantees of exact methods (classified as a method in v1). In 2D cutting &
packing the bounds range from area bounds (total piece area ÷ bin area) to
Martello–Toth-style discrete bounds; they let
branch-and-bound prune unpromising branches and
certify the optimality gap of a heuristic solution. Lower bounds for
two-dimensional packing are surveyed by Lodi, Martello & Monaci (2002).
Claims & evidence
Every relationship is a claim with an equivalence level and an evidence grade. See the evidence policy.
| Relationship | Claim | Equiv. | Evidence | Sources |
|---|---|---|---|---|
| shares method withBranch 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. | E2 | A |
|
Neighborhood
Direct graph neighbors. Toggle depth to expand.
See also
Not directly linked, but conceptually close — by the connections and descriptions they share.
- Integer Linear ProgrammingMethod2 connections in common
- Guillotine CuttingFormal problem2 connections in common
- 2D KnapsackFormal problem2 connections in common
- 3D Bin PackingFormal problem2 connections in common
- Column GenerationMethod2 connections in common
- 1D Cutting StockFormal problem2 connections in common