IEICE TRANSACTIONS on Fundamentals
A Linear Relaxation for Hub Network Design Problems
Summary :
In this paper, we consider a network design problem with hub-and-spoke structure. We propose a relaxation technique for the problem where the location of hub nodes is given and decides the allocation of non-hub nodes to one of the hub nodes. We linearize the non-convex quadratic objective function of the original problem, introducing Hitchcock transportation problems defined for each pair of non-hub nodes. We provide two linear relaxation problems, one based on the Hitchcock transportation problems and the other on the dual Hitchcock transportation problems. We show the tightness of the lower bounds obtained by our formulations by computational experiences.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.1000-1005
- Publication Date
- 2002/05/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiro-o SAITO, Shiro MATUURA, Tomomi MATSUI, "A Linear Relaxation for Hub Network Design Problems" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 1000-1005, May 2002, doi: .
Abstract: In this paper, we consider a network design problem with hub-and-spoke structure. We propose a relaxation technique for the problem where the location of hub nodes is given and decides the allocation of non-hub nodes to one of the hub nodes. We linearize the non-convex quadratic objective function of the original problem, introducing Hitchcock transportation problems defined for each pair of non-hub nodes. We provide two linear relaxation problems, one based on the Hitchcock transportation problems and the other on the dual Hitchcock transportation problems. We show the tightness of the lower bounds obtained by our formulations by computational experiences.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_1000/_p
Copy
@ARTICLE{e85-a_5_1000,
author={Hiro-o SAITO, Shiro MATUURA, Tomomi MATSUI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Linear Relaxation for Hub Network Design Problems},
year={2002},
volume={E85-A},
number={5},
pages={1000-1005},
abstract={In this paper, we consider a network design problem with hub-and-spoke structure. We propose a relaxation technique for the problem where the location of hub nodes is given and decides the allocation of non-hub nodes to one of the hub nodes. We linearize the non-convex quadratic objective function of the original problem, introducing Hitchcock transportation problems defined for each pair of non-hub nodes. We provide two linear relaxation problems, one based on the Hitchcock transportation problems and the other on the dual Hitchcock transportation problems. We show the tightness of the lower bounds obtained by our formulations by computational experiences.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - A Linear Relaxation for Hub Network Design Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1000
EP - 1005
AU - Hiro-o SAITO
AU - Shiro MATUURA
AU - Tomomi MATSUI
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2002
AB - In this paper, we consider a network design problem with hub-and-spoke structure. We propose a relaxation technique for the problem where the location of hub nodes is given and decides the allocation of non-hub nodes to one of the hub nodes. We linearize the non-convex quadratic objective function of the original problem, introducing Hitchcock transportation problems defined for each pair of non-hub nodes. We provide two linear relaxation problems, one based on the Hitchcock transportation problems and the other on the dual Hitchcock transportation problems. We show the tightness of the lower bounds obtained by our formulations by computational experiences.
ER -
English
