An improved algorithm for fixed-hub single allocation problems

DOI10.1007/S40305-016-0143-1MaRDI QIDQ1697895zbMATH OpenOpenAlexFDO

Authors Zizhuo Wang, Lai Wei, Jiawei Zhang, Dongdong Ge

Publication date 20 February 2018

Published in Journal of the Operations Research Society of China (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.4183

zbMATH Keywords

linear programmingnetwork designworst-case analysishub location

Mathematics Subject Classification ID

Linear programming (90C05) Communication networks in operations research (90B18) Discrete location and assignment (90B80)

Abstract: This paper discusses the fixed-hub single allocation problem (FHSAP). In this problem, a network consists of hub nodes and terminal nodes. Hubs are fixed and fully connected; each terminal node is connected to a single hub which routes all its traffic. The goal is to minimize the cost of routing the traffic in the network. In this paper, we propose a linear programming (LP)-based rounding algorithm. The algorithm is based on two ideas. First, we modify the LP relaxation formulation introduced in Ernst and Krishnamoorthy (1996, 1999) by incorporating a set of validity constraints. Then, after obtaining a fractional solution to the LP relaxation, we make use of a geometric rounding algorithm to obtain an integral solution. We show that by incorporating the validity constraints, the strengthened LP often provides much tighter upper bounds than the previous methods with a little more computational effort, and the solution obtained often has a much smaller gap with the optimal solution. We also formulate a robust version of the FHSAP and show that it can guard against data uncertainty with little cost.

Recommendations

• Allocation strategies in hub networks
• The single allocation problem in the interacting three-hub network
• Algorithm for single allocation problem on hub-and-spoke networks in 2-dimensional plane
• Efficient algorithms for the uncapacitated single allocation p-hub median problem
• Tight linear programming relaxations of uncapacitated p-hub median problems

Cites work

• scientific article; zbMATH DE number 1803765 (Why is no real title available?)
• A quadratic integer program for the location of interacting hub facilities
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Efficient algorithms for the uncapacitated single allocation p-hub median problem
• Geometric rounding: A dependent randomized rounding scheme
• Heuristics for the p-hub location problem
• Hub Location and the p-Hub Median Problem
• Hub network design with single and multiple allocation: A computational study
• Integer programming formulations of discrete hub location problems
• Lower Bounds for the Hub Location Problem
• Robust optimization
• Solution algorithms for the capacitated single allocation hub location problem
• The single allocation problem in the interacting three-hub network
• Tight linear programming relaxations of uncapacitated \(p\)-hub median problems

Cited in

(3)

• The single allocation problem in the interacting three-hub network
• Algorithm for single allocation problem on hub-and-spoke networks in 2-dimensional plane
• Solution algorithms for the capacitated single allocation hub location problem

This page was built for publication: An improved algorithm for fixed-hub single allocation problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1697895)