Branch and bound
분기한정법은 여러가지의 최적화 문제, 특히 이산 (discrete) 과 조합최적화 (combinatorial optimization) 에서 최적 해를 찾기위한 일반적인 방법이다. 그것은 암묵적인 열거 방법 (implicit enumeration method) 부류에 속한다. 분기한정법은 1960 년에 linear programming 을 위해 A. H. Land 와 A. G. Doig 가 An Automatic Method for Solving Discrete Programming Problems 에 처음 소개하였다.
분기한정법은 인수 x (가능영역 (feasible region) 이라고 불리움) 에 대해 함수 f(x) 의 최소값을 찾는것이라고 표현할수 있다. f 와 x 는 모두 임의의 값이다. 분기한정 과정은 두가지 tool 을 필요로 한다.
첫째는 여러개의 작은 feasible subregion (이상적으로 subregion 으로 나뉘는) 들이 feasible region 을 구성하는 방법이다. 이것은 분기 (branching) 라고 불리는데, 그 과정이 subregion 각각에 대해 재귀 반복 과정을 거치고, 만들어진 subregion 들이 자연스럽게 search tree 또는 branch-and-bound-tree 라고 불리는 tree 구조를 형성하기 때문이다. 그 노드들 각자가 subregion 이 되는 것이다.
두번째는 bounding 으로서, feasible subregion 내에서 최적해를 찾기위한 upper and low bound 를 빠르게 찾는 방법이다.
분기한정법의 핵심은, (작업을 최소화 하기 위해) 탐색트리에서 subregion A 의 lower bound 가 다른 이미 검사된 subregion B 의 upper bound 보다 크다면 A 를 탐색에서 폐기처분하는 간단한 방법이다. 이러한 단계를 절단 (pruning) 이라고 부른다. 절단은 검사된 모든 subregion 중에서 볼수있는 minimum upper bound 를 기록하는 전역변수 m 을 유지함으로써 구현된다. 즉 lower bound 가 m 보다 큰 어떠한 노드도 폐기처분 될수있다.
노드의 upper bound 가 lower bound 와 match 되고 그 값이 동등한 subregion 내에서 함수의 최소값 일수가 있다. 또 어떤 경우에는 그러한 최소값을 직접 찾는 방법도 있다. 이러한 두가지 경우를 그 노드가 해결 (solved) 된것이라고 말한다. 이러한 노드는 알고리즘이 진행되어 가면서 언제든 pruned 될수 있다는 것을 주목하라.
이상적으로는 분기한정법은 탐색트리의 모든 노드가 절단 (pruned) 되거나 해결 (solved) 되면 끝난다. 그러한 관점에서 모든 non-pruned subregions 은 함수의 전역 최소값과 같은 upper and lower bounds 를 가질것이다. 실제로 사용될때는 분기한정법은 주어진 시간이 지나면 종료된다. 그러한 관점에서 모든 non-pruned sections 중에서 minimum lower bound and the minimum upper bound 는 전역최소값 (global minimum) 을 포함하는 값의 범위로서 정의한다.
분기한정법의 효율성은 사용되는 branching and bounding algorithm 의 효과에 전적으로 의존한다. 즉 잘못 선택하면 subregions 이 매우 작아질 때 까지 어떤 pruning 도 없이 반복된 branching 만 할수도 있다. 그러한 경우에 분기한정법은 비현실적으로 큰 소모적인 열거 (exhaustive enumeration of the domain) 로 환원될 것이다. 모든 문제 해결을 위한 범용 bounding algorithm 은 존재하지 않으며 누군가 발견할 것이라고 희망할수도 없다. 그러므로 일반적인 패러다임은 각각의 응용을 위해 따로 구현될 필요가 있으며 branching and bounding algorithm 은 그 경우에 특별히 설계된다. 분기한정법은 bounding method 와 탐색트리 노드를 생성하고 검사하는 방법에 따라 분류될수 있다.
분기한정법은 자연히 병렬분산 (parallel and distributed) 의 구현, 예를들면 순회판매원 문제 (Travelling Salesman Problem) 같은 문제에 사용된다. 즉 많은 비결정 난해 (NP-hard) 문제를 위해 사용된다.
분기한정법은 다양한 휴리스틱의 기초가 될수있다 예를들면 upper and lower bounds 사이의 차이가 어떤 threshold 보다 작게되면 branching 을 멈추기를 원할수 있다. 이것은 그 해법이 "실제적인 목적을 위해서는 충분히 좋은 (good enough for practical purposes)" 때 사용되며 필요한 계산량을 크게 줄일수 있다. 이러한 종류의 해법은 특히 사용되는 cost function 이 noisy 하거나 통계적 추정 (statistical estimates) 의 결과 일때, 즉 정확하게 알수는 없지만 어떤 확률값의 범위내에 있다는 것을 알때에 사용된다. 알파베타 가지치기 (Alpha-Beta Pruning) 은 최소최대 (Mini-max) 문제를 위해 사용하는 것으로 분기한정의 특별한 버전이라고 할수있다. ............ (Wikipedia : Branch and bound)
term :
분기한정법 (Branch and bound) 최적화 (Optimization) 수학 (Mathematics) 경영과학 (Operation Research) 비결정 완전 (NP-complete) 비결정 난해 (NP-hard) 순회판매원 문제 (Travelling Salesman Problem) 배낭문제 (Knapsack problem) 휴리스틱 (Heuristic) 유전알고리즘 (Genetic Algorithm) 알파베타 가지치기 (Alpha-Beta Pruning) 최소최대 (Mini-max) 조합최적화 (Combinatorial Optimization)
site :
branch and bound : 전북대 박순철 교수님 동영상 (★★★)
알고리즘 강의 : 분기한정법 : 도경구
paper :
Unification of Kohonen Neural Network with the Branch-and-Bound Algorithm on Pattern Clustering : 박창목, 왕지남, 대한산업공학회, 1997