Stabilized Branch-and-cut-and-price for the Generalized Assignment Problem
Alexandre Pigatti (apigattiinf.puc-rio.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.
Entry Submitted: 10/31/2004
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|