Solving multidimensional knapsack problems with generalized upper bound constraints using critical event tabu search Academic Article

abstract

• A critical event tabu search method which navigates both sides of the feasibility boundary has been shown effective for solving the multidimensional knapsack problem. In this paper, we apply the method to the multidimensional knapsack problem with generalized upper bound constraints. This paper also demonstrates the merits of using surrogate constraint information vs. a Lagrangian relaxation scheme as choice rules for the problem class. A constraint normalization method is presented to strengthen the surrogate constraint information and improve the computational results. The advantages of intensifying the search at critical solutions are also demonstrated. 2003 Elsevier Ltd. All rights reserved.

authors

• Curry, Guy

published proceedings

• COMPUTERS & OPERATIONS RESEARCH

author list (cited authors)

• Li, V. C., & Curry, G. L.

citation count

• 20

complete list of authors

• Li, VC||Curry, GL

publication date

• January 2005

publisher

• Elsevier  Publisher

published in

• Computers and Operations Research  Journal

keywords

• Critical Event Tabu Search
• Gub
• Multidimensional Knapsack
• Strategic Oscillation
• Surrogate Constraint

Digital Object Identifier (DOI)

• 10.1016/j.cor.2003.08.021

start page

• 825

end page

• 848

volume

• 32

issue

• 4

URL

• http://dx.doi.org/10.1016/j.cor.2003.08.021