earticle

영어

This paper defines a multi-selection knapsack problem and presents an algorithm for seeking its optimal solution. Multi-selection means that all members of the particular group be selected or excluded. Our branch-and-bound algorithm introduces a simplex containing the feasible region of the original problem to exploit the fact that the most tightly underestimating function on the simplex is linear. In bounding operation, the subproblem defined over the candidate simplex is minimized. During the branching process the candidate simplex is splitted into two one-less dimensional subsimplices by being projected onto two hyperplanes. The approach of this paper can be applied to solving the global minimization problems under various types of the knapsack constraints.

한국어

본 연구에서는 다중 선택 배낭 모형의 최적해를 찾는 해법을 제시하고자 한다. 다중 선택은 동일한 집단에 소속된 구성원들이 동시에 선택되거나 동시에 배제되는 상황에서 관찰된다. 각 집단 간 관련성의 측정치인 오목 함수가 의사결 정기준으로 설정되었다. 다중 선택은 비선형 제약식으로 모형화 되는데 일반 배낭 제약식으로 변환될 수 있다. 따라서 최적 해법 개발을 위해 오목함수 최소화 문제와 배낭 문제의 일반적인 해법들에서 채택하고 있는 분지 한계 접근법을 이용하였다. 단체상에서 오목함수를 가장 근접하게 하한추정하는 함수가 1차식이라는 사실이 한계 전략의 이론적 토대 가 된다. 또한 하위 단계에서도 1차식 목적함수가 유일하게 결정되도록, 후보 단체를 두 개의 초평면에 투사시킴으로써 1차원 낮은 두 개의 하위 단체로 분할하는 방법이 분지 전략의 핵심이다. 앞으로 본 연구의 결과는 다양한 형태의 배낭 제약식 하에서의 오목 함수 최소화 문제의 해법을 개발하는데 응용될 수 있을 것이다.