형식 문제
2D 빈 패킹
직사각형을 최소 개수의 고정 크기 빈에 채우기.
다른 이름: 2D Bin Packing · 이차원 빈 패킹 · 2BP · 직사각형 빈 패킹
마지막 검증: 2026-05-27
정의
축 정렬 직사각형을 겹치지 않게 동일한 고정 크기 빈에 채워, 사용 빈 개수를 최소화한다.
예시
빈 크기 , 부품이 두 개와 두 개라고 하자. 한 빈에 두 개를 위아래로 쌓으면 정확히 가득 차고(), 나머지 두 개는 두 번째 빈 바닥에 나란히 놓인다. 최소 사용 빈은 2개다 — 총 면적이 로 빈 한 개의 16을 넘어 1개로는 불가능하다.
계열
2D 스트립 패킹, 2D 배낭과 함께 Wäscher 외 분류 체계의 핵심 직교 절단·적재 문제 중 하나다. 기하(직사각형 한정)에서 불규칙 네스팅과 대비되지만, 해법 방법론의 일부는 공유한다.
벤치마크
2DPackLib이 직접 벤치마크다(등급 A).
관련 노드
아래 깊이 1 그래프를 참고하라.
주장 & 증거
모든 관계는 등가 수준과 증거 등급을 가진 하나의 주장입니다. 증거 정책을 참고하세요.
| 관계 | 주장 | 등가 | 증거 | 출처 |
|---|---|---|---|---|
| 방법 공유2D 스트립 패킹 | 2D 빈 패킹과 스트립 패킹은 구성적·정확 방법을 공유하며, 단일 빈을 채울 때 스트립 패킹이 부분문제로 자주 등장한다. | E2 | B |
|
| 직접 벤치마크2DPackLib | 2DPackLib은 2차원 직교 빈 패킹의 표준 인스턴스를 제공한다. | — | A |
|
| 사용 방법분기 한정 (Branch and Bound) | 2D 빈 패킹의 정확 접근은 분기 한정(및 분기-가격) 정식화로 보고되어 왔다. | — | B |
|
| 사용 방법감소 우선 적합 (First-Fit Decreasing) | 감소 우선 적합(FFD) 계열의 구성적 휴리스틱이 빈 패킹의 빠른 근사해에 널리 쓰인다. | — | B |
|
| 사용 방법유전 알고리즘 (Genetic Algorithm) | 2D 빈 패킹은 유전 알고리즘 등 메타휴리스틱으로도 다뤄져 왔다. | — | B |
|
| 사용 방법정수 선형 계획법 (Integer Linear Programming) | 2D 빈 패킹은 정수 선형 계획(ILP) 모델로 정식화되며, 이는 분기 한정·분기-가격 같은 정확 해법의 출발점이다. | — | A |
|
| 사용 방법하한 (Lower Bounds) | 2D 빈 패킹의 정확 해법은 면적 하한과 Martello–Toth류 이산 하한 등 강한 하한으로 탐색을 가지친다. | — | A |
|
| 사용 방법열 생성 (Column Generation) | 2D 빈 패킹의 정확 접근은 열 생성/분기-가격으로 보고되어 왔다. | — | B |
|
| 사용 방법타부 서치 (Tabu Search) | 2D 빈 패킹은 타부 서치 기반 탐색으로도 보고되어 왔다. | — | B |
|
이웃 그래프
직접 연결된 그래프 이웃입니다. 깊이를 전환해 확장하세요.
노드를 클릭하면 열리고 · 엣지를 클릭하면 주장이 보입니다
함께 보기
직접 연결되어 있지 않지만, 공유하는 연결과 설명으로 보아 개념적으로 가까운 노드입니다.