Benders decomposition for large-scale uncapacitated hub location

Ivan Contreras, Jean François Cordeau, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

144 Citations (SciVal)


This paper describes an exact algorithm capable of solving large-scale instances of the well-known uncapacitated hub location problem with multiple assignments. The algorithm applies Benders decomposition to a strong path-based formulation of the problem. The standard decomposition algorithm is enhanced through the inclusion of several features such as the use of a multicut reformulation, the generation of strong optimality cuts, the integration of reduction tests, and the execution of a heuristic procedure. Extensive computational experiments were performed to evaluate the efficiency and robustness of the algorithm. Computational results obtained on classical benchmark instances (with up to 200 nodes) and on a new and more difficult set of instances (with up to 500 nodes) confirm the efficiency of the algorithm.

Original languageEnglish
Pages (from-to)1477-1490
Number of pages14
JournalOperations Research
Issue number6
Publication statusPublished - Nov 2011


  • Benders decomposition
  • Elimination tests
  • Hub location
  • Pareto-optimal cuts

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Benders decomposition for large-scale uncapacitated hub location'. Together they form a unique fingerprint.

Cite this