The Multiconstraint 0-1 Knapsack Problem(MCKP) is encountered when one has to decide how to make efficient use of an entity which consumes multiple resources. Unlike the single constraint version of this problem, the MCKP has been seldom addressed in spite of its wide applicability. In this study, the algorithm for the MCKP to optimality is discussed. Main emphasis is on the efficient problem reduction methods which fix as many variables as possible prior to the implicit enumeration phase with small computational burden. The computational results related to the each section are reported.
배낭문제는 경영과학, 경제학, 전산학등 여러분야에서 자주 발생하는 문제로서 그것의 효율적인 해법에 관한 연구가 꾸준히 되어왔다. 그러나 다수의 제약식을 갖는 보다 일반화된 배낭문제의 해법에 관한 연구는 아직까지는 미흡한 편이라하겠다.
본 연구에서는 다수의 제약식을 갖는 배낭문제의 해법을 제시하였다. 본 연구에 제시된 해법은, 배낭문제의 특성을 이용하여, 짧은 계산 시간내에 문제의 크기를 반복적으로 줄여가는데 그 초점을 맞추었다. 이 과정에서 다수의 제약식을 갖는 배낭문제의 휴리스틱 해를 구하는 보다 일반화된 방법을 제시하였다. 그리고 축소된 문제를 풀기위한 효율적인 분단 탐색법 (Branch and Bound Method)도 제시되었다. 한편 기존의 해법과의 비교를 포함한 계산 결과도 제시되었다.
