Problèmes de couverture en nombres entiers : génération de colonnes, heuristiques d'approximation garantie et schémas hybrides. : Applications en transport ferroviaire et en planification de production
Institution:
Paris 13Disciplines:
Directors:
Abstract EN:
Large-size Covering Integer Programs (CIP) model many real-case applications. They appear typically as master problems resulting from a Dantzig-Wolfe decomposition. The well-known column generation approach is widely used for solving such large-size problems. In this thesis, it is combined in a hybrid way with the best-known approximation heuristic for CIP : the greedy heuristic of Dobson that is extended, through the resolution of fractional subproblems, to large-size CIP. The propsed hybridization scheme takes advantage of the distinct criteria of columns selection used by the two methods. It is evaluated on two transportation and production planning applications. Numerical results on real-case instances show that the hybrid scheme improves the convergence of column generation both in terms of number of iterations and computational time. The integer solutions derived from the column generation scheme are also significantly improved, highlighting the diversification potential of the approximation heuristic. On an other hand, an original reformulation of CIP as Set Covering Problems is proposed as an alternative demonstration of the logarithmic approximation ratio allowing it’s extention to new variants of CIP as the Fixed Charge Covering Integer Programs.
Abstract FR:
Les programmes de couverture en nombres entiers (CIP) modélisent de nombreux problèmes industriels réels. Dans le cadre de cette thèse, nous nous intéressons aux CIP de grande taille, programmes qui apparaissent souvent comme problèmes maîtres issus d’une décomposition de type Dantzig-Wolfe. Les approches de résolution de problèmes de grande taille, et plus spécifiquement, la méthode de génération de colonnes, connaissent un intérêt grandissant depuis plusieurs années. Nous présentons dans un premier temps un tour d’horizon autour de la méthode de génération de colonnes, et des approches de résolution entière (exactes ou approchées) basées sur cette méthode. Nous étudions ensuite les heuristiques d’approximation dédiées aux CIP, puis nous proposons une adaptation de l’heuristique gloutonne de Dobson aux CIP de grande taille, engendrant la résolution d’un sous-problème fractionnaire. Nous revisitons à l’issue de cette étude la preuve du rapport d’approximation de l’heuristique de Dobson à l’aide d’une reformulation originale permettant d’étendre cette preuve à de nouvelles variantes. A l’issue des deux études précédentes, nous proposons de nouvelles approches de résolution approchée pour les CIP de grande taille qui font coopérer l’heuristique d’approximation gloutonne et la méthode de génération de colonnes. Des coopérations séquentielles et hybrides sont alors mises en oeuvre et évaluées sur des instances de problèmes réels. Les résultats obtenus montrent que l’heuristique gloutonne constitue un générateur efficace de colonnes et de solutions diversifiées permettant d’améliorer différents aspects du schéma de génération de colonnes : d’une part, en diminuant le nombre d’itérations ainsi que le temps de résolution, et d’autre part, en améliorant la valeur du majorant (les CIP étant des problèmes de minimisation) dans un schéma de résolution en nombres entiers. La validation expérimentale de l’ensemble des approches proposées est finalement réalisée sur deux applications types issues des domaines du transport ferroviaire et de la production agricole.