Upper and lower bounding procedures for the multiple knapsack assignment problem |
| |
Authors: | Seiji Kataoka Takeo Yamada |
| |
Affiliation: | Department of Computer Science, National Defense Academy, Yokosuka, Kanagawa 239-8686, Japan |
| |
Abstract: | We formulate the multiple knapsack assignment problem (MKAP) as an extension of the multiple knapsack problem (MKP), as well as of the assignment problem. Except for small instances, MKAP is hard to solve to optimality. We present a heuristic algorithm to solve this problem approximately but very quickly. We first discuss three approaches to evaluate its upper bound, and prove that these methods compute an identical upper bound. In this process, reference capacities are derived, which enables us to decompose the problem into mutually independent MKPs. These MKPs are solved euristically, and in total give an approximate solution to MKAP. Through numerical experiments, we evaluate the performance of our algorithm. Although the algorithm is weak for small instances, we find it prospective for large instances. Indeed, for instances with more than a few thousand items we usually obtain solutions with relative errors less than 0.1% within one CPU second. |
| |
Keywords: | Combinatorial optimization Heuristics Multiple knapsack problem Assignment problem Lagrangian relaxation |
本文献已被 ScienceDirect 等数据库收录! |
|