Ces cours présentent les problèmes d'optimisation et certaines techniques d'optimisation à travers le problème du sac à dos, l'un des problèmes les plus connus dans ce domaine. Il discute de la façon de formaliser et de modéliser les problèmes d'optimisation en utilisant le problème du sac à dos comme exemple. Il examine ensuite comment appliquer la programmation dynamique et le branch and bound au problème du sac à dos, en fournissant l'intuition derrière ces deux techniques d'optimisation fondamentales. Les concepts de relaxation et de recherche sont également abordés.

La programmation par contraintes est une technique d'optimisation issue du domaine de l'intelligence artificielle. Elle se caractérise par deux idées clés : Exprimer le problème d'optimisation à un niveau élevé pour révéler sa structure et utiliser des contraintes pour réduire l'espace de recherche en supprimant, des domaines variables, les valeurs qui ne peuvent pas apparaître dans les solutions. Ces conférences couvrent la programmation par contraintes en détail, décrivant le langage de la programmation par contraintes, son paradigme informatique sous-jacent et la manière dont elle peut être appliquée dans la pratique.

La recherche locale est probablement la technique d'optimisation la plus ancienne et la plus intuitive. Elle consiste à partir d'une solution et à l'améliorer en effectuant (généralement) des perturbations locales (souvent appelées mouvements). La recherche locale a considérablement évolué au cours des dernières décennies, avec beaucoup d'attention portée sur les mouvements à explorer. Ces conférences explorent la théorie et la pratique de la recherche locale, depuis le concept de voisinage et de connectivité jusqu'aux méta-heuristiques telles que la recherche taboue et le recuit simulé.

La programmation linéaire a été, et reste, un cheval de bataille de l'optimisation. Elle consiste à optimiser un objectif linéaire soumis à des contraintes linéaires, admet des solutions algorithmiques efficaces et constitue souvent un élément de base important pour d'autres techniques d'optimisation. Ces cours passent en revue les concepts fondamentaux de la programmation linéaire, y compris le fameux algorithme du simplexe, le tableau du simplexe et la dualité. .

La programmation en nombres entiers mixtes généralise la programmation linéaire en autorisant des variables entières, ce qui modifie considérablement la complexité des problèmes, mais élargit aussi considérablement les applications potentielles. Ces cours passent en revue la façon de modéliser les problèmes en programmation en nombres entiers mixtes et la façon de résoudre les programmes en nombres entiers mixtes à l'aide de la méthode branch and bound. Des techniques avancées telles que les plans de coupe et les coupes polyédriques sont également abordées.

Ces cours couvrent des concepts plus avancés en matière d'optimisation. Ils introduisent des techniques de programmation par contraintes pour l'ordonnancement et le routage.

Ces cours continuent à couvrir des concepts plus avancés en optimisation. Ils présentent la recherche par grand voisinage, qui combine souvent la programmation par contraintes et la recherche locale, et la génération de colonnes, qui décompose un modèle d'optimisation en un problème principal et un problème de prix, en utilisant des variables plus complexes.