Les problèmes d'optimisation présentant des aspects combinatoires, de par la présence de variables de décision entières, interviennent dans tous les secteurs de la vie économique (investissement, gestion de ressources humaines ou d'équipements, planification de production de l'énergie) mais aussi dans la technologie (conception de circuits intégrés, optimisation de réseaux de télécommunication ou de services en ligne).
Cet ouvrage, issu d'un cours donné à l'Ecole polytechnique, introduit aux grands principes de résolution de tels problèmes, basés sur la théorie des fonctions convexes, la dualité en optimisation, les polyèdres et la programmation linéaire, les méthodes de flots, de programmation dynamique, de séparation et évaluation, ou de coupes d'intégrité. Ce tour d'horizon inclut deux chapitres plus avancés, portant sur les applications en combinatoire de l'optimisation sous contrainte de positivité matricielle (optimisation SDP), et sur les algorithmes de points intérieurs pour la programmation quadratique convexe.
Tout en s'appuyant sur une analyse mathématique rigoureuse, cet ouvrage présente de nombreux exemples. En particulier, un chapitre de corrigés d'une sélection d'exercices, ainsi qu'une trentaine d'énoncés de problèmes avec correction, prolongent le cours et fournissent des illustrations issues de domaines d'application variés.