Integer programming column generation strategies for the cutting stock problem and its variants

Cette thèse traite du problème de découpe uni-dimentionnel et de ses variantes. Une revue compréhensive des différentes formulations et approches de résolution associées y est complètée par des résultats sur les relations théoriques d'équivalence ou de dominance qui existent entre ces formulations et des comparaisons sur des questions pratiques telles que la symétrie dans la représentation des solutions et les schémas de branchement qu'elles induisent. La thèse se poursuit par la comparaison numérique de stratégies d'implémentation pour une approche de branch-and-price avec des résultats en matière d'initialisation, de stabilisation, de stratégie de branchements et sur l'obtention de solutions primales. Ces stratégies sont ensuite utilisées pour résoudre des problèmes industriels. La thèse montre aussi comment le sous-problème de sac-à-dos avec coût fixe peut être résolu exactement et efficacement.BORDEAUX1-BU Sciences-Talence (335222101) / SudocSudocFranceF