방법
열 생성 (Column Generation)
변수(열)를 필요할 때 생성해 거대한 LP를 푸는 기법.
다른 이름: Column Generation · 지연 열 생성 · 분기-가격(확장)
마지막 검증: 2026-05-27
변수가 엄청나게 많은 선형계획을 게으르게 생성하며 푸는 방법: 제한된 마스터를 풀고, 그 쌍대(dual)로 부분문제(흔히 배낭 문제)를 가격 산정해 개선 열을 추가하길 반복한다. Gilmore & Gomory의 1D 절단 재고 연구에서 비롯되었고, 정수해를 위한 분기-가격(branch-and-price)으로 확장된다.
주장 & 증거
모든 관계는 등가 수준과 증거 등급을 가진 하나의 주장입니다. 증거 정책을 참고하세요.
| 관계 | 주장 | 등가 | 증거 | 출처 |
|---|---|---|---|---|
| 방법 공유분기 한정 (Branch and Bound) | 열 생성과 분기 한정을 결합하면 분기-가격(branch-and-price)이 되어, 정수 절단·적재 문제의 정확해에 쓰인다. | E2 | A |
|
이웃 그래프
직접 연결된 그래프 이웃입니다. 깊이를 전환해 확장하세요.
노드를 클릭하면 열리고 · 엣지를 클릭하면 주장이 보입니다
함께 보기
직접 연결되어 있지 않지만, 공유하는 연결과 설명으로 보아 개념적으로 가까운 노드입니다.