Multiple-choice Knapsack Problem


In my new job at University of Cantabria, where I work on a FP7 European research called MULTICUBE, whose objective is to build an innovative design space exploration (DSE) tool for MpSoCs, I’ve found out an unexpected application of genetic algorithms.

When you co-design a hardware/software application on a MpSoC architecture you must chose a suitable architecture (doing an architecture exploration by tuning parameters of the afore mentioned architecture in order to optimize power, performance, area, etc) and then you must map the functionality implemented by the application software optimally (run-time exploration) over the different hardware resources (e.g. microprocessor cores) in order to fully use all the resources available within the constraints imposed by the application.

The process of mapping optimally could be seen as a classical Knapsack Problem (see a Google Search on the subject), which is a problem in combinatorial optimization. The thing is, that instead of 0-1-knapsack problem, we’ve got a Multiple-choice Knapsack Problem (MMKP), that is one of the list of knapsack problems with n items (e.g. application tasks) and m knapsacks (e.g. hardware resources) with capacities Wi.

There are several approximations to the solution of the (NP-Complete) problem including greedy ones, dynamic programming ones, heuristic ones, etc. But the ones that I’m interested in are the evolutionary computation approaches. It’s not easy to find open access to papers which present such solution approaches. I’ve found out a paper who explains a heuristic approach (convex hull) with the quality of service (QoS) management problem of the Multiple Resource Multiple Dimension (MRMD) systems example.

Solving the Multidimensional Multiple-choice Knapsack Problem by constructing convex hulls
Md Mostofa Akbar (a),(b), M. Sohel Rahman (b), M. Kaykobad (b), E.G. Manning (a), G.C. Shoja (a)

(a) Department of CSC, PANDA Lab, University of Victoria, Victoria, BC, Canada, USA
(b) Department of CSE, BUET, Dhaka, Bangladesh

In the paper the authors state that:

Various other techniques like tabu search [14], simulated annealing [15] and genetic algorithms [16] can also be applied to solve the variants of Knapsack Problem. The genetic algorithm has the exponential worst-case complexity—it can explore all the items. Tabu search and simulated annealing are based on looking at the neighbours. These are costlier than the greedy approach used in HEU (heuristic). HEU uses a two-way interchange approach and searches candidates in the neighbourhood which yield better revenue, and changes one selection to another. But in tabu search, simulated annealing and genetic algorithm approach, current solution is moved to another solution by upgrading some and downgrading some. This upgrade and downgrade at the same step requires more time because we have to search all neighbouring combinations of current solution. In the next section, we present our main contribution by presenting a new heuristic to solve MMKP by constructing convex hulls.

The references aforementioned are:

[14] Dammeyer F,Voss S. Dynamic tabu list management using the reverse elimination method.Annals of Operations Research 1991.

[15] Drexel A. A simulated annealing approach to the multiconstraint zero-one knapsack problem. Annals of Computing 1988;40:1–8.

[16] Khuri S, Back T, Heitkotter J. The zero/one multiple knapsack problem and genetic algorithms. ACM Symposium of applied computation; 1994.

So it seems this time genetic algorithms are not the best option at hand to solve the problem … :)

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s