An exact method with variable fixing for solving the generalized assignment problem |
| |
Authors: | Marius Posta Jacques A Ferland Philippe Michelon |
| |
Institution: | 1. Département d’Informatique et de Recherche Opérationelle, Université de Montréal, C.P. 6128, Succursale Centre-Ville, Montréal, Québec, H3C 3J7, Canada 2. Laboratoire d’Informatique d’Avignon, Université d’Avignon et des Pays du Vaucluse, 84911, Avignon, Cedex 9, France
|
| |
Abstract: | We propose a simple exact algorithm for solving the generalized assignment problem. Our contribution is twofold: we reformulate the optimization problem into a sequence of decision problems, and we apply variable-fixing rules to solve these effectively. The decision problems are solved by a simple depth-first lagrangian branch-and-bound method, improved by our variable-fixing rules to prune the search tree. These rules rely on lagrangian reduced costs which we compute using an existing but little-known dynamic programming algorithm. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|