분지가격법 (Branch and Price)
한 줄 정의: 분지한정법의 각 노드에서 열생성으로 LP 완화를 푸는 대규모 정수계획 해법입니다.
쉽게 풀면
변수가 너무 많아서 한꺼번에 적어 놓을 수조차 없는 정수계획 문제가 있습니다. 분지가격법은 필요한 변수(열)만 조금씩 만들어 가며 완화문제를 풀고, 해가 정수가 아니면 문제를 나누어(분지) 같은 과정을 반복합니다. 즉 분지한정법과 열생성법을 결합한 방법입니다.
왜 중요한가
승무원 스케줄링, 차량경로, 절단재고 문제처럼 경로나 패턴 단위로 모형화하는 대형 문제에서 최적해를 구하는 대표 방법입니다. 최신 운영연구 논문에서 정확해법(exact method)으로 자주 제시됩니다.
논문에서는 이렇게 쓰입니다
"시간창이 있는 차량경로문제를 집합분할 모형으로 정식화하고 분지가격법으로 최적해를 구하였다."
경로 하나하나를 변수로 두고, 유망한 경로만 생성하면서 분지해 최적해를 찾았다는 뜻입니다.
조금 더 깊게 보면
각 노드에서는 일부 열만 가진 제한 주문제를 풀고, 그 쌍대가격으로 가격결정(pricing) 부분문제를 풀어 감소비용이 음수(최소화 기준)인 새 열을 찾습니다. 차량경로에서는 이 부분문제가 자원제약 최단경로문제가 되는 경우가 많습니다. 주문제 변수에 그대로 분지하면 부분문제 구조가 깨질 수 있어, 원래 변수나 두 고객의 연속 방문 여부 같은 구조 기반 분지 규칙을 설계하는 것이 핵심입니다. 절단평면까지 함께 쓰면 분지가격절단법(branch-price-and-cut)이라 부릅니다.
주의할 점
분지절단법은 노드에서 제약(행)을 추가하는 반면, 분지가격법은 변수(열)를 추가한다는 점이 다릅니다. 열생성이 끝나기 전의 목적함수 값은 유효한 하한이 아니므로, 이를 가지치기에 쓰려면 라그랑지 한계 같은 별도 계산이 필요합니다.