형식 문제
1D 절단 재고
재고 봉/롤을 주문 길이로 잘라 낭비 또는 사용 재고를 최소화하기.
다른 이름: 1D Cutting Stock · 절단 재고 문제 · 1D CSP · 트림 손실 문제
정의
고정 길이의 재고와, 필요한 더 짧은 길이별 수요가 주어졌을 때, 최소 개수의 재고로 수요를 충족하도록(즉 트림 손실 최소화) 절단 패턴을 선택한다.
예시
재고 길이 , 수요가 길이 6짜리 3개와 길이 4짜리 5개라고 하자. 패턴 “6+4”(길이 합 , 트림 0)를 세 번 쓰면 6짜리 3개와 4짜리 3개가 나오고, 남은 4짜리 2개는 패턴 “4+4”(길이 8, 트림 2) 한 번으로 충당한다. 합계 재고 4개, 총 트림 손실 2 — 6짜리는 한 재고에 하나뿐이라 최소 3개가 필요하고 남은 4짜리에 1개가 더 들기 때문에 이보다 적게는 불가능하다.
여기서 중요한 이유
이 문제는 열 생성의 본고장이다: 모든 절단 패턴을 열거하는 대신, Gilmore–Gomory 접근은 배낭 가격 산정 부분문제를 풀어 유망한 패턴을 필요할 때 생성한다. 같은 기법이 절단·적재 계열 전반에 다시 등장한다.
주장 & 증거
모든 관계는 증거 등급을 가진 하나의 주장이고, 문제 간 관계에는 해당되는 경우 등가 수준도 표시합니다. 증거 정책을 참고하세요.
| 관계 | 주장 | 등가 | 증거 | 출처 |
|---|---|---|---|---|
| 사용 방법열 생성 (Column Generation) | Gilmore & Gomory(1961)는 절단 재고 문제를 위한 열 생성(지연 패턴 생성) LP 접근을 도입했다. | — | A |
|
| 방법 공유2D 빈 패킹 | 1D 절단 재고와 빈 패킹은 같은 절단·적재 계열의 밀접한 구성원이며, 둘 다 패턴/구성 정식화로 다뤄진다. | E3 | B |
|
| 직접 벤치마크BPPLIB | BPPLIB은 빈 패킹과 절단 재고 문제의 인스턴스를 제공하는 직접 벤치마크다. | — | A |
|
| 사용 방법분기 한정 (Branch and Bound) | 절단 재고의 정수해는 열 생성과 분기 한정을 결합한 분기-가격으로 보고되어 왔다. | — | B |
|
| 사용 방법정수 선형 계획법 (Integer Linear Programming) | 1D 절단 재고는 패턴(절단 방식) 변수를 갖는 정수 선형 계획으로 정식화된다 — Gilmore–Gomory의 패턴 정식화가 그 기반이다. | — | A |
|