Résolution exacte du problème de partitionnement de données avec minimisation de variance sous contraintes de cardinalité par programmation par contraintes

Le partitionnement de données représente une procédure destinée à regrouper un ensemble d'observations dans plusieurs sous ensembles homogènes et/ou bien séparés. L'idée derrière une telle activité est de simplifier l'extraction d'information utile en étudiant les groupes résultants plutôt que les observations elles-mêmes. Cela dit, plusieurs situations appellent à ce que la solution générée respecte un ensemble de contraintes données. En particulier, on exige parfois que les groupes résultants comportent un nombre prédéfini d'éléments. On parle de partitionnement avec contraintes de cardinalité. On présente alors, dans ce travail, une approche de résolution exacte pour le partitionnement de données avec minimisation de la variance sous contraintes de cardinalité. En utilisant le paradigme de la Programmation par Contraintes, on propose d'abord un modèle adéquat du problème selon celui-ci. Ensuite, on suggère à la fois une stratégie de recherche rehaussée ainsi que deux algorithmes de filtrage. Ces outils ainsi développés tirent avantage de la structure particulière du problème afin de naviguer l'espace de recherche de façon efficace, à la recherche d'une solution globalement optimale. Des expérimentations pratiques montrent que notre approche procure un avantage important par rapport aux autres méthodes exactes existantes lors de la résolution de plusieurs exemplaires du problème.