Intégration des techniques de recherche locale à la programmation linéaire en nombres entiers
Institution:
AvignonDisciplines:
Directors:
Abstract EN:
We present several algorithms for integrating local search technique into mixed integer programming (MIP). We first introduce a cooperation scheme between local search and branch-and-price that generalizes the concept of branch-and-cut heuristics to branch-and-price and we apply it successfully to the vehicle routing problem with time windows. We then present a new MIP heuristic that we call Relaxation Induced Neighborhood Search (RINS). This heuristic finds good integer solutions on models that previously were very difficult to solve. It is now implemented in ILOG CPLEX 9. RINS exploits the three fundamental concepts of local search (neighborhood, intensification, and diversification) and transposes them to mixed integer programming. This heuristic is generic : it can be applied to any MIP model, with no other input than the model itself. RINS allows us to formalize the notion of "hybrid in spirit'' algorithms. This development paradigm consists in using only one optimization technique and integrating into its framework concepts of other resolution techniques instead of having several software components cooperate. RINS performances and our analysis of difficulties encountered by existing hybrid algorithms suggest that this class of algorithms is promising. We finally concentrate on the job-shop scheduling problem with earliness and tardiness costs on which RINS is particularly effective. We propose several improvements and extensions of the disjunctive model for this problem and a heuristic (MCORE : big-M COefficient REduction) that could be generalized to other MIP models of similar structure. MCORE is also a "hybrid in spirit'' algorithm
Abstract FR:
Cette thèse présente plusieurs algorithmes pour l'intégration des techniques de recherche locale à la programmation linéaire en nombres entiers (PLNE). Premièrement, nous introduisons un schéma de coopération entre recherche locale et génération de colonnes qui généralise le concept d'heuristiques pour le branch-and-cut au branch-and-price et nous l'appliquons avec succès au problème de tournées de véhicules avec fenêtres de temps. Deuxièmement, nous présentons une nouvelle heuristique pour les problèmes linéaires quelconques en nombres entiers : Relaxation Induced Neighborhood Search (RINS). Cette heuristique produit des solutions entières de qualité pour des modèles qu'il était très difficile de résoudre auparavant. Elle est maintenant implantée dans le logiciel ILOG CPLEX 9. RINS exploite les trois concepts fondamentaux de la recherche locale (voisinage, intensification et diversification) en les transposant à la programmation linéaire en nombres entiers. Cette heuristique est générique : elle peut être appliquée à n'importe quel modèle de PLNE, sans aucune connaissance préalable de sa structure. RINS nous permet de formaliser la notion d'algorithme "conceptuellement hybride". Ce paradigme de développement consiste à utiliser une seule technique de résolution et à intégrer dans ce cadre les concepts d'autres techniques plutôt qu'à faire coopérer des composants logiciels. Les performances de RINS et notre analyse des difficultés des algorithmes hybrides existants laissent à penser que cette classe d'algorithmes est prometteuse. Troisièmement, nous nous intéressons plus en détail au problème d'ordonnancement d'atelier avec coûts d'avance et de retard sur lequel RINS est particulièrement efficace. Nous proposons plusieurs améliorations et extensions du modèle disjonctif pour ce problème et une heuristique (MCORE: big-M COefficient REduction) qui pourrait être généralisée à d'autres modèles de structure similaire. MCORE est également un algorithme "conceptuellement hybride"