분지한정법 (Branch and Bound Method)
쉽게 풀면
모든 경우의 수를 하나하나 다 확인하려면 시간이 너무 오래 걸리는 문제가 있습니다. 분지한정법은 이런 문제를 풀 때, 전체 경우의 수를 몇 개의 그룹으로 나눈 다음 각 그룹에서 얻을 수 있는 최선의 결과가 어느 정도인지를 먼저 가늠해봅니다. 만약 어떤 그룹에서 아무리 잘해도 지금까지 찾은 최선의 답보다 못하다는 것이 확인되면, 그 그룹은 더 이상 살펴볼 필요 없이 통째로 포기합니다. 이렇게 가능성 없는 경우들을 미리 걸러내면서 탐색 범위를 좁혀나가면, 모든 경우를 다 확인하지 않고도 최적해를 찾을 수 있습니다.
왜 중요한가
생산 계획, 시설 입지 선정, 일정 계획처럼 변수가 정수 값만 가질 수 있는 정수계획법 문제는 모든 경우를 다 따지면 계산량이 폭발적으로 늘어납니다. 분지한정법은 이런 문제에서 탐색 범위를 체계적으로 줄여 실용적인 시간 안에 최적해 또는 최적에 가까운 해를 찾을 수 있게 해주기 때문에 산업공학의 최적화 논문에서 핵심적인 해법으로 다뤄집니다.
논문에서는 이렇게 쓰입니다
여러 후보지 중 어디에 시설을 설치해야 하는지를 정수계획 문제로 만들고, 탐색 범위를 좁혀가며 최적의 조합을 찾았다는 의미입니다.
변수가 많은 복잡한 일정 계획 문제도 분지한정법을 통해 실용적인 시간 안에 풀 수 있었다는 뜻입니다.
조금 더 깊게 보면
분지한정법은 해공간을 나누는 분지 단계와, 각 부분 문제의 완화된 형태를 풀어 상한 또는 하한 값을 구하는 한정 단계를 반복하는 구조로 이루어집니다. 이때 정수 제약을 잠시 무시하고 연속 변수로 완화한 문제를 먼저 풀어 한계값을 구하는 방식이 흔히 쓰이며, 이 한계값이 지금까지 찾은 최선의 해보다 나쁘면 해당 가지는 더 탐색하지 않고 가지치기합니다.
주의할 점
문제 규모가 매우 크거나 완화 문제의 한계값이 실제 최적값과 차이가 크면 가지치기 효과가 떨어져 탐색 시간이 크게 늘어날 수 있습니다. 따라서 실무에서는 분지 순서나 완화 방식을 문제 특성에 맞게 조정하는 것이 중요합니다.