Optimization Online


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

Pasqualle Avella (avella***at***unisannio.it)
Boccia Maurizio (maboccia***at***unisannio.it)
Igor Vasilyev (vil***at***icc.ru)

Abstract: The Generalized Assignment Problem is a well-known NP-hard combinatorial optimization problem which consists of minimizing the assignment costs a set of jobs to a set of machines satisfying capacity constraints. Most of the existing algorithms are based on Branch-and-Price, with lower bounds computed by 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, based on 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 many previously unsolved instances.

Keywords: generalized assigment problem, knapsack probblem, cutting plane algorithm

Category 1: Integer Programming (0-1 Programming )

Citation: Computational Optimization and Applications, 2008, DOI: 10.1007/s10589-008-9183-8


Entry Submitted: 04/24/2007
Entry Accepted: 04/24/2007
Entry Last Modified: 06/07/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society