An Improved Flow Deviation Method for the Maximum Concurrent Flow Problem

Yanxiang Chen; Yu Zhang; Mengze Yuan

doi:10.1109/ITNEC48623.2020.9085047

An Improved Flow Deviation Method for the Maximum Concurrent Flow Problem

Yanxiang Chen
, Yu Zhang
, Mengze Yuan

School of Information and Electronics

Beijing Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Citations (Scopus)

Abstract

The maximum concurrent flow problem (MCFP) is a multicommodity flow problem in which every pair of vertices can send and receive flow concurrently. The objective of MCFP is to find a maximum throughput and the flow corresponding to the throughput under a set of capacity constraints. We present an improved version of the Flow Deviation Method for the maximum concurrent flow problem, which was first presented by Daniel Bienstock and Olga Raskina in 2000. The algorithm is based on linear programming formulation involving Frank-Wolfe procedure and minimum-cost flow problem. The correctness of the algorithm is strictly proved and the performance is evaluated under several networks of different sizes.

Original language	English
Title of host publication	Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020
Editors	Bing Xu, Kefen Mou
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1179-1182
Number of pages	4
ISBN (Electronic)	9781728143903
DOIs	https://doi.org/10.1109/ITNEC48623.2020.9085047
Publication status	Published - Jun 2020
Event	4th IEEE Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020 - Chongqing, China Duration: 12 Jun 2020 → 14 Jun 2020

Publication series

Name	Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020

Conference

Conference	4th IEEE Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020
Country/Territory	China
City	Chongqing
Period	12/06/20 → 14/06/20

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Keywords

flow-deviation algorithm
maximum concurrent flow problem
multicommodity flow

Access to Document

10.1109/ITNEC48623.2020.9085047

Cite this

Chen, Y., Zhang, Y., & Yuan, M. (2020). An Improved Flow Deviation Method for the Maximum Concurrent Flow Problem. In B. Xu, & K. Mou (Eds.), Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020 (pp. 1179-1182). Article 9085047 (Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ITNEC48623.2020.9085047

Chen, Yanxiang ; Zhang, Yu ; Yuan, Mengze. / An Improved Flow Deviation Method for the Maximum Concurrent Flow Problem. Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020. editor / Bing Xu ; Kefen Mou. Institute of Electrical and Electronics Engineers Inc., 2020. pp. 1179-1182 (Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020).

@inproceedings{6e2134a4326b49059045d40fb0af99a8,

title = "An Improved Flow Deviation Method for the Maximum Concurrent Flow Problem",

abstract = "The maximum concurrent flow problem (MCFP) is a multicommodity flow problem in which every pair of vertices can send and receive flow concurrently. The objective of MCFP is to find a maximum throughput and the flow corresponding to the throughput under a set of capacity constraints. We present an improved version of the Flow Deviation Method for the maximum concurrent flow problem, which was first presented by Daniel Bienstock and Olga Raskina in 2000. The algorithm is based on linear programming formulation involving Frank-Wolfe procedure and minimum-cost flow problem. The correctness of the algorithm is strictly proved and the performance is evaluated under several networks of different sizes.",

keywords = "flow-deviation algorithm, maximum concurrent flow problem, multicommodity flow",

author = "Yanxiang Chen and Yu Zhang and Mengze Yuan",

note = "Publisher Copyright: {\textcopyright} 2020 IEEE.; 4th IEEE Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020 ; Conference date: 12-06-2020 Through 14-06-2020",

year = "2020",

month = jun,

doi = "10.1109/ITNEC48623.2020.9085047",

language = "English",

series = "Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1179--1182",

editor = "Bing Xu and Kefen Mou",

booktitle = "Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020",

address = "United States",

}

Chen, Y, Zhang, Y & Yuan, M 2020, An Improved Flow Deviation Method for the Maximum Concurrent Flow Problem. in B Xu & K Mou (eds), Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020., 9085047, Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020, Institute of Electrical and Electronics Engineers Inc., pp. 1179-1182, 4th IEEE Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020, Chongqing, China, 12/06/20. https://doi.org/10.1109/ITNEC48623.2020.9085047

An Improved Flow Deviation Method for the Maximum Concurrent Flow Problem. / Chen, Yanxiang; Zhang, Yu; Yuan, Mengze.
Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020. ed. / Bing Xu; Kefen Mou. Institute of Electrical and Electronics Engineers Inc., 2020. p. 1179-1182 9085047 (Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - An Improved Flow Deviation Method for the Maximum Concurrent Flow Problem

AU - Chen, Yanxiang

AU - Zhang, Yu

AU - Yuan, Mengze

PY - 2020/6

Y1 - 2020/6

N2 - The maximum concurrent flow problem (MCFP) is a multicommodity flow problem in which every pair of vertices can send and receive flow concurrently. The objective of MCFP is to find a maximum throughput and the flow corresponding to the throughput under a set of capacity constraints. We present an improved version of the Flow Deviation Method for the maximum concurrent flow problem, which was first presented by Daniel Bienstock and Olga Raskina in 2000. The algorithm is based on linear programming formulation involving Frank-Wolfe procedure and minimum-cost flow problem. The correctness of the algorithm is strictly proved and the performance is evaluated under several networks of different sizes.

AB - The maximum concurrent flow problem (MCFP) is a multicommodity flow problem in which every pair of vertices can send and receive flow concurrently. The objective of MCFP is to find a maximum throughput and the flow corresponding to the throughput under a set of capacity constraints. We present an improved version of the Flow Deviation Method for the maximum concurrent flow problem, which was first presented by Daniel Bienstock and Olga Raskina in 2000. The algorithm is based on linear programming formulation involving Frank-Wolfe procedure and minimum-cost flow problem. The correctness of the algorithm is strictly proved and the performance is evaluated under several networks of different sizes.

KW - flow-deviation algorithm

KW - maximum concurrent flow problem

KW - multicommodity flow

UR - https://www.scopus.com/pages/publications/85086261324

U2 - 10.1109/ITNEC48623.2020.9085047

DO - 10.1109/ITNEC48623.2020.9085047

M3 - Conference contribution

AN - SCOPUS:85086261324

T3 - Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020

SP - 1179

EP - 1182

BT - Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020

A2 - Xu, Bing

A2 - Mou, Kefen

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 4th IEEE Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020

Y2 - 12 June 2020 through 14 June 2020

ER -

Chen Y, Zhang Y, Yuan M. An Improved Flow Deviation Method for the Maximum Concurrent Flow Problem. In Xu B, Mou K, editors, Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020. Institute of Electrical and Electronics Engineers Inc. 2020. p. 1179-1182. 9085047. (Proceedings of 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC 2020). doi: 10.1109/ITNEC48623.2020.9085047

An Improved Flow Deviation Method for the Maximum Concurrent Flow Problem

Abstract

Publication series

Conference

UN SDGs

Keywords

Access to Document

Other files and links

Fingerprint

Cite this