집합분할문제 (Set Partitioning Problem)
한 줄 정의: 각 원소가 선택된 부분집합들 중 정확히 하나에만 포함되도록 최소 비용으로 고르는 정수계획 문제입니다.
쉽게 풀면
비행편마다 승무원 조를 정확히 한 팀씩 배정해야 한다고 해 봅시다. 가능한 근무 일정 묶음이 아주 많을 때, 모든 비행편이 빠짐없이, 그리고 겹치지 않게 한 번씩만 덮이도록 가장 싼 묶음 조합을 고르는 문제가 집합분할문제입니다.
왜 중요한가
승무원 스케줄링, 차량경로, 배송 계획처럼 '정확히 한 번'이 요구되는 문제를 깔끔하게 정식화하는 표준 틀입니다. 열생성법·분지가격법과 결합한 대규모 최적화 논문에서 주 문제(master problem)로 자주 쓰입니다.
논문에서는 이렇게 쓰입니다
"승무원 페어링 문제를 집합분할문제로 정식화하고, 가격결정 하위문제로 페어링 후보를 생성하는 분지가격법으로 풀었다."
집합분할 정식화와 열생성의 전형적 결합입니다.
조금 더 깊게 보면
원소 i가 부분집합 j에 포함되면 a_ij=1이라 할 때, 모든 i에 대해 Σ_j a_ij x_j = 1, x_j ∈ {0,1} 조건에서 Σ c_j x_j를 최소화합니다. 등식 제약 때문에 가능해가 아예 없을 수도 있으며, 일반적으로 NP-난해 문제입니다. 부분집합(열) 수가 폭발적으로 많아 열생성으로 필요한 열만 만들어 가며 LP 완화를 푸는 방식이 흔합니다. 실무에서는 한 원소가 두 번 덮여도 큰 문제가 없으면(예: 승무원의 편승 이동) 등식을 ≥로 바꾼 집합피복 정식화를 쓰기도 합니다.
주의할 점
'집합피복' 계열 문제는 각 원소를 '1개 이상' 덮으면 되지만, 집합분할은 '정확히 1개'를 요구하는 등식 제약이라는 점이 다릅니다. 두 정식화는 가능해 존재 여부와 LP 완화의 성질이 다르므로 혼용하면 안 됩니다.