Modeling and analysis of multicommodity network flows via goal programming

In this work goal programming is used to solve a minimum cost multicommodity network flow problem with multiple objectives. The network consists of: linear objective function, linear cost arcs, fixed arc and node capabilities, and specific origin–destination pairs for each commodity. This suggests a classic linear program. When properly modeled, Lagrangian relaxation, Dantzig–Wolfe decomposition and network flow techniques may be employed to exploit the pure network. Lagrangian relaxation captures the essence of the pure network flow problem as a master problem and sub-problems. The relaxation may be optimized directly, or be decomposed into subproblems, one for each commodity with each subproblem a minimum cost single commodity network flow problem. Post-optimality analyses, via sensitivity analysis and parametric analysis, provide a variety of options under which the robustness of the optimal solution may be investigated.