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 journalJournal articlepeer-review

Published
Close
<mark>Journal publication date</mark>16/07/2015
<mark>Journal</mark>European Journal of Operational Research
Issue number2
Volume244
Number of pages10
Pages (from-to)369-378
Publication StatusPublished
Early online date29/01/15
<mark>Original language</mark>English

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.

Bibliographic note

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