Hard knapsack problems that are easy for local search

Hard knapsack problems that are easy for local search

0.00 Avg rating—0 Votes
Article ID: iaor20003741
Country: Singapore
Volume: 16
Issue: 2
Start Page Number: 165
End Page Number: 172
Publication Date: Nov 1999
Journal: Asia-Pacific Journal of Operational Research
Authors: ,
Keywords: heuristics, optimization, computational analysis
Abstract:

Chvátal describes a class of zero–one knapsack problems provably difficult for branch and bound and dynamic programming algorithms. Chung et al. identifies a class of integer knapsack problems hard for branch and bound algorithms. We show that for both classes of problems local search provides optimal solutions quickly.

Reviews

Required fields are marked *. Your email address will not be published.