@article{ART002419052},
author={Junha Hwang},
title={An Integer Programming-based Local Search for the Multiple-choice Multidimensional Knapsack Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2018},
volume={23},
number={12},
pages={1-9},
doi={10.9708/jksci.2018.23.12.001}
TY - JOUR
AU - Junha Hwang
TI - An Integer Programming-based Local Search for the Multiple-choice Multidimensional Knapsack Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2018
VL - 23
IS - 12
PB - The Korean Society Of Computer And Information
SP - 1
EP - 9
SN - 1598-849X
AB - 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.
KW - Multiple-choice Multidimensional Knapsack Problem;Integer Programming;Local Search;Linear Programming
DO - 10.9708/jksci.2018.23.12.001
ER -
Junha Hwang. (2018). An Integer Programming-based Local Search for the Multiple-choice Multidimensional Knapsack Problem. Journal of The Korea Society of Computer and Information, 23(12), 1-9.
Junha Hwang. 2018, "An Integer Programming-based Local Search for the Multiple-choice Multidimensional Knapsack Problem", Journal of The Korea Society of Computer and Information, vol.23, no.12 pp.1-9. Available from: doi:10.9708/jksci.2018.23.12.001
Junha Hwang "An Integer Programming-based Local Search for the Multiple-choice Multidimensional Knapsack Problem" Journal of The Korea Society of Computer and Information 23.12 pp.1-9 (2018) : 1.
Junha Hwang. An Integer Programming-based Local Search for the Multiple-choice Multidimensional Knapsack Problem. 2018; 23(12), 1-9. Available from: doi:10.9708/jksci.2018.23.12.001
Junha Hwang. "An Integer Programming-based Local Search for the Multiple-choice Multidimensional Knapsack Problem" Journal of The Korea Society of Computer and Information 23, no.12 (2018) : 1-9.doi: 10.9708/jksci.2018.23.12.001
Junha Hwang. An Integer Programming-based Local Search for the Multiple-choice Multidimensional Knapsack Problem. Journal of The Korea Society of Computer and Information, 23(12), 1-9. doi: 10.9708/jksci.2018.23.12.001
Junha Hwang. An Integer Programming-based Local Search for the Multiple-choice Multidimensional Knapsack Problem. Journal of The Korea Society of Computer and Information. 2018; 23(12) 1-9. doi: 10.9708/jksci.2018.23.12.001
Junha Hwang. An Integer Programming-based Local Search for the Multiple-choice Multidimensional Knapsack Problem. 2018; 23(12), 1-9. Available from: doi:10.9708/jksci.2018.23.12.001
Junha Hwang. "An Integer Programming-based Local Search for the Multiple-choice Multidimensional Knapsack Problem" Journal of The Korea Society of Computer and Information 23, no.12 (2018) : 1-9.doi: 10.9708/jksci.2018.23.12.001
