- 일반 다중선택 다분할 선형계획 배낭문제
- ㆍ 저자명
- 원중연,Won. Joong-Yeon
- ㆍ 간행물명
- 대한산업공학회지
- ㆍ 권/호정보
- 2014년|40권 4호|pp.396-403 (8 pages)
- ㆍ 발행정보
- 대한산업공학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
The multi-divisional knapsack problem is defined as a binary knapsack problem where each mutually exclusive division has its own capacity. In this paper, we present an extension of the multi-divisional knapsack problem that has generalized multiple-choice constraints. We explore the linear programming relaxation (P) of this extended problem and identify some properties of problem (P). Then, we develop a transformation which converts the problem (P) into an LP knapsack problem and derive the optimal solutions of problem (P) from those of the converted LP knapsack problem. The solution procedures have a worst case computational complexity of order $O(n^2{log};n)$, where n is the total number of variables. We illustrate a numerical example and discuss some variations of problem (P).