Cette séance de cours passe en revue les problèmes classiques d'optimisation combinatoire et montre comment ils peuvent être modélisés en tant que problèmes linéaires mixtes, en commençant par le problème du sac à dos. En utilisant l'exemple d'un randonneur emballer un sac à dos avec une capacité de poids, la séance de cours explique comment maximiser l'utilité tout en restant dans la limite de poids en définissant des variables de décision, la fonction objectif, et les contraintes. Le problème du sac à dos est un problème d'optimisation combinatoire fondamental applicable dans divers contextes, tels que la sélection d'actifs pour les investisseurs.