Hub Location as the Minimization of a Supermodular Set Function

Ivan Contreras () and Elena Fernández ()
Additional contact information
Ivan Contreras: Concordia University and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montréal H3T 2A7, Canada
Elena Fernández: Statistics and Operations Research Department, Technical University of Catalonia, Barcelona, Spain 08034

Operations Research, 2014, vol. 62, issue 3, 557-570

Abstract: 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.

Keywords: hub location; supermodular functions; cutting plane methods; integer programming (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2014.1263 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:62:y:2014:i:3:p:557-570

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().