열 생성 (Column Generation)

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