Data-driven decomposition and constraint customization for combinatorial optimization

Récemment, on a assisté à une montée en puissance des méthodes basées sur les données dans le domaine de l’optimisation. En général, la construction de modèles mathématiques pour un système implique d’obtenir des informations sur le système pour le modéliser. D’une part, l’émergence du big data motive l’utilisation des méthodes basées sur les données pour trouver les modèles latents des données, estimer les paramètres et construire des modèles d’optimisation. D’autre part, comme la disponibilité des données conduit à des modèles d’optimisation plus sophistiqués, il est nécessaire de développer des méthodes basées sur les données pour s’attaquer à la complexité de résolution de ces problèmes d’optimisation. Certaines études dans ce domaine s’appuient sur des techniques axées sur les données pour évaluer les paramètres des problèmes d’optimisation afin de détecter automatiquement les modèles sous-jacents. Elles tentent d’explorer la structure de la matrice des coûts ou de la matrice des contraintes et de trouver des modèles dans une classe spécifique de problèmes. L’utilisation de l’apprentissage automatique pour traiter directement les instances d’un problème d’optimisation est une autre application des méthodes basées sur les données dans le domaine de l’optimisation. La résolution de modèles d’optimisation par des approches d’apprentissage automatique et l’incorporation du problème d’optimisation dans l’étape d’apprentissage sont quelques exemples dans ce domaine. Dans cette thèse, nous tirons parti des techniques basées sur les données pour étudier et développer des méthodes de résolution de certains problèmes d’optimisation difficiles à résoudre. Les méthodes de décomposition sont utilisées dans la littérature de l’optimisation depuis de nombreuses années comme une alternative pour traiter les problèmes de grandes dimensions. La décomposition consiste à diviser un problème en sous-problèmes plus petits qui peuvent être résolus séparément. Dans deux chapitres de ce travail, nous étudions la décomposabilité de certains problèmes de Programmation Quadratique Binaire avec des contraintes linéaires par le biais d’une approche basée sur des méthodes basées sur les données. Nous étudions la structure des données relatives aux coûts quadratiques des Programmes Quadratiques Binaires et exploitons les modèles spécifiques liés au type de problème pour reformuler et convexifier les problèmes, et utiliser la décomposition pour les résoudre. La Programmation Quadratique Binaire est une classe de problèmes Optimisation Combinatoire avec des variables binaires et des fonctions objectifs quadratiques. Dans la première étude de la thèse, nous étudions la généralisation de la “reformulation en étoile” introduite pour le Problème d’Arbre Quadratique Adjacent Minimal dans la littérature pour d’autres problèmes de Programmation Quadratique Binaire simplement adjacents. Nous considérons deux problèmes de cette classe, le Problème d’Assignation Adjacent Semi Quadratique et le problème de Suivi d’Objets Multiples en vision artificielle pour démontrer l’efficacité de la reformulation en étoile. La deuxième étude de cette thèse est consacré à la proposition d’un cadre unifié combinant la reformulation en étoile et une approche de division des coûts pour reformuler les problèmes de Programmation Quadratique Binaire généraux. Dans cette approche, nous exploitons la structure du coût quadratique basée sur les coûts adjacents et les coûts non adjacents et fournissons une reformulation. Ainsi, nous tirons parti de la structure en étoile de la nouvelle reformulation pour développer un algorithme de Génération de Colonnes basé sur la décomposition. La composante quadratique du problème est traitée dans le problème principal de Génération de Colonnes et dans ses sous-problèmes. Dans nos expérimentations, nous évaluons les performances de la méthodologie sur différentes applications avec différentes structures quadratiques. La reformulation en étoile et la Génération de Colonnes sont plus performants que GUROBI en termes de borne duale et de temps de calcul dans presque tous les cas de problèmes de Programmation Quadratique Binaire adjacents. En outre, même une simple mise en oeuvre du cadre de fractionnement des coûts donne des résultats encourageants pour le Problème d’Assignation Semi Quadratique en tant qu’étude de cas, en particulier pour les instances avec des matrices quadratiques plus éparses. Dans le troisième essai, une approche basée sur les données est utilisée pour personnaliser les contraintes des modèles de Programmation Linéaire en Nombres Entiers Mixtes classiques afin de produire une solution qui est probablement réalisable en pratique sur la base des contraintes apprises à partir des solutions précédemment mises en oeuvre. Les décideurs de différents secteurs utilisent des logiciels d’optimisation pour la planification et la prise de décision. Cependant, dans de nombreuses applications réelles, ils personnalisent les solutions fournies par le logiciel sur la base de certaines règles et préférences opérationnelles internes implicites. Pour s’assurer que de telles considérations et contraintes cachées peuvent être systématiquement prises en compte sans nécessiter de connaissances explicites obtenues auprès d’experts humains, il est possible d’exploiter des méthodes basées sur les données pour intégrer des contraintes latérales dans des Programmes Linéaires en Nombres Entiers Mixtes classiques. Plutôt que de s’appuyer sur un simple modèle de régression linéaire proposé dans la littérature, nous étendons le cadre en incorporant la régression linéaire régularisée et les arbres de décision dans le modèle d’optimisation. Pour motiver la méthode, nous discutons de différentes combinaisons de règles dans le problème du sac à dos linéaire et binaire. En outre, nous présentons une approche pour traiter les cas programmation linéaire en nombres entiers mixtes 0-1 en intégrant un arbre de classification au lieu d’une régression linéaire. Nous abordons également des règles opérationnelles plus difficiles et utilisons le cadre dans une application pratique, le Problème de Roulement des Infirmières. Les solutions optimales obtenues par la méthode suggèrent que l’approche proposée peut apprendre les ajustements à partir des données et être plus efficace que les travaux antérieurs dans ce domaine dans des environnements complexes. MOTS-CLÉS : programmation quadratique binaire, optimisation combinatoire, génération de colonnes, problème de semi-affectation, problème de suivi d’objets multiples, personnalisation des contraintes, méthodes basées sur les données, programmation linéaire en nombres entiers mixtes, arbre de décision.