NDLI: Formulations and algorithms for the multi-path selection problem in network routing

Content Provider	IEEE Xplore Digital Library
Author	Kazmi, N.A. Koster, A.M.C.A. Branke, J.
Copyright Year	2012
Description	Author affiliation: Warwick Business School, University of Warwick, Coventry CV4 7AL, UK (Kazmi, N.A.; Branke, J.) \|\| Lehrstuhl II für Mathematik, RWTH Aachen University, 52062, Germany (Koster, A.M.C.A.)
Abstract	Traffic bifurcation over multiple paths may be used to balance load on telecommunication networks. This balancing of load not only improves resilience against link failures but also provides an indication of the margin available for growth in demand values. In this paper, we present a novel mixed integer programming formulation for minimization of maximum link utilization in the case of link failure. The new formulation is much more compact than a previously proposed formulation. Additionally, we propose a local search heuristic with exact neighborhood search to tackle larger problems within reasonable computational time. The empirical examination on several test problems demonstrates that, with the new compact problem formulation, CPLEX is able to find solutions much quicker. The heuristic works well and in several cases yields better solutions than ILP in a given time limit, or provides solutions for problems where ILP could not even find one valid solution in the given time limit. In cases where ILP is able to find the optimal solution, the heuristic algorithm obtains the same solution usually in less time.
Starting Page	738
Ending Page	744
File Size	452883
Page Count	7
File Format	PDF
ISBN	9781467320160
ISSN	2157023X
e-ISBN	9781467320177
DOI	10.1109/ICUMT.2012.6459762
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-10-03
Publisher Place	Russia
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Network protection Heuristic algorithms Pricing Routing Minimization Educational institutions Self-protecting multi-paths Mathematical model Survivability Load modeling
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in