열 생성 (Column Generation)

변수(열)를 필요할 때 생성해 거대한 LP를 푸는 기법.

다른 이름: Column Generation · 지연 열 생성 · 분기-가격(확장)

변수가 엄청나게 많은 선형계획을 게으르게 생성하며 푸는 방법: 제한된 마스터를 풀고, 그 쌍대(dual)로 부분문제(흔히 배낭 문제)를 가격 산정해 개선 열을 추가하길 반복한다. Gilmore & Gomory의 1D 절단 재고 연구에서 비롯되었고, 정수해를 위한 분기-가격(branch-and-price)으로 확장된다.

주장 & 증거

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

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

이 항목에서 나가는 관계 1

방법 공유
열 생성 (Column Generation)에서 분기 한정 (Branch and Bound)로
열 생성과 분기 한정을 결합하면 분기-가격(branch-and-price)이 되어, 정수 절단·적재 문제의 정확해에 쓰인다.
증거A · 동료심사 논문 / 공식 문서
등가E2 · 방법론 공유
출처
- 출처 등급: 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.
- 출처 등급: A — 동료심사 논문 / 공식 문서Branch-and-Price: Column Generation for Solving Huge Integer Programs
  서지정보
  Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., Vance, P.H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research 46(3):316-329. Formalizes combining column generation with branch-and-bound (branch-and-price).

이 항목에서 나가는 관계
관계	주장	증거	등가	출처
방법 공유 열 생성 (Column Generation)에서 분기 한정 (Branch and Bound)로	열 생성과 분기 한정을 결합하면 분기-가격(branch-and-price)이 되어, 정수 절단·적재 문제의 정확해에 쓰인다.	A · 동료심사 논문 / 공식 문서	E2 · 방법론 공유	출처 등급: 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. 출처 등급: A — 동료심사 논문 / 공식 문서Branch-and-Price: Column Generation for Solving Huge Integer Programs 서지정보 Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., Vance, P.H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research 46(3):316-329. Formalizes combining column generation with branch-and-bound (branch-and-price).

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

사용 방법
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.
사용 방법
2D 빈 패킹에서 열 생성 (Column Generation)로
2D 빈 패킹의 정확 접근은 열 생성/분기-가격으로 보고되어 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem
  서지정보
  Pisinger, D., Sigurd, M. (2007). Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem. INFORMS Journal on Computing 19(1):36-51. A Dantzig-Wolfe / branch-and-price-and-cut exact method for 2D bin packing.
사용 방법
길로틴 절단에서 열 생성 (Column Generation)로
Gilmore & Gomory는 2차원 길로틴 절단 재고를 위해 열 생성/패턴 생성 접근을 확장했다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Multistage Cutting Stock Problems of Two and More Dimensions
  서지정보
  Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.

이 항목으로 들어오는 관계
관계	주장	증거	등가	출처
사용 방법 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.
사용 방법 2D 빈 패킹에서 열 생성 (Column Generation)로	2D 빈 패킹의 정확 접근은 열 생성/분기-가격으로 보고되어 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem 서지정보 Pisinger, D., Sigurd, M. (2007). Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem. INFORMS Journal on Computing 19(1):36-51. A Dantzig-Wolfe / branch-and-price-and-cut exact method for 2D bin packing.
사용 방법 길로틴 절단에서 열 생성 (Column Generation)로	Gilmore & Gomory는 2차원 길로틴 절단 재고를 위해 열 생성/패턴 생성 접근을 확장했다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Multistage Cutting Stock Problems of Two and More Dimensions 서지정보 Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.