Using Surrogate Constraints in Genetic Algorithms for Solving Multidimensional Knapsack Problems

In the multidimensional knapsack problem (or multiconstraint zero-one knapsack problem) one has to decide on how to make efficient use of an entity which consumes multiple resources. The problem is known to be NP-hard, thus heuristics come into consideration for a solution. In this paper we investigate genetic algorithms as a solution approach. Surrogate constraints are generated by several different methods and are utilized as one of the stages in genetic algorithms for solving the multidimensional knapsack problem. This approach as a standalone method does not improve results but in conjunction with a greedy local search strategy results may be improved for problem instances with small object-constraint ratio.