Adapting polyhedral properties from facility to hub location problems

We examine the feasibility polyhedron of the uncapacitated hub location problem (UHL) with multiple allocation, which has applications in the fields of air passenger and cargo transportation, telecommunication and postal delivery services. In particular we determine the dimension and derive some classes of facets for this polyhedron. We develop a general rule about lifting facets from the uncapacitated facility location problem to UHL. Using this lifting procedure we derive a new class of facets for UHL which dominates the inequalities in the original formulation. Thus we obtain a new formulation of the UHL whose constraints are all facet-defining. (C) 2003 Elsevier B.V. All rights reserved.