Paper Info
Title
A Branch-and-Price Algorithm for the Multilevel Generalized Assignment Problem
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.
Year
DOI
Venue
2006
10.1287/opre.1060.0323
Operations Research
Keywords
Field
DocType
different correlation,branch-and-price algorithm,different efficiency level,multilevel generalized assignment problem,master problem,different cost,multiple-choice knapsack problem,generalized assignment problem,different number,agent-task-level assignment,branch and price
Weapon target assignment problem,Mathematical optimization,Exact algorithm,Branch and price,Generalized assignment problem,Algorithm,Assignment problem,Integer programming,Knapsack problem,Mathematics,Linear bottleneck assignment problem
Journal
Volume
Issue
ISSN
54
6
0030-364X
Citations 
PageRank 
References 
10
0.64
7
Authors
2
Name
Order
Citations
PageRank
Alberto Ceselli134130.53
Giovanni Righini252033.90