Réduction des variables et application dans une méthode hybride pour la résolution des problèmes de programmation linéaire en nombres entiers.

Abstract

Dans cette thèse, nous nous sommes intéressés à l’amélioration des méthodes de résolution pour les problèmes de Programmation Linéaire en Nombres Entiers (PLNE) à variables bornées, en combinant des techniques de presolving et une heuristique basée sur une procédure d’arrondissement. Le presolving vise à réduire la taille des modèles en fixant certaines variables, en éliminant les redondances, en resserrant les bornes des variables et en simplifiant les contraintes, tandis que l’heuristique propose une méthode rapide pour obtenir des solutions entières réalisables, et ce, en résolvant un problème auxiliaire. Les résultats expérimentaux montrent que le presolving simplifie efficacement les modèles et améliore les performances des solveurs, tandis que l’heuristique offre un compromis intéressant entre rapidité d’exécution et qualité des solutions, avec des écarts satisfaisants par rapport à l’optimalité. Ces contributions constituent une avancée pour résoudre efficacement les PLNE de grande taille, tout en ouvrant des perspectives pour des améliorations futures.