NDLI: Minimum concave cost multicommodity network design

Content Provider	Springer Nature Link
Author	Bazlamaçcı, Cüneyt F. Say, Fatih
Copyright Year	2008
Abstract	The minimum concave cost multicommodity network design problem (MCMNDP) arises in many application areas, such as transportation planning, energy distribution systems and especially in the design of both packet and circuit switching backbone networks. Exact concave cost optimization algorithms have been developed but they are applicable only if the network size is small. Therefore, MCMNDP is usually solved using non-exact iterative methods. In this paper, such heuristic techniques proposed within the context of circuit switching and packet switching network design are evaluated in detail. Following a comprehensive literature survey, Yaged’s linearization, Minoux’s greedy and Minoux’s accelerated greedy methods have been selected for the circuit switching network design case for further investigation. Minoux’s greedy methods are found to create routes that include cycles causing degradation in the quality of the solution; therefore, we propose a simple but effective modification scheme as a cycle elimination strategy. Similarly, but within the context of packet switching network design, Gerla and Kleinrock’s concave branch elimination, Gersht’s greedy, and Stacey’s concave link elimination methods have been selected for further investigation. All of these methods consider aggregate flows on each link, simultaneously re-routing more than one commodity in one step. In this paper, we propose an alternative disaggregate approach, where only one commodity is handled at a time. Our final proposal is the adaptation of the algorithms proposed for circuit switching network design to the packet switching case. Then an extensive comparative computational study is performed for a number of networks and cost structures to help establish the best method with respect to time and solution quality. Our computational results have shown that the performances of the MCMNDP algorithms heavily depend on the network type and the cost structure. The results have also revealed that our proposed modification to Minoux greedy to eliminate cycles leads to considerable improvements and our proposed disaggregate approach gives the best result in some networks with certain cost structures.
Starting Page	181
Ending Page	203
Page Count	23
File Format	PDF
ISSN	10184864
Journal	Telecommunication Systems
Volume Number	36
Issue Number	4
e-ISSN	15729451
Language	English
Publisher	Springer US
Publisher Date	2008-02-15
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Concave cost network design Circuit switching and packet switching network design Multicommodity flow problem Probability Theory and Stochastic Processes Artificial Intelligence (incl. Robotics) Computer Communication Networks Business Information Systems
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering

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

Telecommunications network design with multiple technologies

Solving multicommodity integral flow problems by simulated allocation

A concave link elimination (CLE) procedure and lower bound for concave topology, capacity and flow assignment network design problems

Protecting local access telecommunications networks: Toward a minimum-cost solution

A randomized rounding approach to a k-splittable multicommodity flow problem with lower path flow bounds affording solution quality guarantees

An Efficient Scheduling Discipline for Packet Switching Networks Using Earliest Deadline First Round Robin

Multilayered Wholesale Resource Trading to Foster Service Diversity in Packet-Switching Networks

Adaptive random sampling for traffic volume measurement

Model and heuristic for a generalized access network design problem

Minimum concave cost multicommodity network design

Similar Documents

Telecommunications network design with multiple technologies

Solving multicommodity integral flow problems by simulated allocation

A concave link elimination (CLE) procedure and lower bound for concave topology, capacity and flow assignment network design problems

Protecting local access telecommunications networks: Toward a minimum-cost solution

A randomized rounding approach to a k-splittable multicommodity flow problem with lower path flow bounds affording solution quality guarantees

An Efficient Scheduling Discipline for Packet Switching Networks Using Earliest Deadline First Round Robin

Multilayered Wholesale Resource Trading to Foster Service Diversity in Packet-Switching Networks

Adaptive random sampling for traffic volume measurement

Model and heuristic for a generalized access network design problem

Minimum concave cost multicommodity network design