Problème d'affectation quadratique

Le problème d'affectation quadratique est l'un des problèmes fondamentaux d'optimisation combinatoire dans le domaine de l'optimisation ou de la recherche opérationnelle en mathématiques ; il appartient à la catégorie des problèmes de l'emplacement d'installation. Il a été initialement proposé par Tjalling Koopmans et Martin J. Beckmann.

Ce problème modélise la situation suivante, tirée de la vie réelle :

Soit un ensemble de n installations et un ensemble de n emplacements. Pour chaque paire d'emplacements, une distance est spécifiée, et pour chaque paire d'installations, un poids ou un flux est spécifié (par exemple, la quantité de marchandises transportées entre les deux installations). Le problème consiste à affecter toutes les installations à des emplacements différents, dans le but de minimiser la somme des distances multipliées par les flux correspondants.

L'énoncé du problème ressemble à celui du problème d'affectation, sauf que la fonction objectif est exprimée en termes d'inégalités quadratiques, d'où son nom.

Définition mathématique formelle

La définition formelle du problème d'affectation quadratique est la suivante:

Étant donné un entier positif $n$ et $n^{4}$ coefficients de coût $\{c_{i,j,p,q}\}$, déterminez la matrice $n\times n$ $[x_{ij}]$ qui minimise la fonction objectif.

$\sum _{i,j}\sum _{p,q}c_{i,j,p,q}x_{i,j}x_{p,q}$

compte tenu des contraintes

$\sum _{j}x_{i,j}=\sum _{i}x_{i,j}=1,$

$x_{ij}\in \{0,1\}$

Formulation de Koopmans-Beckmann

Le problème d'affectation quadratique a été initialement défini par Tjalling Koopmans et Martin J. Beckmann sous la forme suivante.

Étant donné deux matrices carrées D et T, trouvez la matrice de permutation X qui minimise le produit scalaire double de T avec X. $A=XDX^{\intercal }$.

Autrement dit, étant donné D et T, trouvez $\{x_{ij}\}_{1\leq i,j\leq n}$ afin de

${\begin{aligned}{\text{minimiser}}\quad &\sum _{1\leq i,j\leq n}a_{ij}t_{ij}\\{\text{compte tenu de}}\quad &\sum _{1\leq k\leq n}x_{ik}=\sum _{1\leq k\leq n}x_{jk}=1,\\&x_{ij}\in \{0,1\}.\end{aligned}}$

En utilisant la terminologie ci-dessus, la matrice D répertorie les distances ($d_{ij}$ indique la distance de l'emplacement i à l'emplacement j) et T les flux ($t_{ij}$ indique la quantité de marchandises à transporter de l'installation i à l'installation j). La matrice de permutation X représente une affectation des installations aux emplacements ($x_{ij}$ vaut 1 uniquement si l'installation i est située à l'emplacement j).

Intuitivement, la fonction objectif favorise le regroupement des installations entre lesquelles les flux sont importants.

Complexité computationnelle

Ce problème est NP-difficile ; il n’existe donc aucun algorithme connu permettant de le résoudre en temps polynomial, et même des instances de petite taille peuvent nécessiter un temps de calcul important. Il a également été démontré que ce problème ne dispose d’aucun algorithme d’approximation fonctionnant en temps polynomial pour un facteur (constant) quelconque, à moins que P = NP. Le problème du voyageur de commerce peut être considéré comme un cas particulier du problème d'affectation quadratique si l’on suppose que les flux relient toutes les installations uniquement le long d’un seul anneau, que tous les flux ont la même valeur non nulle (constante) et que toutes les distances sont égales aux distances respectives de l’instance du problème du voyageur de commerce. D'autres problèmes d’optimisation combinatoire classiques peuvent être décrits sous cette forme.

Applications

Outre sa formulation initiale relative à l'implantation d'usines, le problème d'affectation quadratique est un modèle mathématique permettant de résoudre le problème du placement de composants électroniques interconnectés sur un circuit imprimé ou une puce électronique, qui s'inscrit dans la phase de placement-routage de la conception assistée par ordinateur dans l'industrie électronique.

Le problème d'affectation quadratique a également été utilisé pour modéliser le coût de la disposition des caractères sur un clavier. Dans ce cas, les emplacements correspondent aux touches du clavier et leurs distances par paires correspondent au temps nécessaire pour appuyer sur une paire de touches donnée. Les éléments sont les caractères et leurs poids sont proportionnels à la fréquence d'apparition de la paire de caractères donnée dans un corpus de textes. Ce type de modèle a été utilisé lors de la conception de la norme relative au clavier AZERTY (NF Z71-300).

Articles connexes

• Problème d'affectation des goulots d'étranglement de type quadratique

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Quadratic assignment problem » (voir la liste des auteurs).

Bibliographie

• Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979 (ISBN 0-7167-1045-5) A2.5: ND43, pg.218.
• (en) Miguel Anjos, E Çela, SE Karisch et F Rendl, QAPLIB - A Quadratic Assignment Problem Library - Problem instances and solutions, 2022 (DOI 10.7488/DS/3428, lire en ligne)