OPTIMISATION DISCRETE De la modélisation à la résolution par des logiciels de programmation mathématique
Alain BillionnetParmi tous les problèmes rencontrés par l’ingénieur, le chercheur, le gestionnaire ou l’économiste, les problèmes d ’optimisation et, en particulier, les problèmes discrets occupent une place de choix. Depuis une trentaine d’années, des méthodes très efficaces ont été proposées et sans cesse améliorées pour résoudre les problèmes d’optimisation linéaires ou quadratiques convexes com portant des variables entières. Par ailleurs, de nombreux logiciels - ou solveurs - mettant en œuvre ces méthodes sont actuellement disponibles (COIN-OR, CPLEX, OSL, Xpress-MP, etc.) ainsi que des langages de modélisation - ou modeleurs - qui apportent une aide précieuse à l’utilisation de ces logiciels (AIMMS, AMPL, GAMS, MPL, Mosel, etc.).
Toutefois, un grand nombre de problèmes d’optimisation discrets, pertinents d ’un point de vue scientifique ou économique, mais difficiles à résoudre, ne se formulent pas directement de façon linéaire ou quadratique convexe.
Face à de tels problèmes, et compte tenu de la puissance croissante des ordinateurs, il est donc tentant d’essayer de les formuler comme des problèmes linéaires ou quadratiques en variables entières. Dans certains cas, il est relativement facile
d’obtenir ces formulations. C ’est le cas des problèmes d’optimisation dont la nature est fondamentalement linéaire ou quadratique (convexe). Dans les autres cas, la modélisation est plus difficile à obtenir. Dans les deux cas, il reste la question délicate du choix d’une formulation, car il en existe souvent plusieurs, et l’efficacité de la résolution du problème dépend fortement de la formulation retenue.
Le but de cet ouvrage est de montrer comment construire de bonnes modélisations, sous la forme de problèmes d’optimisation linéaires ou quadratiques en variables entières, de très nombreux problèmes d’optimisation, même si cette modélisation ne paraît pas évidente a priori. O n peut ainsi, par cette approche, résoudre un vaste ensemble de problèmes d’optimisation difficiles de la recherche opérationnelle et des sciences de l’ingénieur, en profitant des techniques et logiciels développés pour l’optimisation linéaire ou quadratique en variables entières. Le champ d’application de ce domaine de la programmation mathématique devient alors beaucoup plus large. Il est ainsi possible d’obtenir par cette approche, en quelques heures de travail et en utilisant un ordinateur personnel, la solution d’un problème d’optimisation complexe dont le traitement par un algorithme spécifique demanderait infiniment plus d’efforts.