Permutation problems have captured the attention of the combinatorial optimization community for decades due to the challenge they pose. Although their solutions are naturally encoded as permutations, in each problem, the information to be used to optimize them can vary substantially. In this article, we consider the Quadratic Assignment Problem (QAP) as a case study, and propose using Doubly Stochastic Matrices (DSMs) under the framework of Estimation of Distribution Algorithms. To that end, we design efficient learning and sampling schemes that enable an effective iterative update of the probability model. Conducted experiments on commonly adopted benchmarks for the QAP prove doubly stochastic matrices to be preferred to other four models for permutations, both in terms of effectiveness and computational efficiency. Moreover, additional analyses performed on the structure of the QAP and the Linear Ordering Problem (LOP) show that DSMs are good to deal with assignment problems, but they have interesting capabilities to deal also with ordering problems such as the LOP. The article concludes with a description of the potential uses of DSMs for other optimization paradigms, such as genetic algorithms or model-based gradient search.

On the use of the Doubly Stochastic Matrix models for the Quadratic Assignment Problem

Santucci, Valentino
;
2025-01-01

Abstract

Permutation problems have captured the attention of the combinatorial optimization community for decades due to the challenge they pose. Although their solutions are naturally encoded as permutations, in each problem, the information to be used to optimize them can vary substantially. In this article, we consider the Quadratic Assignment Problem (QAP) as a case study, and propose using Doubly Stochastic Matrices (DSMs) under the framework of Estimation of Distribution Algorithms. To that end, we design efficient learning and sampling schemes that enable an effective iterative update of the probability model. Conducted experiments on commonly adopted benchmarks for the QAP prove doubly stochastic matrices to be preferred to other four models for permutations, both in terms of effectiveness and computational efficiency. Moreover, additional analyses performed on the structure of the QAP and the Linear Ordering Problem (LOP) show that DSMs are good to deal with assignment problems, but they have interesting capabilities to deal also with ordering problems such as the LOP. The article concludes with a description of the potential uses of DSMs for other optimization paradigms, such as genetic algorithms or model-based gradient search.
2025
Doubly Stochastic Matrix
Estimation of Distribution Algorithm
Fourier transform
Ordering vs. Assignment Problems
Quadratic Assignment Problem
File in questo prodotto:
File Dimensione Formato  
article__On_the_use_of_the_Doubly_Stochastic_Matrix_models_.pdf

non disponibili

Descrizione: Versione Editoriale
Tipologia: Versione Editoriale (PDF)
Licenza: Copyright dell'editore
Dimensione 8.97 MB
Formato Adobe PDF
8.97 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
_ECJ___Major_Revision__On_the_use_of_DSMs.pdf

accesso aperto

Descrizione: Preprint
Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 5.29 MB
Formato Adobe PDF
5.29 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12071/46188
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact