Abstract
Given a network flow problem and a partition of its nodes into disjoint sets, we provide an aggregationβdisaggregation procedure that reformulates the problem as the union of network flow subproblems. Each subproblem either involves nodes in a set and their induced arcs or involves nodes and arcs between a pair of node sets. We present a hierarchical solution procedure, based on ficitious play of a twoβperson game, that solves each of the subproblems separately at each iteration, retains network structure of each of the subproblems across iterations, generates upper and lower bounds to the objective function value at each iteration, and converges asymptotically to the global optimal solution. We apply the algorithms to a logistics planning model involving uncapacitated transportation problems and provide computational results for problem reformulations based on two different partitions. When the procedure is initialized with a good initial solution, we observe excellent convergence rates for the optimality gap across iterations. We also discuss relationships between our approach and Benders' decomposition and provide an example comparing the objective function values of solutions generated by the two approaches.