A LAGRANGEAN RELAXATION-BASED SOLUTION APPROACH FOR MULTICOMMODITY NETWORK DESIGN PROBLEM WITH CAPACITY VIOLATIONS
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 additio...
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
National Defense University Barbaros Naval Sciences and Engineering Institute Journal of Naval Science and Engineering
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/b3b68fa02cc84e4cb8c2fd0fe51722ca |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | 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. |
|---|