An access network design problem with end-to-end QoS constraints

Chanwoo Park; Youngho Lee; Youngjin Kim; Gigyoung Park

doi:10.1016/j.omega.2014.02.006

An access network design problem with end-to-end QoS constraints

Chanwoo Park, Youngho Lee, Youngjin Kim, Gigyoung Park

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

In this paper, we present an access network design problem with end-to-end quality of service (QoS) requirement. The problem can be conceptualized as a two-level hierarchical location-allocation problem on the tree topology with nonlinear side constraints. The objective function of the nonlinear mixed integer programming model minimizes the total cost of switch and fiber cable, while satisfying demand within the prescribed level of QoS. By exploiting the inherent structure of the nonlinear QoS constraints, we develop linearization techniques for finding an optimal solution. Also, we devise an effective exact optimal algorithm within the context of disjunctive constraint generation. We present promising computational results that demonstrate the effectiveness of the proposed solution procedure.

Original language	English
Pages (from-to)	36-48
Number of pages	13
Journal	Omega (United Kingdom)
Volume	48
DOIs	https://doi.org/10.1016/j.omega.2014.02.006
Publication status	Published - 2014 Oct

Bibliographical note

Funding Information:
This work was supported by the second phase of the Brain Korea 21 Program in 2012, by National Research Foundation of Korea Grant funded by the Korean Government (Nos. 2011-0011400 and 2012R-1A-1A2006847 ), and by Korea University Research Grant 2012.

Keywords

Access network design
Constraint generation
Hierarchical location-allocation problem
Linearization techniques
Mixed integer nonlinear programming

ASJC Scopus subject areas

Strategy and Management
Management Science and Operations Research
Information Systems and Management

Access to Document

10.1016/j.omega.2014.02.006

Cite this

@article{d98eed4085394fefb3e3b369a6dcd460,

title = "An access network design problem with end-to-end QoS constraints",

abstract = "In this paper, we present an access network design problem with end-to-end quality of service (QoS) requirement. The problem can be conceptualized as a two-level hierarchical location-allocation problem on the tree topology with nonlinear side constraints. The objective function of the nonlinear mixed integer programming model minimizes the total cost of switch and fiber cable, while satisfying demand within the prescribed level of QoS. By exploiting the inherent structure of the nonlinear QoS constraints, we develop linearization techniques for finding an optimal solution. Also, we devise an effective exact optimal algorithm within the context of disjunctive constraint generation. We present promising computational results that demonstrate the effectiveness of the proposed solution procedure.",

keywords = "Access network design, Constraint generation, Hierarchical location-allocation problem, Linearization techniques, Mixed integer nonlinear programming",

author = "Chanwoo Park and Youngho Lee and Youngjin Kim and Gigyoung Park",

note = "Funding Information: This work was supported by the second phase of the Brain Korea 21 Program in 2012, by National Research Foundation of Korea Grant funded by the Korean Government (Nos. 2011-0011400 and 2012R-1A-1A2006847 ), and by Korea University Research Grant 2012. ",

year = "2014",

month = oct,

doi = "10.1016/j.omega.2014.02.006",

language = "English",

volume = "48",

pages = "36--48",

journal = "Omega (United Kingdom)",

issn = "0305-0483",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - An access network design problem with end-to-end QoS constraints

AU - Park, Chanwoo

AU - Lee, Youngho

AU - Kim, Youngjin

AU - Park, Gigyoung

N1 - Funding Information: This work was supported by the second phase of the Brain Korea 21 Program in 2012, by National Research Foundation of Korea Grant funded by the Korean Government (Nos. 2011-0011400 and 2012R-1A-1A2006847 ), and by Korea University Research Grant 2012.

PY - 2014/10

Y1 - 2014/10

N2 - In this paper, we present an access network design problem with end-to-end quality of service (QoS) requirement. The problem can be conceptualized as a two-level hierarchical location-allocation problem on the tree topology with nonlinear side constraints. The objective function of the nonlinear mixed integer programming model minimizes the total cost of switch and fiber cable, while satisfying demand within the prescribed level of QoS. By exploiting the inherent structure of the nonlinear QoS constraints, we develop linearization techniques for finding an optimal solution. Also, we devise an effective exact optimal algorithm within the context of disjunctive constraint generation. We present promising computational results that demonstrate the effectiveness of the proposed solution procedure.

AB - In this paper, we present an access network design problem with end-to-end quality of service (QoS) requirement. The problem can be conceptualized as a two-level hierarchical location-allocation problem on the tree topology with nonlinear side constraints. The objective function of the nonlinear mixed integer programming model minimizes the total cost of switch and fiber cable, while satisfying demand within the prescribed level of QoS. By exploiting the inherent structure of the nonlinear QoS constraints, we develop linearization techniques for finding an optimal solution. Also, we devise an effective exact optimal algorithm within the context of disjunctive constraint generation. We present promising computational results that demonstrate the effectiveness of the proposed solution procedure.

KW - Access network design

KW - Constraint generation

KW - Hierarchical location-allocation problem

KW - Linearization techniques

KW - Mixed integer nonlinear programming

UR - http://www.scopus.com/inward/record.url?scp=84901491995&partnerID=8YFLogxK

U2 - 10.1016/j.omega.2014.02.006

DO - 10.1016/j.omega.2014.02.006

M3 - Article

AN - SCOPUS:84901491995

SN - 0305-0483

VL - 48

SP - 36

EP - 48

JO - Omega (United Kingdom)

JF - Omega (United Kingdom)

ER -

An access network design problem with end-to-end QoS constraints

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this