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

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 p_j and weights w_j, 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.

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.