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

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.