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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Levent ERİŞKİN
Formato:	article
Lenguaje:	EN
Publicado:	National Defense University Barbaros Naval Sciences and Engineering Institute Journal of Naval Science and Engineering 2021
Materias:	multicommodity network design problem lagrangean relaxation subgradient algorithm decomposition Naval Science V
Acceso en línea:	https://doaj.org/article/b3b68fa02cc84e4cb8c2fd0fe51722ca
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:b3b68fa02cc84e4cb8c2fd0fe51722ca
record_format	dspace
spelling	oai:doaj.org-article:b3b68fa02cc84e4cb8c2fd0fe51722ca2021-11-16T15:46:46ZA LAGRANGEAN RELAXATION-BASED SOLUTION APPROACH FOR MULTICOMMODITY NETWORK DESIGN PROBLEM WITH CAPACITY VIOLATIONS1304-2025https://doaj.org/article/b3b68fa02cc84e4cb8c2fd0fe51722ca2021-11-01T00:00:00Zhttps://dergipark.org.tr/tr/download/article-file/1749652https://doaj.org/toc/1304-2025In 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.Levent ERİŞKİNNational Defense University Barbaros Naval Sciences and Engineering Institute Journal of Naval Science and Engineeringarticlemulticommodity network design problemlagrangean relaxationsubgradient algorithmdecompositionNaval ScienceVENJournal of Naval Science and Engineering, Vol 17, Iss 2, Pp 241-263 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	multicommodity network design problem lagrangean relaxation subgradient algorithm decomposition Naval Science V
spellingShingle	multicommodity network design problem lagrangean relaxation subgradient algorithm decomposition Naval Science V Levent ERİŞKİN A LAGRANGEAN RELAXATION-BASED SOLUTION APPROACH FOR MULTICOMMODITY NETWORK DESIGN PROBLEM WITH CAPACITY VIOLATIONS
description	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.
format	article
author	Levent ERİŞKİN
author_facet	Levent ERİŞKİN
author_sort	Levent ERİŞKİN
title	A LAGRANGEAN RELAXATION-BASED SOLUTION APPROACH FOR MULTICOMMODITY NETWORK DESIGN PROBLEM WITH CAPACITY VIOLATIONS
title_short	A LAGRANGEAN RELAXATION-BASED SOLUTION APPROACH FOR MULTICOMMODITY NETWORK DESIGN PROBLEM WITH CAPACITY VIOLATIONS
title_full	A LAGRANGEAN RELAXATION-BASED SOLUTION APPROACH FOR MULTICOMMODITY NETWORK DESIGN PROBLEM WITH CAPACITY VIOLATIONS
title_fullStr	A LAGRANGEAN RELAXATION-BASED SOLUTION APPROACH FOR MULTICOMMODITY NETWORK DESIGN PROBLEM WITH CAPACITY VIOLATIONS
title_full_unstemmed	A LAGRANGEAN RELAXATION-BASED SOLUTION APPROACH FOR MULTICOMMODITY NETWORK DESIGN PROBLEM WITH CAPACITY VIOLATIONS
title_sort	lagrangean relaxation-based solution approach for multicommodity network design problem with capacity violations
publisher	National Defense University Barbaros Naval Sciences and Engineering Institute Journal of Naval Science and Engineering
publishDate	2021
url	https://doaj.org/article/b3b68fa02cc84e4cb8c2fd0fe51722ca
work_keys_str_mv	AT leventeriskin alagrangeanrelaxationbasedsolutionapproachformulticommoditynetworkdesignproblemwithcapacityviolations AT leventeriskin lagrangeanrelaxationbasedsolutionapproachformulticommoditynetworkdesignproblemwithcapacityviolations
_version_	1718426322926043136

A LAGRANGEAN RELAXATION-BASED SOLUTION APPROACH FOR MULTICOMMODITY NETWORK DESIGN PROBLEM WITH CAPACITY VIOLATIONS

Ejemplares similares