하한 (Lower Bounds)
최적값의 하한을 계산해 정확 탐색을 가지치고 해의 품질을 보증하는 기법.
다른 이름: Lower Bounds · lower bound · 하한값 · Martello-Toth bounds
정확 해법의 효율과 품질 보증을 떠받치는 바운딩 기법(v1에서는 method로 분류).
2D 절단·적재에서는 면적 하한(총 부품 면적 ÷ 빈 면적)부터 Martello–Toth 계열의
이산 하한까지 여러 하한이 쓰이며, 분기 한정에서 유망하지
않은 가지를 잘라내고 휴리스틱 해의 최적성 간극(optimality gap)을 보증한다. 2차원
패킹의 하한은 Lodi, Martello & Monaci(2002)의 서베이에 정리되어 있다.
주장 & 증거
모든 관계는 증거 등급을 가진 하나의 주장이고, 문제 간 관계에는 해당되는 경우 등가 수준도 표시합니다. 증거 정책을 참고하세요.
A–X는 근거의 신뢰도, E0–E4는 문제 사이의 수학적 유사도입니다. 두 축은 서로 독립적입니다.
이 항목에서 나가는 관계 1
- 방법 공유
하한 계산은 분기 한정의 가지치기를 이끄는 핵심 구성 요소다 — 강한 하한일수록 탐색 트리를 더 많이 잘라낸다.
증거A · 동료심사 논문 / 공식 문서등가E2 · 방법론 공유출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
서지정보
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.
| 관계 | 주장 | 증거 | 등가 | 출처 |
|---|---|---|---|---|
방법 공유 | 하한 계산은 분기 한정의 가지치기를 이끄는 핵심 구성 요소다 — 강한 하한일수록 탐색 트리를 더 많이 잘라낸다. | A · 동료심사 논문 / 공식 문서 | E2 · 방법론 공유 |
|
이 항목으로 들어오는 관계 1
- 사용 방법
2D 빈 패킹의 정확 해법은 면적 하한과 Martello–Toth류 이산 하한 등 강한 하한으로 탐색을 가지친다.
증거A · 동료심사 논문 / 공식 문서출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
서지정보
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.
| 관계 | 주장 | 증거 | 등가 | 출처 |
|---|---|---|---|---|
사용 방법 | 2D 빈 패킹의 정확 해법은 면적 하한과 Martello–Toth류 이산 하한 등 강한 하한으로 탐색을 가지친다. | A · 동료심사 논문 / 공식 문서 | — |
|