Premium
Projecting the flow variables for hub location problems
Author(s) -
Labbé Martine,
Yaman Hande
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20019
Subject(s) - polyhedron , projection (relational algebra) , mathematics , facet (psychology) , flow (mathematics) , inequality , facility location problem , combinatorics , mathematical optimization , flow network , algorithm , geometry , mathematical analysis , psychology , social psychology , personality , big five personality traits
We consider two formulations for the uncapacitated hub location problem with single assignment (UHL), which use multicommodity flow variables. We project out the flow variables and determine some extreme rays of the projection cones. Then we investigate whether the corresponding inequalities define facets of the UHL polyhedron. We also present two families of facet defining inequalities that dominate some projection inequalities. Finally, we derive a family of valid inequalities that generalizes the facet defining inequalities and that can be separated in polynomial time. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(2), 84–93 2004