The Tree of Hubs Location Problem: Formulation and Solution Algorithms

  • chair:

    Institutskolloquium des IOR

  • place:

    Gebäude 20.13, Raum 111

  • :

    June 18th, 2009

  • Referent:

    Elena Fernández, Universidad Polytècnica de Catalunya in Barcelona (Spain)

  • Zeit:

    17:30 Uhr

The Tree of Hubs Location Problem: Formulation and Solution Algorithms

 

The Tree of Hubs Location Problem (THLP) is a hub location problem that combines several aspects of location, network design and routing problems. Its main particularity is that it is required that the hubs are connected by means of a tree. Feasible solutions can be obtained with a simple heuristic. However, mathematical programming formulations that allow the exact solution of the THLP require a big number of variables which limits drastically the size of the instances that can addressed in practice. We present two different integer programming formulations for the THLP and, for each of them, we analyze its potential advantages and difficulties, as well as its algorithmic possibilities. Furthermore, we present several families of valid inequalities, and we give an exact separation procedure for them. Finally, some computational results are given that for instances up to 100 nodes.