This paper is concerned with an algorithm for the Generalized Covering Problem. This paper shows a procedure to yield a Generalized Covering Problem form a General 0-1 integer program and shows that a Generalized Covering Problem can be transformed to a Pure Set Covering Problem. This transformation allows us to use a Set Covering Problem algorithm for the computation of a Generalized Covering Problem.
The special structure of a Generalized Covering Problem permits us a rather efficient, yet simple solution procedure that is basically a Branch and Bound type algorithm coupled with linear programming and a suboptimization technique. The algorithm's originality stems from an efficient suboptimization procedure which heuristically constructs integer solutions from the solutions to the relaxed Linear Programming problem. Also, this algorithm uses Dual Simplex Algorithm to solve the nested sequence of Linear Programming problems. Finally, this paper shows that our algorithm could be used to solve the nested sequence of Generalized Set Covering Problems so as to solve a general 0-1 integer program.
본 연구의 목적은 일반적 포함문제 (Generalized Set Covering Problem)를 푸는 한가지 해법을 개발하는데 있다.
일반적 포함문제는 제약조건식의 계수들 중에 {-1}을 포함하고 있는것 외에는, 포함문제 (Set Covering Problem)와 같은 형태를 취하고 있다 포함문제에 대한 해법은 오래전 부터 많이 개발되어 왔다. 본 논문에서는, 먼저 일반적 포함문제가 포함문제의 형태로 바꿔질 수 있음을 증명하였다.
이러한 사실에 의하여, 우리는 포함문제를 푸는 여러 해법들 중에서 한 해법에 기초를 두어, 일반적 포함문제를 푸는 해법을 개발하였다.
본 논문의 해법은 기본적으로는 분단탐색형태 (Branch and Bound type) 의 해법이며, 선형계획문제 (Linear Programming Problem)를 푸는 한 해법과 이렇게 선형계획문제를 풀어서 나온 비정수해(nonintegral solution)에서부터 0-1 정수해를 구하는 하나의 탐색적해법(Heuristic Algorithm)으로 구성되어 있다.
그리고, 본 논문에 나오는 해법의 특징은 이외에도, 선형계획문제를 풀때, 매번 제약식이 추가되는 점을 고려하여 쌍대선형계획해법 (Dual Simplex method)을 사용하였다는 점을 들 수 있다.
실제계산결과, 다른 해법을 이용하여 일반적 포함문제를 풀때 보다, 본 논문의 해법을 이용하여 푸는 것이 많은 부분에 있어서 계산시간이 더 줄어드는 것으로 나타났다.
그리고, 일반적 포함문제는 일반적인 0-1 정수계획문제를 풀때 나타나기 때문에, 본 논문의 해법은 일반적인 0-1 정수계획문제를 풀기 위하여 더 개발 될 수도 있을 것이다.
