Lagrangean-based decomposition algorithms for multicommodity network design problems with penalized constraints

This paper discusses problems in the context of multicommodity network design where the additional constraints (such as capacity), rather than being imposed in a strict manner, are allowed to be violated at the expense of additional penalty costs. Such penalized cost structures allow these constraints to be treated as utilization targets and provide a better modelling framework in terms of strategic or tactical level planning of network design, especially in freight transportation systems. However, due to penalized costs, these problems are generally in the form of a nonlinear integer multicommodity network problem. This paper presents two algorithms based on Lagrangean relaxation and decomposition for the solution of such problems. The first is through relaxing flow constraints that results in an arc decomposition, and the second relies upon dualizing the capacity constraints that result in a flow decomposition. It is shown that nonlinearities in the decomposed substructures can be handled in a very efficient manner. Arc decomposition is shown, through computational experiments, to have better convergence properties. Through the proposed algorithms, reasonably good solutions can be obtained for these problems where publicly available state-of-the-art nonlinear optimization codes fail to identify feasible solutions