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.

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

Relationships from this entry 1

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 from this entry
Relationship	Claim	Evidence	Equiv.	Sources
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.

Relationships to this entry 1

uses method
2D Bin Packing to Lower Bounds
Exact methods for 2D bin packing prune the search with strong lower bounds, from area bounds to Martello–Toth-style discrete bounds.
EvidenceA · Peer-reviewed / official
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 2D Bin Packing to Lower Bounds	Exact methods for 2D bin packing prune the search with strong lower bounds, from area bounds to Martello–Toth-style discrete bounds.	A · Peer-reviewed / official	—	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.