École Nationale Supérieure de
Techniques Avancées

Résumé

Ce rapport donne une approche d’étude pour analyser et résoudre le problème de la minimisation de polynômes en variables binaires. Il explique et décrit une méthode, tirée d’un article [1] de C. Hojny et co-auteurs, de linéarisation par ajout de monômes artificiels permettant de savoir s’il existe ou non une linéarisation dont la relaxation continue est exacte. Cette méthode étudie notamment les sous-cycles d’un diagramme de Hasse du polynôme. Ce rapport décrit également la mise en pratique de cette méthode par une implémentation en langage de programmation Julia. Enfin, ce rapport présente les résultats obtenus par la méthode utilisant le diagramme de Hasse, et offre un comparatif de ces résultats avec ceux obtenus par la linéarisation standard.