Hub Location as the Minimization of a Supermodular Set Function

• 成果类型: Article
• 署名作者: Contreras, Ivan; Fernandez, Elena
• 署名单位: Concordia University - Canada; Universite de Montreal; Universitat Politecnica de Catalunya
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2014.1263
• 发表日期: 2014
• 页码: 557-570
• 关键词: Network design; cut algorithm; formulation; approximations; facilities; branch; bounds

摘要

This paper highlights how a general class of hub location problems can be modeled as the minimization of a real-valued supermodular set function. Well-known problems such as uncapacitated hub location, p-hub median, and hub arc location, among others, are shown to be particular cases of this class. Two integer programming formulations are introduced and compared. One uses path-based variables, frequently employed in hub location, whereas the other exploits properties of supermodular functions. In addition, several worst case bounds for a greedy and a local improvement heuristic are obtained for the general class and for some particular cases in which sharper bounds can be devised. Computational experiments are performed to compare both formulations when used with a general purpose solver. Computational results obtained on benchmark instances confirm the superiority of the supermodular formulation.