Reformulations and Computational Results for the Uncapacitated Single Allocation Hub Covering Problem

Andreas Ernst, Houyuan Jiang, M Krishnamoorthy, Davaatseren Baatar

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch


We study the single allocation hub covering problem, which is a special case of the general hub location problem and an important extension to traditional covering problems. Hubs are located at some nodes in the network and are used to facilitate (consolidate, transfer, distribute) flows. An important feature in hub location is that the transfer cost between hub nodes is discounted. The hub covering problem is to locate a minimum number of hubs such that the travel cost between each o–d pair in the network does not exceed a given threshold. We improve the best existing integer programming formulation for this problem by lifting constraints to produce facet-defining inequalities. We also develop a new formulation for the problem. The numerical results show that your new formulation performs better than existing formulations when using lifted constraints and paying special attention the number of non-zero coefficients used.
Original languageEnglish
Title of host publicationData and Decision Sciences in Action
Subtitle of host publicationProceedings of the Australian Society for Operations Research Conference 2016
EditorsRuhul Sarker, Hussein A Abbass, Simon Dunstall, Philip Kilby, Richard Davis, Leon Young
Place of PublicationCham Switzerland
Number of pages16
ISBN (Electronic)9783319559148
ISBN (Print)9783319559131
Publication statusPublished - 2018
EventAustralian Society for Operations Research Conference 2016 - Canberra, Australia
Duration: 16 Nov 201618 Nov 2016
Conference number: 24th

Publication series

NameLecture Notes in Management and Industrial Engineering
ISSN (Print)2198-0772
ISSN (Electronic)2198-0780


ConferenceAustralian Society for Operations Research Conference 2016
Abbreviated titleASOR 2016
OtherThe 24th ASOR Nation conference, 16-18 November 2016, Canberra
Internet address

Cite this