This paper considers a generalized knapsack problem where the required sets of activities are not necessarily mutually exclusive. This problem appears in several applications including the capital budgeting problem, FMS production planning problem and database design problem. We formulate this problem as a nonlinear knapsack problem with polynomial objective function. After linearizing the nonlinear terms, we analyze the polyhedral structure of the convex hull of integral feasible solutions. Some classes of strong valid inequalities for this polytope are suggested. We show that these inequalities can define facets of the polytope under certain conditions. Additionally, we show that some subset of these inequalities is sufficient to cut off all the fractional vertices of the natural linear programming relaxation. Using these polyhedral results, we develop a strong cutting plane algorithm for the problem. The algorithm is tested on several sets of test problems. The computational result shows that this algorithm can be used to solve proatical problems in reasonable time. Moreover, this approach can be generalized to the cases where more than one type of resource constraints are needed.
본 논문은 일반화된 배낭문제의 해법을 다루고 있다. 일반화된 배낭문제는 각각의 프로젝트에 대한 필요자원의 집합이 교집합을 가질 수 있는 경우의 배낭문제가 된다. 즉, 한 가지 자원이 하나의 프로젝트에 고유한 것이 아니고, 여러 개의 프로젝트에 공통으로 작용할 수 있는 경우이다. 이 문제는 자본배분문제, 유연생산 시스템의 생산계획문제, 데이터베이스의 설계 등의 문제에 응용될 수 있다. 일반화된 배낭문제는 보통의 배낭문제와 달리 비선형의 목적함수를 가진다. 본 논문에서는 이와같은 비선형배낭문제를 0-1 정수계획법문제로 바꾸어 이 문제에 대한 절단평면 알고리듬을 제안하고 있다. 먼저 정수계획문제의 정수가능해들이 정의하는 볼록집합(convex hull)의 기본성질에 대하여 분석하고, 정수해들에 의해서는 만족되면서, 부분해들을 절단 할 수 있는 적법한 부등식들을 제안하였다. 또한, 이들 부등식들의 성질에 대해 규명하고, 이들의 유용성을 이론적으로 증명하였다. 위의 결과를 이용하여 절단평면 알고리듬을 개발하였고, 다양한 자료들에 대해 시험해 본 결과 이 알고리듬이 대형문제를 짧은 시간내에 효율적으로 해결할 수 있음이 증명되었다.
