La méthode de décomposition s'applique à des problèmes structurés dans lesquels on reconnaît des sous-problèmes pour lesquels on dispose d'algorithmes relativement efficaces. La stratégie consiste alors à reformuler le problème en terme des choix de solutions qu'on peut faire pour les sous-problèmes. Cette reformulation forte permet de faire reculer les limites de la complexité de résolution. Cette approche est cependant restée au stade des méthodes développées en recherche, par des experts, dans le cadre d'études d'applications spécifiques. Son efficacité est reconnue sur des problèmes tels que : les problèmes de transport et de tournées livraisons, les problèmes de découpe optimale (p.e. du papier), les problèmes de dimensionnement de réseau de télécommunication ou les problèmes de planification des tâches. Sa mise en uvre est jusqu'ici perçue comme nécessairement liée à l'application. Le défi consiste à rendre cette approche générique et faire la démonstration que cette approche peut devenir un outil disponible pour tous dans les solveurs commerciaux.
Le prototype BaPCod que nous avons développé automatise les
manipulations qui sont demandées à l'utilisateur et propose un cur de méthode
commun à toutes les applications. Cet algorithme générique intègre les dernières avancées en
recherche dans le développement de la méthode de
``branch-and-price''. Le corps du logiciel BaPCod représente 32500 lignes de code C++.
Par défaut, BaPCod fait appel à un solveur de programmation linéaire
en variables entières et continues (``MIP-solver'') pour résoudre le programme maître et
les sous-problèmes issus de la décomposition. Le logiciel est donc
conçu comme une couche au dessus de la couche de base qu'est un
``MIP-solver''. BaPCod peut ainsi être interfacé avec des
``MIP-solvers'' commerciaux ou ``open-source''. Les interfaces actuellement
disponibles sont : Cplex, Xpress-mp, Lp-Solve (``open-source'')
et GLPK (``open-source''). L'interface avec Coin-OR-CBC est
à réaliser. Par ailleurs,
les sous-problèmes peuvent être résolus par des algorithmes combinatoires
spécifiques. BaPCod en offre certains dans sa distribution (essentiellement les
solveurs pour les variantes du problème de sac-à-dos).