An exact method with variable fixing for solving the generalized assignment problem
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. Copyright Springer Science+Business Media, LLC 2012
Volume (Year): 52 (2012)
Issue (Month): 3 (July)
|Contact details of provider:|| Web page: http://www.springer.com|
|Order Information:||Web: http://www.springer.com/math/journal/10589|
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Pasquale Avella & Maurizio Boccia & Igor Vasilyev, 2010. "A computational study of exact knapsack separation for the generalized assignment problem," Computational Optimization and Applications, Springer, vol. 45(3), pages 543-555, April.
- Diaz, Juan A. & Fernandez, Elena, 2001. "A Tabu search heuristic for the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 132(1), pages 22-38, July.
- Haddadi, Salim & Ouzia, Hacene, 2004. "Effective algorithm and heuristic for the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 153(1), pages 184-190, February.
When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:52:y:2012:i:3:p:629-644. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Sonal Shukla)or (Rebekah McClure)
If references are entirely missing, you can add them using this form.