Lower Bounds
Bounding the optimum to prune exact search and certify solution quality.
Also called: Lower Bounds · lower bound · 하한값 · Martello-Toth bounds
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 evidence grade; applicable problem-to-problem relationships also carry an equivalence level. 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 |
|