A linear formulation with O(n2) variables for quadratic assignment problems with Manhattan distance matrices

We present O(n2)an integer linear formulation that uses the so-called “distance variables” to solve the quadratic assignment problem (QAP). The formulation performs particularly well for problems with Manhattan distance matrices. It involves O(n2) variables. Valid equalities and inequalities are pro...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Serigne Gueye, Philippe Michelon
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2015
Materias:	90-XX 90Cxx 65K05 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/7c02ee14063840faa708442c3aa2a222
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:7c02ee14063840faa708442c3aa2a222
record_format	dspace
spelling	oai:doaj.org-article:7c02ee14063840faa708442c3aa2a2222021-12-02T05:00:43ZA linear formulation with O(n2) variables for quadratic assignment problems with Manhattan distance matrices2192-440610.1007/s13675-014-0033-4https://doaj.org/article/7c02ee14063840faa708442c3aa2a2222015-05-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S219244062100040Xhttps://doaj.org/toc/2192-4406We present O(n2)an integer linear formulation that uses the so-called “distance variables” to solve the quadratic assignment problem (QAP). The formulation performs particularly well for problems with Manhattan distance matrices. It involves O(n2) variables. Valid equalities and inequalities are proposed divided into two families. First, a family of inequalities valid for any quadratic assignment problems, and second, a family valid only for problems with Manhattan distance matrices, for which we exploit metric properties, as well as an algebraic characterization that Mittelman and Peng (SIAM J Opt 2010:20(6), 3408–3426, 2010) recently proved. We numerically tested the lower bound provided by the linear relaxation using instances of the quadratic assignment problem library (QAPLIB) with randomly generated distance matrices, as well as Manhattan distance matrices. Our results are compared with the best known lower bounds. For Manhattan distance matrices, the formulation gives a very competitive lower bound in a short computational time, improving seven best lower bounds of QAPLIB instances for which no optimality proofs exist.Serigne GueyePhilippe MichelonElsevierarticle90-XX90Cxx65K05Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 3, Iss 2, Pp 79-110 (2015)
institution	DOAJ
collection	DOAJ
language	EN
topic	90-XX 90Cxx 65K05 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90-XX 90Cxx 65K05 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Serigne Gueye Philippe Michelon A linear formulation with O(n2) variables for quadratic assignment problems with Manhattan distance matrices
description	We present O(n2)an integer linear formulation that uses the so-called “distance variables” to solve the quadratic assignment problem (QAP). The formulation performs particularly well for problems with Manhattan distance matrices. It involves O(n2) variables. Valid equalities and inequalities are proposed divided into two families. First, a family of inequalities valid for any quadratic assignment problems, and second, a family valid only for problems with Manhattan distance matrices, for which we exploit metric properties, as well as an algebraic characterization that Mittelman and Peng (SIAM J Opt 2010:20(6), 3408–3426, 2010) recently proved. We numerically tested the lower bound provided by the linear relaxation using instances of the quadratic assignment problem library (QAPLIB) with randomly generated distance matrices, as well as Manhattan distance matrices. Our results are compared with the best known lower bounds. For Manhattan distance matrices, the formulation gives a very competitive lower bound in a short computational time, improving seven best lower bounds of QAPLIB instances for which no optimality proofs exist.
format	article
author	Serigne Gueye Philippe Michelon
author_facet	Serigne Gueye Philippe Michelon
author_sort	Serigne Gueye
title	A linear formulation with O(n2) variables for quadratic assignment problems with Manhattan distance matrices
title_short	A linear formulation with O(n2) variables for quadratic assignment problems with Manhattan distance matrices
title_full	A linear formulation with O(n2) variables for quadratic assignment problems with Manhattan distance matrices
title_fullStr	A linear formulation with O(n2) variables for quadratic assignment problems with Manhattan distance matrices
title_full_unstemmed	A linear formulation with O(n2) variables for quadratic assignment problems with Manhattan distance matrices
title_sort	linear formulation with o(n2) variables for quadratic assignment problems with manhattan distance matrices
publisher	Elsevier
publishDate	2015
url	https://doaj.org/article/7c02ee14063840faa708442c3aa2a222
work_keys_str_mv	AT serignegueye alinearformulationwithon2variablesforquadraticassignmentproblemswithmanhattandistancematrices AT philippemichelon alinearformulationwithon2variablesforquadraticassignmentproblemswithmanhattandistancematrices AT serignegueye linearformulationwithon2variablesforquadraticassignmentproblemswithmanhattandistancematrices AT philippemichelon linearformulationwithon2variablesforquadraticassignmentproblemswithmanhattandistancematrices
_version_	1718400837781291008

A linear formulation with O(n2) variables for quadratic assignment problems with Manhattan distance matrices

Ejemplares similares