IEICE TRANSACTIONS on Communications
Network Congestion Minimization Models Based on Robust Optimization
Summary :
This paper introduces robust optimization models for minimization of the network congestion ratio that can handle the fluctuation in traffic demands between nodes. The simplest and widely used model to minimize the congestion ratio, called the pipe model, is based on precisely specified traffic demands. However, in practice, network operators are often unable to estimate exact traffic demands as they can fluctuate due to unpredictable factors. To overcome this weakness, we apply robust optimization to the problem of minimizing the network congestion ratio. First, we review existing models as robust counterparts of certain uncertainty sets. Then we consider robust optimization assuming ellipsoidal uncertainty sets, and derive a tractable optimization problem in the form of second-order cone programming (SOCP). Furthermore, we take uncertainty sets to be the intersection of ellipsoid and polyhedral sets, and considering the mirror subproblems inherent in the models, obtain tractable optimization problems, again in SOCP form. Compared to the previous model that assumes an error interval on each coordinate, our models have the advantage of being able to cope with the total amount of errors by setting a parameter that determines the volume of the ellipsoid. We perform numerical experiments to compare our SOCP models with the existing models which are formulated as linear programming problems. The results demonstrate the relevance of our models in terms of congestion ratio and computation time.
- Publication
- IEICE TRANSACTIONS on Communications Vol.E101-B No.3 pp.772-784
- Publication Date
- 2018/03/01
- Publicized
- 2017/09/14
- Online ISSN
- 1745-1345
- DOI
- 10.1587/transcom.2017EBP3193
- Type of Manuscript
- PAPER
- Category
- Network
Authors
Bimal CHANDRA DAS
The University of Electro-Communications
Satoshi TAKAHASHI
The University of Electro-Communications
Eiji OKI
Kyoto University
Masakazu MURAMATSU
The University of Electro-Communications
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
Bimal CHANDRA DAS, Satoshi TAKAHASHI, Eiji OKI, Masakazu MURAMATSU, "Network Congestion Minimization Models Based on Robust Optimization" in IEICE TRANSACTIONS on Communications,
vol. E101-B, no. 3, pp. 772-784, March 2018, doi: 10.1587/transcom.2017EBP3193.
Abstract: This paper introduces robust optimization models for minimization of the network congestion ratio that can handle the fluctuation in traffic demands between nodes. The simplest and widely used model to minimize the congestion ratio, called the pipe model, is based on precisely specified traffic demands. However, in practice, network operators are often unable to estimate exact traffic demands as they can fluctuate due to unpredictable factors. To overcome this weakness, we apply robust optimization to the problem of minimizing the network congestion ratio. First, we review existing models as robust counterparts of certain uncertainty sets. Then we consider robust optimization assuming ellipsoidal uncertainty sets, and derive a tractable optimization problem in the form of second-order cone programming (SOCP). Furthermore, we take uncertainty sets to be the intersection of ellipsoid and polyhedral sets, and considering the mirror subproblems inherent in the models, obtain tractable optimization problems, again in SOCP form. Compared to the previous model that assumes an error interval on each coordinate, our models have the advantage of being able to cope with the total amount of errors by setting a parameter that determines the volume of the ellipsoid. We perform numerical experiments to compare our SOCP models with the existing models which are formulated as linear programming problems. The results demonstrate the relevance of our models in terms of congestion ratio and computation time.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2017EBP3193/_p
Copy
@ARTICLE{e101-b_3_772,
author={Bimal CHANDRA DAS, Satoshi TAKAHASHI, Eiji OKI, Masakazu MURAMATSU, },
journal={IEICE TRANSACTIONS on Communications},
title={Network Congestion Minimization Models Based on Robust Optimization},
year={2018},
volume={E101-B},
number={3},
pages={772-784},
abstract={This paper introduces robust optimization models for minimization of the network congestion ratio that can handle the fluctuation in traffic demands between nodes. The simplest and widely used model to minimize the congestion ratio, called the pipe model, is based on precisely specified traffic demands. However, in practice, network operators are often unable to estimate exact traffic demands as they can fluctuate due to unpredictable factors. To overcome this weakness, we apply robust optimization to the problem of minimizing the network congestion ratio. First, we review existing models as robust counterparts of certain uncertainty sets. Then we consider robust optimization assuming ellipsoidal uncertainty sets, and derive a tractable optimization problem in the form of second-order cone programming (SOCP). Furthermore, we take uncertainty sets to be the intersection of ellipsoid and polyhedral sets, and considering the mirror subproblems inherent in the models, obtain tractable optimization problems, again in SOCP form. Compared to the previous model that assumes an error interval on each coordinate, our models have the advantage of being able to cope with the total amount of errors by setting a parameter that determines the volume of the ellipsoid. We perform numerical experiments to compare our SOCP models with the existing models which are formulated as linear programming problems. The results demonstrate the relevance of our models in terms of congestion ratio and computation time.},
keywords={},
doi={10.1587/transcom.2017EBP3193},
ISSN={1745-1345},
month={March},}
Copy
TY - JOUR
TI - Network Congestion Minimization Models Based on Robust Optimization
T2 - IEICE TRANSACTIONS on Communications
SP - 772
EP - 784
AU - Bimal CHANDRA DAS
AU - Satoshi TAKAHASHI
AU - Eiji OKI
AU - Masakazu MURAMATSU
PY - 2018
DO - 10.1587/transcom.2017EBP3193
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E101-B
IS - 3
JA - IEICE TRANSACTIONS on Communications
Y1 - March 2018
AB - This paper introduces robust optimization models for minimization of the network congestion ratio that can handle the fluctuation in traffic demands between nodes. The simplest and widely used model to minimize the congestion ratio, called the pipe model, is based on precisely specified traffic demands. However, in practice, network operators are often unable to estimate exact traffic demands as they can fluctuate due to unpredictable factors. To overcome this weakness, we apply robust optimization to the problem of minimizing the network congestion ratio. First, we review existing models as robust counterparts of certain uncertainty sets. Then we consider robust optimization assuming ellipsoidal uncertainty sets, and derive a tractable optimization problem in the form of second-order cone programming (SOCP). Furthermore, we take uncertainty sets to be the intersection of ellipsoid and polyhedral sets, and considering the mirror subproblems inherent in the models, obtain tractable optimization problems, again in SOCP form. Compared to the previous model that assumes an error interval on each coordinate, our models have the advantage of being able to cope with the total amount of errors by setting a parameter that determines the volume of the ellipsoid. We perform numerical experiments to compare our SOCP models with the existing models which are formulated as linear programming problems. The results demonstrate the relevance of our models in terms of congestion ratio and computation time.
ER -
English
