CMU Artificial Intelligence Repository
SAC94 Suite: Collection of Multiple Knapsack Problems
areas/genetic/ga/test/sac/
This directory contains a collection of 0/1 Multiple Knapsack Problems,
that are well known from the literature, and heuristically solved in the
following publications.
Tabu Search:
F. Dammeyer and S. Voss, "Dynamic tabu list management using
the reverse elimination method."
Annals of Operations Research, 1991.
Simulated Annealing:
A. Drexel, "A Simulated Annealing Approach to the
Multiconstraint Zero-One Knapsack Problem."
Computing, 40:1-8, 1988.
Genetic Algorithms:
S. Khuri, T. Baeck, J. Heitkoetter, "The Zero/One Multiple
Knapsack Problem and Genetic Algorithms", to appear in the 1994
ACM Symposium on Applied Computing, SAC'94, Phoenix,
Arizona, 1994.
Version: 13-JUL-93
CD-ROM: Prime Time Freeware for AI, Issue 1-1
Keywords:
Benchmark Data Sets, Genetic Algorithms!Benchmarks,
Knapsack Problems, Multiple Knapsack Problems, SAC94
References:
C.C. Petersen (1967) "Computational experience with variants of the
balas algorithm applied to the selection of R&D projects."
Management Science, 13:736-750. [PET*.DAT]
S. Senyu and Y. Toyada (1967) "An approach to linear programming
with 0-1 variables."
Management Science, 15:B196-B207. [SENTO*.DAT]
H.M. Weingartner and D.N. Ness (1967) "Methods for the solution of
the multi-dimensional 0/1 knapsack problem."
Operations Research, 15:83-103. [WEING*.DAT]
W. Shi (1979) "A branch and bound method for the multiconstraint
zero one knapsack problem."
J. Opl. Res. Soc., 30:369-378. [WEISH*.DAT]
A. Freville and G. Plateau (1990) "Hard 0-1 multiknapsack testproblems
for size reduction methods."
Investigation Operativa, 1:251-270. [PB*.DAT, HP*.DAT]
Last Web update on Mon Feb 13 10:23:19 1995
AI.Repository@cs.cmu.edu