Union de polyèdres

À l'intersection des mathématiques appliquées et de l'informatique théorique, l'optimisation combinatoire consiste à trouver un objet optimal parmi un ensemble fini d'objets. Ces problèmes peuvent rarement être résolus par énumération et leur étude nécessite d'en dégager des propriétés structurelles. Ces objets peuvent par exemple être des chemins sur une carte ou des tâches à ordonner. Les polyèdres peuvent être utilisés pour décrire l'ensemble des solutions d'un problème d'optimisation combinatoire. Sur cette figure, l'union (en vert) des deux polyèdres (magenta et bleu) permet d'obtenir la description de l'ensemble des solutions d'un problème à partir de caractérisations partielles.