The 0-1 Multidimensional Knapsack Problem

This web page is intended to give some additional information as support to the abstract PaperId = 495

"Tabu Search for 0-1 Multidimensional Knapsack Revisited: 
Choosing Internal Heuristics and Fine Tuning of Parameters"

authored by M. Josep Blesa, Lluís Hernàndez and Fatos Xhafa 
submitted to YOR 12 Workshop

The 0-1 Multidimensional Knapsack problem  is a well-known NP-hard problem. It is a generalisation of the 0-1 simple knapsack problem. It is an important combinatorial optimization problem both from a theoretic and practical point of view. Its mathematical formulation (as an integer linear program) is as follows:
maximize cj· xj
subject toAi,j · x bi , for all i=1.. m,
                    xj  in  {0,1}, for all j=1..n
where cj represents the benefit of the item j, bi represents the ith capacity and Ai,jrepresent the entries of the constraint matrix.

Table of Contents:


[BX00a] Pseudo-code of Tabu Search Algorithm for the 0-1 Multidimensional Knapsack Problem.
Maria J. Blesa and Fatos Xhafa.
Working Document
[BX00b]  A C++ Implementation of a Skeleton for Tabu Search Method.
Maria J. Blesa and Fatos Xhafa.
Technical Report of the LSI Department (LSI-00-47-R).
Universitat Politecnica de Catalunya.
[BHX00] Parallel Skeletons for Tabu Search Method.
Maria J. Blesa, Lluís Hernàndez and Fatos Xhafa.
Technical Report of the LSI Department (LSI-00-81-R).
Universitat Politècnica de Catalunya.
[CB97]  A genetic algorithm for the Multidimensional Knapsack Problem. 
P.C. Chu and J.E. Beasley.
Working paper (1997).
[CT97]  Parallel Metaheuristics.
Teodor G. Crainic and Michel Toulouse.
[CT98]  A Hybrid Genetic Algorithm for the 0-1 Multiple Knapsack Problem.
Carlos Cotta and José Mª Troya.
Artificial Neural Nets and Genetic Algorithms 3
Springer-Verlag Wien New York 1998,  pp. 250-254
[CTG95]  Toward a Taxonomy of Parallel Tabu Search Heuristics.
Teodor G. Crainic, Michel Toulouse and Michel Gendreau.
[FP90] Hard 0-1 Multiknapsack Testproblems for Size Reduction Methods.
A. Freville and G. Plateau.
Investigacion Operativa, 1:251-270, 1990.
[GL93] Modern Heuristic Techniques for Combinatorial Problems.
F. Glover and M. Laguna.
Technical report, Blackwell, Oxford, 1993.
[GL94] The MPI Communication Library: its design and a portable implementation.
W. Gropp and E. Lusk.
In Proceedings of the Scalable Parallel Libraries Conference, october 6-8, 1993, Missisippi.
IEEE Computer Society Press.
[GL96] User's Guide for mpich, a Portable Implementation of MPI.
W. Gropp  and E. Lusk.
Mathematics and Computer Science Division, Argonne National Laboratory, 1996. ANL-96/6.
[GL97] Sowing MPICH: A Case Study in the Disemination of a Portable Environment for Parallel Scientific Computing.
W. Gropp and E. Lusk.
The International Journal of Supercomputer Applications and High Performance Computing, 11(2):103-114, 1997.
[GLDS96] A High-Performance, Portable Implementation of the MPI Message Passing Interface Standard.
W. Gropp, E. Lusk, N.Doss and A. Skjellum.
Parallel Computing, 22(6):789-828, september1996.
[Glo89] Tabu Search - Part I.
F. Glover.
ORSA Journal on Computing, 1:190-206, 1989.
[Glo90] Tabu Search - Part II.
F. Glover.
ORSA Journal on Computing, 2:4-32, 1990.
[HTW97] Tabu Search.
A. Hertz, E. Taillard and D. de Werra.
Local Search in Combinatorial Optimization. In E. Aarts and J.K. Lenstra editors, Wiley-Interscience Series in Discrete Mathematics and Optimization, chapter 5, pages 121-136. John Wilet & Sons Ltd, 1997.
[MT97] Knapsack Problems: Algorithms and Computer Implementation.
S. Martello and P. Toth.
Wiley & Sons, 1997.
[NF96] A Parallel Tabu Search Algorihm for the 0-1 Multidimensional Knapsack Problem.
Smaïl Niar and Arnaud Freville.
Technical report, Universite de Valenciennes, LIMAV, 1996.
International Parallel Processing Symposium (IPPS'97), 1997.
[NH97]  Une Resolution Parallele du Probleme du Sac a Dos Multidimensionnel Basee Sur la Recherche Tabou.
Smaïl Niar et Saïd Hanafi.
[Pil97]  Solving multiobjective knapsack problems using MOTS
Michael Pilegaard Hansen.
Conference paper (MIC'97).
[ST67] An approach to linear programming with 0-1 variables.
S. Senyu and Y. Toyada.
Management Science, 15:B196-B207, 1967.
[WN67] Methods for the resolution of the Multi-dimensional 0/1 Knapsack Problem.
H.M. Weingartner and D.N. Ness.
Operations Research, 15:83-103, 1967.