Polyhedral Analysis of Uncapacitated Single Allocation p-Hub Center Problems

Technical Report, Reports in Wirtschaftsmathematik, Number 109, Technische Universität Kaiserslautern, Available at http://kluedo.ub.uni-kl.de/volltexte/2007/2088/, April, 2007

Authors

• Silke Jütte
• Elena Gavriliouk
• Horst W. Hamacher

Abstract

In contrast to p-hub problems with a summation objective (p-hub median), minmax hub problems (p-hub center) have not attained much attention in the literature. In this paper, we give a polyhedral analysis of the uncapacitated single allocation p-hub center problem (USApHCP). The analysis will be based on a radius formulation which currently yields the most efficient solution procedures. We show which of the valid inequalities in this formulation are facet-defining and present non-elementary classes of facets, for which we propose separation problems. A major part in our argumentation will be the close connection between polytopes of the USApHCP and the uncapacitated p-facility location (pUFL). Hence, the new classes of facets can also be used to improve pUFL formulations.

BibTeX

 
@TechReport{ JuettaGavHam07, 
   title = { Polyhedral Analysis of Uncapacitated Single Allocation p-Hub Center Problems }, 
   author = { Silke Jütte and Elena Gavriliouk and Horst W. Hamacher },     
   series = { Reports in Wirtschaftsmathematik },  
   number = { 109 }, 
   institution = { Technische Universität Kaiserslautern },       
   note = { Available at http://kluedo.ub.uni-kl.de/volltexte/2007/2088/ }, 
   month = apr, 
   year = 2007, 
} 

---

This publication belongs to the project DeNDeMA.