A new strategy for the undirected two-commodity maximum flow problem

作者：Sedeno Noda A^*; Gonzalez Martin C; Alonso Rodriguez S

来源：Computational Optimization and Applications, 2010, 47(2): 289-305.

DOI：10.1007/s10589-008-9214-5

• Two-commodity flow
• Two-commodity maximum flow
• Biobjective two-commodity maximum flow

We address the two-commodity maximum flow problem on undirected networks. As a result of a change of variables, we introduce a new formulation that solves the problem through classical maximum flow techniques with only one-commodity. Therefore, a general strategy, based on this change of variables, is defined to deal with other undirected multi-commodity problems. Finally, we extend the single objective problem to a bicriteria environment. We show that the set of efficient solutions of the biobjective undirected two-commodity maximum flow problem is the set of alternative optimum solutions of the undirected two-commodity maximum flow problem. In addition, we prove that the set of efficient extreme points in the objective space has, at most, cardinality two.

• 出版日期2010-10