Marie-Claude PORTMANN
Docteur ès sciences mathématiques, Université Nancy 1 - Professeur à l’École Nationale Supérieure des Mines de Nancy, INPL
Cet article présente les méthodes et techniques les plus usitées pour résoudre les problèmes d’optimisation discrète, à savoir la complexité des algorithmes contenant des variables discrètes. Pour cela, il aborde la modélisation de quatre problèmes concrets à l’aide d’équations linéaires ou éventuellement quadratiques. Sont ainsi détaillées les méthodes de résolution exacte, les méthodes exponentielles appelées procédures par séparation et évaluation, ou celles de résolution approchée, comme les méta-heuristiques.