Enveloppe convexe de la linéarisation d'une fonction pseudo-booléenne

Abstract

Ce mémoire traite le problème d’optimisation de fonctions pseudo-booléennes multilinéaires particulières. L’objectif est de décrire l’ensemble des inégalités définissant l’enveloppe convexe des solutions binaires associée à une telle fonction. Après avoir établi le lien entre les problèmes d’optimisation sur ces fonctions et la programmation linéaire en nombres entiers, ce mémoire s’intéresse particulièrement aux fonctions pseudo-booléennes à un, deux et trois monômes non linéaires. Il traite également une configuration particulière de m monômes non linéaires.