Stabilized Branch-and-cut-and-price for the Generalized Assignment Problem

Alexandre Pigatti (apigattiinf.puc-rio.br)
Marcus Poggi de Aragão (poggiinf.puc-rio.br)
Eduardo Uchoa (uchoaproducao.uff.br)

Abstract: The Generalized Assignment Problem (GAP) is a classic scheduling problem with many applications. We propose a branch-and-cut-and-price for that problem featuring a stabilization mechanism to accelerate column generation convergence. We also propose ellipsoidal cuts, a new way of transforming the exact algorithm into a powerful heuristic, in the same spirit of the cuts recently proposed by Fischetti and Lodi. The improved solutions found by this heuristic can, in turn, help the task of the exact algorithm. The resulting algorithms showed a very good performance and were able to solve three among the last five open instances from the OR-Library.

Keywords: Column Generation, Integer Programming, Stabilization, MIP based local search

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Applications -- OR and Management Sciences (Scheduling )

Citation: Relatórios de Pesquisa em Engenharia de Produção, RPEP Vol.4 no. 21, Universidade Federal Fluminense, October, 2004.

Download: [PDF]

Entry Submitted: 10/31/2004
Entry Accepted: 11/01/2004
Entry Last Modified: 11/10/2004

Modify/Update this entry