Solution of “Hard” Knapsack Instances Using Quantum Inspired Evolutionary Algorithm

Solution of “Hard” Knapsack Instances Using Quantum Inspired Evolutionary Algorithm

C. Patvardhan (Department of Electrical Engineering, Dayalbagh Educational Institute, Agra, India), Sulabh Bansal (Department of Electrical Engineering, Dayalbagh Educational Institute, Agra, India) and Anand Srivastav (Institut für Informatik, Universität zu Kiel, Kiel, Germany)
Copyright: © 2014 |Pages: 17
DOI: 10.4018/ijaec.2014010104

Abstract

Knapsack Problem (KP) is a popular combinatorial optimization problem having application in many technical and economic areas. Several attempts have been made in past to solve the problem. Various exact and non-exact approaches exist to solve KP. Exact algorithms for KP are based on either branch and bound or dynamic programming technique. Heuristics exist which solve KP non-exactly in lesser time. Heuristic approaches do not provide any guarantee regarding the quality of solution whereas exact approaches have high worst case complexities. Quantum-inspired Evolutionary Algorithm (QEA) is a subclass of Evolutionary Algorithm, a naturally inspired population based search technique. QEA uses concepts of quantum computing. An engineered Quantum-inspired Evolutionary Algorithm (QEA-E), an improved version of QEA, is presented which quickly solves extremely large spanner problem instances (e.g. 290,000 items) that are very difficult for the state of the art exact algorithm as well as the original QEA.
Article Preview

Introduction

The 0/1 knapsack problem (KP) is a well known combinatorial optimization problem which occurs in several real world decision-making processes such as finding the least wasteful way to cut raw materials, selection of capital investments and financial portfolios etc. (Kellerer, et al., 2004)

KP in its most basic form is defined as follows: Given a set of n items with their profits pj and weights wj, jϵ{1,…,n}, the problem is to select a subset of items such that profit is maximized and weight doesn’t exceed the capacity C.

maximize: subject to:
(1)

Greedy approaches are also popular for solving optimization problems. Some heuristic is used in greedy algorithms to generate a sequence of sub-optimums in less time that hopefully yield results that are close to optimum. One such heuristic chooses the items with as high profit by weight ratio as possible(Kellerer, et al., 2004).

Several attempts have been made to provide algorithms for exact solution of KPs(Martello, et al., 2000). These algorithms are based on branch and bound technique or/and dynamic programming. Dynamic programming derives optimal solutions to specific type of optimization problems whose solutions satisfy the recurrence relations with overlapping sub-problems(Bellman, 1957). Pisinger (1997) presented an effective dynamic programming based pseudo polynomial algorithm named as minknap which is able to solve large size problems speedily (problems of size 10000 items within couple of minutes). Branch and bound techniques construct candidate solutions one component at a time and evaluate the partially constructed solutions. Relaxations and fathoming criteria are used to identify and to eliminate further expansion of partial solutions which would not lead to optimal solutions. The initial branch and bound algorithms for KP reported in 1970s are (Horowitz, et al., 1974; Fayard, et al., 1975; Nauss, 1976; Martello, et al., 1977). This approach makes it possible to solve some large instances of difficult combinatorial problems. However, in the worst case, the algorithms still have exponential complexity. Balas and Zemel (1980) provided an exact algorithm using core concept, combined with some heuristics and branch and bound technique. It is an effective and fast algorithm which solves problems having 10000 items in few seconds. Other effective algorithm based on core concept and branch and bound technique are presented in Fayard, et al. (1982), Plateau, et al. (1985), and Martello, et al. (1988). The refined core approach is presented in (Pisinger, 1995). Attempts have also been made to combine branch and bound techniques with dynamic programming approach to reduce storage and/or computational requirements. Martello et al. (1999) proposed an algorithm combining dynamic programming with tight bounds and core concept.

Pisinger (2005) presented some types of the hard KP instances which are difficult to solve and also described the way to generate them. A detailed comparison of various effective exact algorithms found in literature on various types of difficult knapsack problem instances is also presented. The most successful algorithm which solves KPs exactly is ‘Combo’(Martello, et al., 1999; Pisinger, 2005). This algorithm is a combination of many different concepts. Out of all the problem instances presented in Pisinger (2005), the spanner instances are shown as the most difficult, even for Combo, to solve. Combo is able to solve almost all the other KP problems fairly efficiently.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): 1 Released, 3 Forthcoming
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