경영의사결정론) 혼합 정수계획법(Mixed Integer Programming)의 해법 중에 분단탐색법(Branch and Bound) 알고리즘에 대해 설명하시오.

1. 분단탐색법 개요

분단탐색법(Branch and Bound)은 혼합 정수계획법(Mixed Integer Programming, MIP) 문제를 해결하는 데 사용되는 효율적인 알고리즘이다. 이 방법은 문제의 해공간을 체계적으로 분할하여 최적해를 찾는 전략으로, 큰 규모의 정수 계획 문제를 해결하는 데 매우 적합하다. 분단탐색법은 먼저 전체 해공간을 하나의 큰 문제로 간주하고, 이 문제에 대한 최적해 또는 하한값(Lower Bound)을 계산한다. 이후 해결 가능한 해를 찾기 위해 문제를 작은 하위 문제들로 분할하는 과정을 반복한다. 이때 각 하위 문제는 고정된 변수의 값에 따라 부분적인 제약조건이 추가된 형식이며, 이 과정을 `분기(branching)`라고 부른다. 분기 단계에서 나온 하위 문제들의 해를 각각 평가하여 가능한 해 중 최적해를 갱신해 나가며, 동시에 하한값과 상한값(Upper Bound)을 계산한다. 상한값은 현재까지 찾은 최적해의 값을 의미하며, 하한값은 하위 문제에서 가능한 최저 비용 또는 목적값을 나타낸다. 만약 하한값이 상한값보다 커지면, 해당 하위 문제는 더 이상 해를 찾을 필요가 없음을 의미하여 가지치기(pruning)가 수행된다. 이 과정을 반복하면서 해공간이 점…