This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Ceselli, A. Articles by Righini, G. Search for Related Content

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

Dipartimento di Tecnologie dell’Informazione, Università degli Studi di Milano, via Bramante 65, 26013, Crema, Italy
Dipartimento di Tecnologie dell’Informazione, Università degli Studi di Milano, via Bramante 65, 26013, Crema, Italy
ceselli{at}dti.unimi.it
righini{at}dti.unimi.it

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.

Subject classifications: integer programming: branch-and-price; production-scheduling: generalized assignment.
History: Received May 2004; revision received October 2005; accepted October 2005.