| Popis: |
In this study, we formulate and compare two different Lagrangean relaxation-based decompositions for multicommodity network problems with penalized constraints. These problems are different versions of capacitated multicommodity network problems where capacity constraints can be violated for additional penalty costs. These costs are reflected as nonlinear terms in the objective function; hence, these problems turn out to be nonlinear mixed-integer optimization problems. To the best of our knowledge, there is no exact solution algorithm for this type of problem. We propose two kinds of Lagrangean relaxation-based decompositions and solve these problems with the subgradient algorithm. The resulting subproblems are easy to solve and the proposed algorithms can reach reasonable solutions where CPLEX solver cannot even find a solution. In the study, we also conduct a computational analysis where we compare two relaxations over various performance measures. Even though two relaxations present similar performances in terms of computation times and the number of iterations, we observed that Relaxation 1 statistically outperforms Relaxation 2. |
