Home > Research > Publications & Outputs > A bi-objective column generation algorithm for ...

Electronic data

  • Revised-15-1-2015

    Rights statement: This is the author’s review version of a work that was accepted for publication in European Journal of Operational Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in European Journal of Operational Research, 244, 2, 2015 DOI: 10.1016/j.ejor.2015.01.021

    Submitted manuscript, 423 KB, PDF document

    Available under license: CC BY-NC-ND: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Links

Text available via DOI:

View graph of relations

A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem. / Moradi, Siamak; Raith, Andrea; Ehrgott, Matthias.
In: European Journal of Operational Research, Vol. 244, No. 2, 16.07.2015, p. 369-378.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

Moradi, S, Raith, A & Ehrgott, M 2015, 'A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem', European Journal of Operational Research, vol. 244, no. 2, pp. 369-378. https://doi.org/10.1016/j.ejor.2015.01.021

APA

Vancouver

Moradi S, Raith A, Ehrgott M. A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem. European Journal of Operational Research. 2015 Jul 16;244(2):369-378. Epub 2015 Jan 29. doi: 10.1016/j.ejor.2015.01.021

Author

Moradi, Siamak ; Raith, Andrea ; Ehrgott, Matthias. / A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem. In: European Journal of Operational Research. 2015 ; Vol. 244, No. 2. pp. 369-378.

Bibtex

@article{dd9f9398f5b64db0a023f80a14d753d2,
title = "A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem",
abstract = "We present a column generation algorithm for solving the bi-objective multi-commodity minimum cost flow problem. This method is based on the bi-objective simplex method and Dantzig–Wolfe decomposition. The method is initialised by optimising the problem with respect to the first objective, a single objective multi-commodity flow problem, which is solved using Dantzig–Wolfe decomposition. Then, similar to the bi-objective simplex method, our algorithm iteratively moves from one non-dominated extreme point to the next one by finding entering variables with the maximum ratio of improvement of the second objective over deterioration of the first objective. Our method reformulates the problem into a bi-objective master problem over a set of capacity constraints and several single objective linear fractional sub-problems each over a set of network flow conservation constraints. The master problem iteratively updates cost coefficients for the fractional sub-problems. Based on these cost coefficients an optimal solution of each sub-problem is obtained. The solution with the best ratio objective value out of all sub-problems represents the entering variable for the master basis. The algorithm terminates when there is no entering variable which can improve the second objective by deteriorating the first objective. This implies that all non-dominated extreme points of the original problem are obtained. We report on the performance of the algorithm on several directed bi-objective network instances with different characteristics and different numbers of commodities.",
keywords = "Network flows, Bi-objective multi-commodity minimum cost flow problem, Dantzig–Wolfe decomposition, Column generation, Bi-objective simplex method",
author = "Siamak Moradi and Andrea Raith and Matthias Ehrgott",
note = " This is the author{\textquoteright}s review version of a work that was accepted for publication in European Journal of Operational Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in European Journal of Operational Research, 244, 2, 2015 DOI: 10.1016/j.ejor.2015.01.021",
year = "2015",
month = jul,
day = "16",
doi = "10.1016/j.ejor.2015.01.021",
language = "English",
volume = "244",
pages = "369--378",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier Science B.V.",
number = "2",

}

RIS

TY - JOUR

T1 - A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem

AU - Moradi, Siamak

AU - Raith, Andrea

AU - Ehrgott, Matthias

N1 - This is the author’s review version of a work that was accepted for publication in European Journal of Operational Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in European Journal of Operational Research, 244, 2, 2015 DOI: 10.1016/j.ejor.2015.01.021

PY - 2015/7/16

Y1 - 2015/7/16

N2 - We present a column generation algorithm for solving the bi-objective multi-commodity minimum cost flow problem. This method is based on the bi-objective simplex method and Dantzig–Wolfe decomposition. The method is initialised by optimising the problem with respect to the first objective, a single objective multi-commodity flow problem, which is solved using Dantzig–Wolfe decomposition. Then, similar to the bi-objective simplex method, our algorithm iteratively moves from one non-dominated extreme point to the next one by finding entering variables with the maximum ratio of improvement of the second objective over deterioration of the first objective. Our method reformulates the problem into a bi-objective master problem over a set of capacity constraints and several single objective linear fractional sub-problems each over a set of network flow conservation constraints. The master problem iteratively updates cost coefficients for the fractional sub-problems. Based on these cost coefficients an optimal solution of each sub-problem is obtained. The solution with the best ratio objective value out of all sub-problems represents the entering variable for the master basis. The algorithm terminates when there is no entering variable which can improve the second objective by deteriorating the first objective. This implies that all non-dominated extreme points of the original problem are obtained. We report on the performance of the algorithm on several directed bi-objective network instances with different characteristics and different numbers of commodities.

AB - We present a column generation algorithm for solving the bi-objective multi-commodity minimum cost flow problem. This method is based on the bi-objective simplex method and Dantzig–Wolfe decomposition. The method is initialised by optimising the problem with respect to the first objective, a single objective multi-commodity flow problem, which is solved using Dantzig–Wolfe decomposition. Then, similar to the bi-objective simplex method, our algorithm iteratively moves from one non-dominated extreme point to the next one by finding entering variables with the maximum ratio of improvement of the second objective over deterioration of the first objective. Our method reformulates the problem into a bi-objective master problem over a set of capacity constraints and several single objective linear fractional sub-problems each over a set of network flow conservation constraints. The master problem iteratively updates cost coefficients for the fractional sub-problems. Based on these cost coefficients an optimal solution of each sub-problem is obtained. The solution with the best ratio objective value out of all sub-problems represents the entering variable for the master basis. The algorithm terminates when there is no entering variable which can improve the second objective by deteriorating the first objective. This implies that all non-dominated extreme points of the original problem are obtained. We report on the performance of the algorithm on several directed bi-objective network instances with different characteristics and different numbers of commodities.

KW - Network flows

KW - Bi-objective multi-commodity minimum cost flow problem

KW - Dantzig–Wolfe decomposition

KW - Column generation

KW - Bi-objective simplex method

U2 - 10.1016/j.ejor.2015.01.021

DO - 10.1016/j.ejor.2015.01.021

M3 - Journal article

VL - 244

SP - 369

EP - 378

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -