 |
Une stratégie de résolution (SR) au sein d'un solveur de Programmation Linéaire en Nombres Entiers Mixtes (PLNEM) peut être définie par un ou plusieurs composants qui prennent des décisions au cours de la résolution d'un problème jusqu'a son optimalité. Avec la croissance exponentielle de l'utilisation des méthodes d'apprentissage automatique (AA), il est désormais possible de formaliser une SR comme un problème de classification et de l'aborder via des techniques d'AA. Cependant, les modèles actuels, bien qu'efficaces sur des ensembles homogènes et préalablement définis, rencontrent de grandes difficultés lorsqu'il s'agit de généraliser à des instances présentant des structures variées ou appartenant à des classes différentes. Ainsi, un écart important subsiste avant que ces méthodes puissent être utilisées de manière fiable dans des solveurs polyvalents.
L'introduction d'une métrique de distance entre instances constitue une étape clé pour améliorer la généralisation de ces méthodes. Une telle métrique permettrait de quantifier l'hétérogénéité des ensembles d'instances PLNEM utilisés pour l'évaluation des SR, offrant ainsi un indicateur rigoureux de la généralisabilité des modèles. Les résultats des méthodes actuelles montrent clairement qu'elles sont performantes sur des ensembles homogènes, mais inefficaces lorsqu'on considère l'ensemble de l'espace PLNEM. En conséquence, l'utilisation d'une distance pour segmenter l'espace des PLNEM en groupes homogènes et développer une SR spécifique à chaque groupe — créant ainsi une approche de type portfolio — offrirait une solution générale pour l'application des SR basées sur l'AA.
Plusieurs approches ont été proposées pour mesurer la similarité entre instances MILP. L'approche \emph{ISS}~\cite{steever_image-based_2022} encode les matrices de contraintes en images analysées par des autoencodeurs et calcule la distance des répresentation, mais reste sensible à l'ordre des contraintes. La méthode \emph{GNN}~\cite{steever_graph-based_2024} est un classifieur basé sur les graphes ce qui permet une représentation invariante et permet d'améliorer la généralisation au sein de classes préalablement définies, mais nécessitent un entraînement supervisé et restent limitées à ces classes. Dasn la bibliothèque MIPLIB 2017, la distance \emph{Feat}~\cite{gleixner_miplib_2021} propose plus de 100 caractéristiques extraites manuellement pour comparer les instances dans un espace de grande dimension, mais ce procédé manque de fondement théorique pour la sélection et la normalisation des caractéristiques. %Dans l'ensemble, ces méthodes montrent l'intérêt de quantifier la similarité entre MILP, mais elles demeurent limitées soit par leur dépendance à des classes prédéfinies, soit par leur sensibilité à la taille et à l'ordre des éléments, soulignant le besoin d'une approche plus rigoureuse et mathématiquement fondée.
Pour répondre à ces limitations, nous proposons une mesure de distance entre instances MILP directement dérivée de leur formulation mathématique, sans nécessiter d'entraînement supervisé; ce résumé étendu est la version réduite de~\cite{maudet_distance_2025}. Chaque variable, coefficient et terme du second membre est catégorisé, ce qui permet une représentation d'une contrainte en fonction de la proportion d'apparition de la même paire variable-coefficient, et par extension, une représentation d'une instance par proportion de contraintes similaires. Cette représentation est indépendante de la taille de l'instance, permettant la comparaison d'instances de dimensions différentes. La distance entre contraintes est quantifiée à l'aide de la distance du cantonnier~\cite{rubner_earth_2000}, qui mesure la quantité de transformation nécessaire pour convertir une contrainte en une autre. Ce principe est ensuite étendu pour définir la distance entre instances.
Notre experience évalue la capacité d'une métrique à identifier comme similaires les instances appartenant à la même classe, en considérant cinq classes d'instances~\cref{striplib_1}. Dans l'étude complète~\cite{maudet_distance_2025}, l'évaluation est réalisée sur 19 classes, avec un complément sur des ensembles issus de sous-classes d'instances. Nous comparons notre méthode dans différents réglages : $\cancel{\alpha}$ sans considération du type de poids devant les variables, $\cancel{\beta}$ sans considération du type de variable, $\cancel{\gamma}$ sans considération du type de second membre, $\cancel{\zeta}$ sans considération de la fonction objectif, $\emptyset E$ pour la version exacte et $\emptyset$ pour la version approximative. Les résultats montrent que la prise en compte de l'ensemble des composantes du problème est cruciale pour évaluer correctement la similarité entre instances. De plus, la version approximative présente moins de variations de temps de calcul et est en moyenne 200 fois plus rapide tout en produisant des résultats comparables à la version exacte. Par rapport aux autres méthodes de référence non supervisées présentés plus haut (\emph{ISS} et \emph{Feat}), notre approche les surpasse largement et atteint des performances similaires à celles du \emph{GNN} supervisé, spécifiquement entraîné sur les classes considérées.
\begin{table}[htbp]
\centering
\footnotesize
\setlength{\tabcolsep}{4.5pt}
\begin{tabular}{c|c|c|c|c|c|c|c|c|c}
& \multicolumn{6}{c|}{Formal}& Feat&ISS&GNN\\
\hline
&$\cancel{\alpha}$&$\cancel{\beta}$&$\cancel{\gamma}$&$\cancel{\zeta}$&$\emptyset E$&$\emptyset$\\
bpp&\cellcolor[cmyk]{0.037,0.963,1.0,0.241} 42&\cellcolor[cmyk]{0.16,0.84,1.0,0.21} 47&\cellcolor[cmyk]{0.204,0.796,1.0,0.199} 49&\cellcolor[cmyk]{0.0,1.0,1,0.25} 26&\cellcolor[cmyk]{0.167,0.833,1.0,0.208} 47&\cellcolor[cmyk]{0.16,0.84,1.0,0.21} 47&\cellcolor[cmyk]{0.0,1.0,1,0.25} 27&\cellcolor[cmyk]{0.0,1.0,1,0.25} 32&\cellcolor[cmyk]{1.0,0.0,1,0.0} 81\\
bp2&\cellcolor[cmyk]{0.25,0.75,1.0,0.188} 62&\cellcolor[cmyk]{0.415,0.585,1.0,0.146} 71&\cellcolor[cmyk]{1.0,0.0,1,0.0} 100&\cellcolor[cmyk]{0.415,0.585,1.0,0.146} 71&\cellcolor[cmyk]{0.91,0.09,1.0,0.023} 95&\cellcolor[cmyk]{0.9,0.1,1.0,0.025} 95&\cellcolor[cmyk]{0.0,1.0,1,0.25} 24&\cellcolor[cmyk]{0.04,0.96,1.0,0.24} 52&\cellcolor[cmyk]{1.0,0.0,1,0.0} 100\\
bif&\cellcolor[cmyk]{1.0,0.0,1,0.0} 50&\cellcolor[cmyk]{0.76,0.24,1.0,0.06} 44&\cellcolor[cmyk]{1.0,0.0,1,0.0} 50&\cellcolor[cmyk]{1.0,0.0,1,0.0} 50&\cellcolor[cmyk]{1.0,0.0,1,0.0} 50&\cellcolor[cmyk]{1.0,0.0,1,0.0} 50&\cellcolor[cmyk]{0.0,1.0,1,0.25} 21&\cellcolor[cmyk]{0.28,0.72,1.0,0.18} 32&\cellcolor[cmyk]{0.72,0.28,1.0,0.07} 43\\
clp&\cellcolor[cmyk]{0.694,0.306,1.0,0.076} 54&\cellcolor[cmyk]{0.851,0.149,1.0,0.037} 59&\cellcolor[cmyk]{0.161,0.839,1.0,0.21} 37&\cellcolor[cmyk]{1.0,0.0,1,0.0} 64&\cellcolor[cmyk]{0.812,0.188,1.0,0.047} 57&\cellcolor[cmyk]{0.773,0.227,1.0,0.057} 56&\cellcolor[cmyk]{0.0,1.0,1,0.25} 28&\cellcolor[cmyk]{0.0,1.0,1,0.25} 12&\cellcolor[cmyk]{0.161,0.839,1.0,0.21} 37\\
col&\cellcolor[cmyk]{1.0,0.0,1,0.0} 40&\cellcolor[cmyk]{1.0,0.0,1,0.0} 40&\cellcolor[cmyk]{1.0,0.0,1,0.0} 40&\cellcolor[cmyk]{1.0,0.0,1,0.0} 40&\cellcolor[cmyk]{1.0,0.0,1,0.0} 40&\cellcolor[cmyk]{1.0,0.0,1,0.0} 40&\cellcolor[cmyk]{0.363,0.637,1.0,0.159} 27&\cellcolor[cmyk]{0.8,0.2,1.0,0.05} 36&\cellcolor[cmyk]{1.0,0.0,1,0.0} 40\\
\end{tabular}
\caption{Évaluation de différentes mesures de similarité pour identifier si des instances appartiennent à la même classe de problème.}
\label{striplib_1}
\end{table}
En conclusion, nous avons présenté une distance formelle pour les MILP, constituant un outil fondamental pour l'analyse d'instances et l'intégration dans des pipelines d'AA pour les SR. Les travaux futurs incluent l'exploration d'une approche de type portfolio, consistant à créer plusieurs groupes d'instances, chacun associé à une SR spécifique développée par AA, afin que pour une nouvelle instance, la SR la plus adaptée puisse être automatiquement sélectionnée.
\subsubsection*{Acknowledgements}
Cette recherche a été financée par l'ANR France (ANR-22-CE46-0011) et le FNR Luxembourg (INTER/ANR/22/17133848) via le projet UltraBO.
