Страница публикации

A Computational Study of Exact Knapsack Separation for the Generalized Assignment Problem

Тип публикации: Статья в журнале

Тип материала: Текст

Авторы: Avella P., Boccia M., Vasilyev I.

Журнал: Computational Optimization and Applications

Язык публикации: english

Том: 45

Номера страниц: 543-555

Количество страниц: 13

Номер: 3

Год публикации: 2010

Отчетный год: 2010

DOI: 10.1007/s10589-008-9183-8

Аннотация: The Generalized Assignment Problem is a well-known NP-hard combinatorial optimization problem which consists of minimizing the assignment costs of a set of jobs to a set of machines satisfying capacity constraints. Most of the existing algorithms are of a Branch-and-Price type, with lower bounds computed through Dantzig-Wolfe reformulation and column generation. In this paper we propose a cutting plane algorithm working in the space of the variables of the basic formulation, whose core is an exact separation procedure for the knapsack polytopes induced by the capacity constraints. We show that an efficient implementation of the exact separation procedure allows to deal with large-scale instances and to solve to optimality several previously unsolved instances.

Индексируется WOS: Q1

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет