A Branch-and-Price Algorithm for the Multilevel Generalized Assignment Problem

Alberto Ceselli () and Giovanni Righini ()
Additional contact information
Alberto Ceselli: Dipartimento di Tecnologie dell’Informazione, Università degli Studi di Milano, via Bramante 65, 26013, Crema, Italy
Giovanni Righini: Dipartimento di Tecnologie dell’Informazione, Università degli Studi di Milano, via Bramante 65, 26013, Crema, Italy

Operations Research, 2006, vol. 54, issue 6, 1172-1184

Abstract: The multilevel generalized assignment problem (MGAP) is a variation of the generalized assignment problem, in which agents can execute tasks at different efficiency levels with different costs. We present a branch-and-price algorithm that is the first exact algorithm for the MGAP. It is based on a decomposition into a master problem with set-partitioning constraints and a pricing subproblem that is a multiple-choice knapsack problem. We report on our computational experience with randomly generated instances with different numbers of agents, tasks, and levels; and with different correlations between cost and resource consumption for each agent-task-level assignment. Experimental results show that our algorithm is able to solve instances larger than those of the maximum size considered in the literature to proven optimality.

Keywords: integer programming: branch-and-price; production-scheduling: generalized assignment (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1060.0323 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:54:y:2006:i:6:p:1172-1184

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().