| The multidimensional knapsack problem has been used to model various decision-making processes in business, engineering and other areas. In addition to its numerous applications including capital budgeting, cargo loading, computer systems design and combinatorial auction, the MKP is also important from a theoretical point of view due to its generality.; The MKP is known to be NP-hard thus we cannot expect to find fully polynomial approximation schemes. For this reason, researchers have recently focused on finding “good” heuristic solutions.; In this dissertation, a Lagrangian based local search approach to the Multidimensional Knapsack Problem is proposed. It combines a dual space cyclic coordinate search motivated by previous ideas of Wedelin (1995) with local search techniques, in this case Tabu search. The general philosophy is to utilize the information provided by duality theory to find promising regions, then use local search to intensively investigate these promising local regions of the solution space. Empirical studies were conducted to investigate the effects of the algorithm parameters on the quality of the solution. Approaches, such as adding cuts, to enhance the algorithm are also discussed. The neighborhood used to conduct Tabu search is made more efficient by reducing the variables considered to a most promising core set. The proposed approach has been tested on standard MKP test problems from OR-Library as well as much larger instances generated by us using previously proposed methods. It competed successfully with state-of-the-art heuristics and commercial software both in terms of computational time and the quality of objective values. |
