1D 절단 재고

재고 봉/롤을 주문 길이로 잘라 낭비 또는 사용 재고를 최소화하기.

다른 이름: 1D Cutting Stock · 절단 재고 문제 · 1D CSP · 트림 손실 문제

정의

고정 길이의 재고와, 필요한 더 짧은 길이별 수요가 주어졌을 때, 최소 개수의 재고로 수요를 충족하도록(즉 트림 손실 최소화) 절단 패턴을 선택한다.

예시

재고 길이 $L = 10$ , 수요가 길이 6짜리 3개와 길이 4짜리 5개라고 하자. 패턴 “6+4”(길이 합 $6+4=10$ , 트림 0)를 세 번 쓰면 6짜리 3개와 4짜리 3개가 나오고, 남은 4짜리 2개는 패턴 “4+4”(길이 8, 트림 2) 한 번으로 충당한다. 합계 재고 4개, 총 트림 손실 2 — 6짜리는 한 재고에 하나뿐이라 최소 3개가 필요하고 남은 4짜리에 1개가 더 들기 때문에 이보다 적게는 불가능하다.

여기서 중요한 이유

이 문제는 열 생성의 본고장이다: 모든 절단 패턴을 열거하는 대신, Gilmore–Gomory 접근은 배낭 가격 산정 부분문제를 풀어 유망한 패턴을 필요할 때 생성한다. 같은 기법이 절단·적재 계열 전반에 다시 등장한다.

주장 & 증거

모든 관계는 증거 등급을 가진 하나의 주장이고, 문제 간 관계에는 해당되는 경우 등가 수준도 표시합니다. 증거 정책을 참고하세요.

A–X는 근거의 신뢰도, E0–E4는 문제 사이의 수학적 유사도입니다. 두 축은 서로 독립적입니다.

이 항목에서 나가는 관계 5

사용 방법
1D 절단 재고에서 열 생성 (Column Generation)로
Gilmore & Gomory(1961)는 절단 재고 문제를 위한 열 생성(지연 패턴 생성) LP 접근을 도입했다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem
  서지정보
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
방법 공유
1D 절단 재고에서 2D 빈 패킹로
1D 절단 재고와 빈 패킹은 같은 절단·적재 계열의 밀접한 구성원이며, 둘 다 패턴/구성 정식화로 다뤄진다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E3 · 구조적 유추
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
직접 벤치마크
1D 절단 재고에서 BPPLIB로
BPPLIB은 빈 패킹과 절단 재고 문제의 인스턴스를 제공하는 직접 벤치마크다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서BPPLIB: a library for bin packing and cutting stock problems
  서지정보
  Delorme, M., Iori, M., Martello, S. (2018). BPPLIB: a library for bin packing and cutting stock problems. Optimization Letters 12:235-250.
사용 방법
1D 절단 재고에서 분기 한정 (Branch and Bound)로
절단 재고의 정수해는 열 생성과 분기 한정을 결합한 분기-가격으로 보고되어 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서BPPLIB: a library for bin packing and cutting stock problems
  서지정보
  Delorme, M., Iori, M., Martello, S. (2018). BPPLIB: a library for bin packing and cutting stock problems. Optimization Letters 12:235-250.
사용 방법
1D 절단 재고에서 정수 선형 계획법 (Integer Linear Programming)로
1D 절단 재고는 패턴(절단 방식) 변수를 갖는 정수 선형 계획으로 정식화된다 — Gilmore–Gomory의 패턴 정식화가 그 기반이다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem
  서지정보
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.

