D.C. OPTIMIZATION METHODS FOR SOLVING MINIMUM MAXIMAL NETWORK FLOW PROBLEM

Abstract

We consider the minimum maximal flow problem, i.e., minimizing the flow value among maximal flow, which is an NP-hard problem. This problem is formulated as an optimization problem over the Pareto set of a linear vector program. We use a d.c. optimization formulation of the problem to obtain solution methods for the problem. Two solution approaches are described. The first one is a global optimization method based upon a branch-and-bound strategy. The second is a local search technique based upon a d.c. optimization algorithm.