A branch-and-price algorithm for the multilevel generalized assignment problem

被引：16

作者：

Ceselli, Alberto ^{[1
]}

Righini, Giovanni ^{[1
]}

机构：

[1] Univ Milan, Dipartimento Tecnol Informaz, I-26013 Crema, Italy

来源：

OPERATIONS RESEARCH | 2006年 / 54卷 / 06期

关键词：

D O I：

10.1287/opre.1060.0323

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：1172 / 1184

页数：13

共 14 条

[1] Branch-and-price: Column generation for solving huge integer programs [J].