이 항목에서 나가는 관계
관계	주장	증거	등가	출처
사용 방법 1D 절단 재고에서 열 생성 (Column Generation)로	Gilmore & Gomory(1961)는 절단 재고 문제를 위한 열 생성(지연 패턴 생성) LP 접근을 도입했다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem 서지정보 Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
방법 공유 1D 절단 재고에서 2D 빈 패킹로	1D 절단 재고와 빈 패킹은 같은 절단·적재 계열의 밀접한 구성원이며, 둘 다 패턴/구성 정식화로 다뤄진다.	B · 서베이 / 튜토리얼 / 커뮤니티	E3 · 구조적 유추	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
직접 벤치마크 1D 절단 재고에서 BPPLIB로	BPPLIB은 빈 패킹과 절단 재고 문제의 인스턴스를 제공하는 직접 벤치마크다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서BPPLIB: a library for bin packing and cutting stock problems 서지정보 Delorme, M., Iori, M., Martello, S. (2018). BPPLIB: a library for bin packing and cutting stock problems. Optimization Letters 12:235-250.
사용 방법 1D 절단 재고에서 분기 한정 (Branch and Bound)로	절단 재고의 정수해는 열 생성과 분기 한정을 결합한 분기-가격으로 보고되어 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서BPPLIB: a library for bin packing and cutting stock problems 서지정보 Delorme, M., Iori, M., Martello, S. (2018). BPPLIB: a library for bin packing and cutting stock problems. Optimization Letters 12:235-250.
사용 방법 1D 절단 재고에서 정수 선형 계획법 (Integer Linear Programming)로	1D 절단 재고는 패턴(절단 방식) 변수를 갖는 정수 선형 계획으로 정식화된다 — Gilmore–Gomory의 패턴 정식화가 그 기반이다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem 서지정보 Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.

이 항목으로 들어오는 관계 4

방법 공유
0/1 배낭 문제에서 1D 절단 재고로
절단 재고의 열 생성에서 가격 산정 부분문제가 (정수) 배낭 문제로 나타나, 두 문제는 방법론적으로 맞물린다.
증거A · 동료심사 논문 / 공식 문서
등가E3 · 구조적 유추
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem
  서지정보
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
방법 공유
가변 크기 빈 패킹 (Variable-Sized Bin Packing)에서 1D 절단 재고로
가변 크기 빈 패킹과 1D 절단 재고는 '여러 종류의 재고/빈을 비용 최소로 고른다'는 구조를 공유하며, 둘 다 패턴/구성 정식화로 다뤄진다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E3 · 구조적 유추
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
산업 사례
제지 롤 슬리팅에서 1D 절단 재고로
제지 롤 슬리팅은 1D 절단 재고의 산업적 사례이며, Gilmore–Gomory의 절단 재고 연구를 촉발한 실제 동기였다.
증거A · 동료심사 논문 / 공식 문서
등가E1 · 같은 기반, 다른 부가 제약
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem
  서지정보
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
언급
Wäscher 절단·적재 유형론 (Wäscher Typology)에서 1D 절단 재고로
유형론은 1D 절단 재고를 '입력 최소화' · 강하게 이질적인 소형 항목을 갖는 유형으로 분류한다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

이 항목으로 들어오는 관계
관계	주장	증거	등가	출처
방법 공유 0/1 배낭 문제에서 1D 절단 재고로	절단 재고의 열 생성에서 가격 산정 부분문제가 (정수) 배낭 문제로 나타나, 두 문제는 방법론적으로 맞물린다.	A · 동료심사 논문 / 공식 문서	E3 · 구조적 유추	출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem 서지정보 Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
방법 공유 가변 크기 빈 패킹 (Variable-Sized Bin Packing)에서 1D 절단 재고로	가변 크기 빈 패킹과 1D 절단 재고는 '여러 종류의 재고/빈을 비용 최소로 고른다'는 구조를 공유하며, 둘 다 패턴/구성 정식화로 다뤄진다.	B · 서베이 / 튜토리얼 / 커뮤니티	E3 · 구조적 유추	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
산업 사례 제지 롤 슬리팅에서 1D 절단 재고로	제지 롤 슬리팅은 1D 절단 재고의 산업적 사례이며, Gilmore–Gomory의 절단 재고 연구를 촉발한 실제 동기였다.	A · 동료심사 논문 / 공식 문서	E1 · 같은 기반, 다른 부가 제약	출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem 서지정보 Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
언급 Wäscher 절단·적재 유형론 (Wäscher Typology)에서 1D 절단 재고로	유형론은 1D 절단 재고를 '입력 최소화' · 강하게 이질적인 소형 항목을 갖는 유형으로 분류한다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.