본문 바로가기
  • Home

An Integer Programming-based Local Search for the Multiple-choice Multidimensional Knapsack Problem

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2018, 23(12), pp.1-9
  • DOI : 10.9708/jksci.2018.23.12.001
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science
  • Received : September 17, 2018
  • Accepted : November 12, 2018
  • Published : December 31, 2018

Junha Hwang ORD ID 1

1금오공과대학교

Accredited

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.

Citation status

* References for papers published after 2022 are currently being built.