An Improved Generalized Quantum-Inspired Evolutionary Algorithm for Multiple Knapsack Problem

An Improved Generalized Quantum-Inspired Evolutionary Algorithm for Multiple Knapsack Problem

Sulabh Bansal (School of Computing and Information Technology, Manipal University Jaipur, Jaipur, India) and C. Patvardhan (Faculty of Engineering, Dayalbagh Educational Institute (DEI), Agra, India)
Copyright: © 2018 |Pages: 35
DOI: 10.4018/IJAEC.2018010102

Abstract

This article describes how the 0/1 Multiple Knapsack Problem (MKP), a generalization of popular 0/1 Knapsack Problem, is NP-hard and harder than simple Knapsack Problem. Solution of MKP involves two levels of choice – one for selecting an item to be placed and the other for selecting the knapsack in which it is to be placed. Quantum Inspired Evolutionary Algorithms (QIEAs), a subclass of Evolutionary algorithms, have been shown to be effective in solving difficult problems particularly NP-hard combinatorial optimization problems. QIEAs provide a general framework which needs to be customized according to the requirements of a given problem to obtain good solutions in reasonable time. An existing QIEA for MKP (QIEA-MKP) is based on the representation where a Q-bit collapse into a binary number. But decimal numbers are required to identify the knapsack where an item is placed. The implementation based on such representation suffers from overhead of frequent conversion from binary numbers to decimal numbers and vice versa. The generalized QIEA (GQIEA) is based on a representation where a Q-bit can collapse into an integer and thus no inter conversion between binary and decimal is required. A set of carefully selected features have been incorporated in proposed GQIEA-MKP to obtain better solutions in lesser time. Comparison with QIEA-MKP shows that GQIEA-MKP outperforms it in providing better solutions in lesser time for large sized MKPs. The generalization proposed can be used with advantage in other Combinatorial Optimization problems with integer strings as solutions.
Article Preview
Top

1. Introduction

0-1 Multiple Knapsack Problem (MKP) is a generalization of the standard 0-1 Knapsack Problem (KP) where multiple knapsacks are required to be filled instead of one.

Given a set of n items with their profits pj and weights wj, IJAEC.2018010102.m01. and m knapsacks with capacities ci,IJAEC.2018010102.m02. the MKP is to select a subset of items to fill given m knapsacks such that the total profit is maximized and sum of weights in each knapsack i doesn’t exceed its capacity ci.

maximize: IJAEC.2018010102.m03(1) subject to: IJAEC.2018010102.m04(2)
IJAEC.2018010102.m05
(3)
IJAEC.2018010102.m06
(4)

where IJAEC.2018010102.m07.= 1 if item j is assigned to knapsack i, IJAEC.2018010102.m08.= 0 otherwise and coefficients pj, wj and ci are positive integers.

In order to avoid any trivial case, the following assumptions are made

  • 1.

    Every item has a chance to be placed at least in largest knapsack:

    IJAEC.2018010102.m09
    (5)

  • 2.

    The smallest knapsack can be filled at least by the smallest item:

    IJAEC.2018010102.m10
    (6)

  • 3.

    There is no knapsack which can be filled with all N items:

    IJAEC.2018010102.m11
    (7)

The subset sum variant of MKP having IJAEC.2018010102.m12 is known as Multiple Subset Sum Problem (MSSP).

The MKP have several applications. An application is seen when scheduling jobs on processors where some machines are unavailable for a fixed duration or some high priority jobs are pre-assigned to processors (Diedrich & Jansen, 2009). A real-world application of MKP is the problem of cargo loading where some containers need to be chosen from a set of n containers to be loaded in m vessels with different loading capacities for the shipment of the containers (Eilon & Christofides, 1971). Another real-world problem for MSSP is mentioned in (Kellerer, Pferschy, & Pisinger, 2004, p. 287) from a company producing objects of marble.

The MKP problem is strongly NP-complete. Some approximation algorithms exist for MKP. Kellerer (Kellerer H., 1999) presented a Polynomial Time Approximation Scheme for MKP with identical capacities. Chekuri & Khanna (Chekuri & Khanna, 2006) generalized it and presented the PTAS for MKP. However, no Fully Polynomial Time Approximation Scheme is possible for MKP (Chekuri & Khanna, 2006).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): 2 Released, 2 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing