A new strategy for the undirected two-commodity maximum flow problem |
| |
Authors: | A Sedeño-Noda C González-Martín S Alonso-Rodríguez |
| |
Institution: | (3) Dept. Industrial and Systems Engin. Univ. Florida, Gainesville, FL 32611, USA;(4) Sloan School of Management and Dept. Electrical Engin. and Computer Sci. Massachusetts Inst. Technol., Cambridge, MA 02139, USA;(5) Sloan School of Management Massachusetts Inst. Technol., Cambridge, MA 02139, USA |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|