다선택 다차원 배낭 문제를 위한 정수 계획법 기반 지역 탐색
An Integer Programming-based Local Search for the Multiple-choice Multidimensional Knapsack Problem
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
The multiple-choice multidimensional knapsack problem (MMKP) is a variant of the well known 0-1 knapsack problem, which is known as an NP-hard problem. This paper proposes a method for solving the MMKP using the integer programming-based local search (IPbLS). IPbLS is a kind of a local search and uses integer programming to generate a neighbor solution. The most important thing in IPbLS is the way to select items participating in the next integer programming step. In this paper, three ways to select items are introduced and compared on 37 well-known benchmark data instances. Experimental results shows that the method using linear programming is the best for the MMKP. It also shows that the proposed method can find the equal or better solutions than the best known solutions in 23 data instances, and the new better solutions in 13 instances.
Abstract
The multiple-choice multidimensional knapsack problem (MMKP) is a variant of the well known 0-1 knapsack problem, which is known as an NP-hard problem. This paper proposes a method for solving the MMKP using the integer programming-based local search (IPbLS). IPbLS is a kind of a local search and uses integer programming to generate a neighbor solution. The most important thing in IPbLS is the way to select items participating in the next integer programming step. In this paper, three ways to select items are introduced and compared on 37 well-known benchmark data instances. Experimental results shows that the method using linear programming is the best for the MMKP. It also shows that the proposed method can find the equal or better solutions than the best known solutions in 23 data instances, and the new better solutions in 13 instances.
참고문헌 (13)
- M. Hifi, "Heuristic Algorithms for the Multiple-choice Multidimensional Knapsack Problem", Journal of the Operational Research Society, 55, pp.1323~1332 (2004)
- M. Caserta, "An Exact Algorithm for the Reliability Redundancy Allocation Problem", European Journal of Operational Research, 244(1), pp.110~116 (2015)
- D. Pisinger, "Budgeting with Bounded Multiple-choice Constraints", European Journal of Operational Research, 129(3), pp.471~480 (2001)
- C. Basnet, "Heuristics for Determining the Number of Warehouses for Storing Non-compatible Products", International Transactions in Operational Research, 12(5), pp.527~538 (2005)
- S. Khan, "Solving the Knapsack Problem for Adaptive Multimedia Systems", Studia Informatica Universalis, 2(1), pp.157~178 (2002)
- M. Hifi, "A Reactive Local Search-based Algorithm for the Multiple-choice Multi-dimensional Knapsack Problem", Computational Optimization and Applications, 33(2-3), pp.271~285 (2006)
- H. Shojaei, "A Fast and Scalable Multidimensional Multiple-choice Knapsack Heuristic", ACM Transactions on Design Automation of Electronic Systems, 18(4), pp.1~32 (2013)
- Y. Chen, "A Reduce and Solve Approach for the Multiple-choice Multidimensional Knapsack Problem", European Journal of Operational Research, 239(2), pp.313~322 (2014)
- C. Gao, "An Iterative Pseudo-gap Enumeration Approach for the Multidimensional Multiple-choice Knapsack Problem", European Journal of Operational Research, 260(1), pp.1~11 (2017)
- K. Genova, "Linear Integer Programming Methods and Approaches–A Survey", Cybernetics and Information Technologies, 11(1), pp.3~25 (2011)
- 황준하, "집합 커버링 문제를 위한 정수계획법 기반 지역 탐색", 한국컴퓨터정보학회논문지, 19(10), pp.13~21 (2014), 한국컴퓨터정보학회
- 황준하, "다차원 배낭 문제를 위한 정수계획법 기반 지역 탐색 기법", 한국컴퓨터정보학회논문지, 17(6), pp.13~27 (2012), 한국컴퓨터정보학회[DOI]
- "IBM Decision Optimization CPLEX Modeling for Python V2.7" (2018), IBM Corporation