Cadre De Génération De Programmation Linéaire Mixte En Nombres Entiers MILP-StuDio

MILP-StuDio est un cadre innovant de génération de programmation linéaire mixte en nombres entiers (MILP) proposé en 2024 par l'équipe du professeur Wang Jie (MIRA Lab) à l'Université des sciences et technologies de Chine. Le nom complet est Block Structure Decomposition, qui vise à générer des instances MILP de haute qualité en préservant la structure du bloc du problème pour améliorer la qualité de la solution des solveurs de recherche opérationnelle d'IA. Les résultats pertinents de l'article sont «MILP-StuDio : Génération d'instances MILP via la décomposition de la structure des blocs", a été accepté par NeurIPS 2024, une conférence de premier plan sur l'intelligence artificielle.

L'idée principale de MILP-StuDio est d'identifier la structure du bloc dans les matrices de coefficients de contrainte MILP (CCM) et de décomposer l'instance en unités de bloc, qui servent de base à la construction d'instances MILP. Sur cette base, trois opérateurs sont conçus pour construire de nouvelles instances en supprimant, remplaçant et ajoutant des unités de bloc dans l'instance d'origine, afin de générer des instances de tailles différentes.