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

  • Alexandre Pigatti
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Meta Heuristics, Scheduling Tags , , , Short URL: https://optimization-online.org/?p=9634

    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.

    Citation

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

    Article

    Download

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