In integer programming the fact that branch-and-bound method which is the one of the most general method has the restriction on the capacity of memory is its limitation. To overcome this limitation we apply the Artifitial Intelligence (AI) search technique to integer programming problem. By applying $A^{\ast}$ algorithm which is the one of AI search techniques to branch-and-bound method, we try to combine OR and AI.
Containing heuristic value which is a nonnegative estimate of the optimal value of the subproblem makes the solution procedure efficient. That is, h-value plays a role in finding an optimal solution and preventing needless branching. Especially when heuristic function guarantees to obtain its lower bound, we cannot fail to obtain an optimal solution. We adopt Lagrangean relaxation among various relaxations as heuristic function and by using Lagrangean multipliers we can generate a good surrogate constraint. This surrogate constraint generates minimal cover and extendible set and both make our proposed algorithm efficient in separation too. Computational results are reported.
정수 계획법의 해법 중에는 널리 이용 되고 있는 방법 중의 하나로서 branch-and-bound method 가 있으나 많은 기억 용량의 요구로 그 효율성의 감소 문제가 한계점으로 대두되게 되었다. 이러한 어려움을 극복하고자 인공지능에서 많이 연구된 탐색 기법(Search Technique)을 응용한 해법의 개발을 시도하였다. 즉, 0-1 정수 계획법에 있어서의 branch-and-bound method 에 인공지능의 한 탐색 기법인 $A^{\ast}$ algorithm 을 도입함으로써 OR 과 AI 의 접목을 시도하였다.
비용 최소화 문제의 경우 branch 되는 각 node 들의 측정 value 에 heuristic value를 포함시켜, 종래 OR 에서 배제되어 왔던 예상 비용의 개념을 가시화함으로써 최적해 도출의 과정을 효율적으로 개선시킬 수 있었다. 특히 heuristic value 를 제공하는 함수가 lower bound를 항상 만족시키는 경우에는 최적해를 정확히 구할 수 있기 때문에 본 논문에서는 Lagrangean relaxation 을 이용하였으며 Lagrangean 승수로부터 도출된 General Covering constraint 와 Minimal cover를 사용함으로써 separation에 있어서도 효율성을 도모하였다.
