Ce module traite de la programmation linéaire en nombres entiers et de son utilisation pour résoudre des problèmes NP-hard (optimisation combinatoire). Nous aborderons quelques exemples de ce qu'est la programmation linéaire en nombres entiers en formulant des problèmes tels que Knapsack, Vertex Cover et Graph Coloring. Ensuite, nous étudierons le concept d'écart d'intégralité et le cas particulier de l'écart d'intégralité pour les problèmes de couverture de sommet. Nous conclurons par un tutoriel sur la formulation et la résolution de programmes linéaires en nombres entiers à l'aide de la bibliothèque python Pulp.

Nous introduirons des algorithmes d'approximation pour la résolution de problèmes NP-hard. Ces algorithmes sont rapides (souvent des algorithmes gourmands) et peuvent ne pas produire une solution optimale, mais garantissent que leur solution n'est pas "trop éloignée" de la meilleure possible. Nous présenterons certains de ces algorithmes en commençant par une introduction de base aux concepts impliqués, suivie d'une série d'algorithmes d'approximation pour les problèmes d'ordonnancement, le problème de couverture des sommets et le problème de satisfiabilité maximale.

Nous présenterons le problème du voyageur de commerce (TSP), un problème d'optimisation combinatoire très important et largement applicable, sa dureté NP et la dureté de l'approximation d'un TSP général avec un facteur constant. Nous présentons une formulation de programmation linéaire en nombres entiers et un algorithme de programmation dynamique simple mais élégant. Nous présenterons un algorithme d'approximation de facteur 3/2 par Christofides et discuterons de quelques approches heuristiques pour résoudre les TSP. Nous conclurons en présentant des schémas d'approximation pour le problème du sac à dos.