일반 다중선택 다분할 선형계획 배낭문제

다국어 초록 (Multilingual Abstract)

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² logn), where n is the total number of variables. We illustrate a numerical example and discuss some variations of problem (P).

참고문헌 (Reference)

1 원중연, "일반화된 일반상한제약을 갖는 이차원 선형계획 배낭문제 연구" 대한산업공학회 37 (37): 258-263, 2011

2 서정대, "세부공정으로 구성된 LCD 모듈 라인의 다중스테이지 메타휴리스틱 스케줄링 알고리즘 연구" 대한산업공학회 38 (38): 262-275, 2012

3 심승배, "군 통합 물류센터의 최적 위치 결정" 대한산업공학회 39 (39): 587-598, 2013

4 Armstrong, R. D., "The multiplechoice nested knapsack model" 28 (28): 34-43, 1982

5 Won, J. Y., "The multi-divisional linear knapsack problem" 17 (17): 127-130, 1991

6 Dudzinski, K., "On a cardinality constrained linear programming knapsack problem" 8 : 215-218, 1989

7 Campello, R. E., "Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints :properties and algorithms" 18 : 119-136, 1987

8 Balas, E., "An algorithm for large zero-one knapsack problem" 28 (28): 1130-1154, 1980