A distributed scheme for resolution of the single-path routing problem
(2013) 9th International Conference on the Design of Reliable Communication Networks (DRCN), 2013 p.210-217- Abstract
- The goal of the paper is to present a distributed scheme to resolving a single path routing problem in multidomain networks. The global problem is formulated as a mixed-integer program (MIP) and approached by means of branch-and-price (B&P). Problems associated with a B&P tree nodes are decomposed using the Dantzig-Wolfe method to a set of domain subproblems coordinated by a single master problem. The presented scheme applies a novel formulation of a domain subproblem that in general results in very tight bounds on the problem represented by a B&P node and hence leads to faster completion of the B&P algorithm. The issue of implementing such a scheme as a distributed network-wide process which could be run in the control... (More)
- The goal of the paper is to present a distributed scheme to resolving a single path routing problem in multidomain networks. The global problem is formulated as a mixed-integer program (MIP) and approached by means of branch-and-price (B&P). Problems associated with a B&P tree nodes are decomposed using the Dantzig-Wolfe method to a set of domain subproblems coordinated by a single master problem. The presented scheme applies a novel formulation of a domain subproblem that in general results in very tight bounds on the problem represented by a B&P node and hence leads to faster completion of the B&P algorithm. The issue of implementing such a scheme as a distributed network-wide process which could be run in the control plane of the multi-domain network is considered. Correctness of the scheme is verified experimentally and results of preliminary numerical tests are presented. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/3912859
- author
- Mycek, Mariusz and Pioro, Michal LU
- organization
- publishing date
- 2013
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- [Host publication title missing]
- pages
- 210 - 217
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- conference name
- 9th International Conference on the Design of Reliable Communication Networks (DRCN), 2013
- conference location
- Budapest, Hungary
- conference dates
- 2013-03-04 - 2013-03-07
- external identifiers
-
- scopus:84881102065
- ISBN
- 978-1-4799-0049-7
- language
- English
- LU publication?
- yes
- id
- e5aab104-db6b-45e0-85e6-a0798fa2b5c4 (old id 3912859)
- alternative location
- http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6529863
- date added to LUP
- 2016-04-04 11:47:03
- date last changed
- 2022-01-29 22:25:45
@inproceedings{e5aab104-db6b-45e0-85e6-a0798fa2b5c4, abstract = {{The goal of the paper is to present a distributed scheme to resolving a single path routing problem in multidomain networks. The global problem is formulated as a mixed-integer program (MIP) and approached by means of branch-and-price (B&P). Problems associated with a B&P tree nodes are decomposed using the Dantzig-Wolfe method to a set of domain subproblems coordinated by a single master problem. The presented scheme applies a novel formulation of a domain subproblem that in general results in very tight bounds on the problem represented by a B&P node and hence leads to faster completion of the B&P algorithm. The issue of implementing such a scheme as a distributed network-wide process which could be run in the control plane of the multi-domain network is considered. Correctness of the scheme is verified experimentally and results of preliminary numerical tests are presented.}}, author = {{Mycek, Mariusz and Pioro, Michal}}, booktitle = {{[Host publication title missing]}}, isbn = {{978-1-4799-0049-7}}, language = {{eng}}, pages = {{210--217}}, publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}}, title = {{A distributed scheme for resolution of the single-path routing problem}}, url = {{http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6529863}}, year = {{2013}}, }