École Nationale Supérieure de
Techniques Avancées

Résumé

Ce rapport présente une méthode de résolution de problèmes quadra-tiques non-convexes en nombres entiers en s’appuyant sur la méthode décrite dans l’article [1] rédigé par Dominique Quadri et Eric Soutil. Essentiellement il s’agit d’une reformulation du problème afin de transformer la partie quadratique de la fonction objectif en une fonction linéaire par ajout de nouvelles contraintes. Cette transformation permet ensuite de résoudre le nouveau problème linéaire avec l’algorithme Branch & Bound. Il est aussi expliqué comment passer du cas convexe au cas non-convexe. Il y est également justifié le choix de Julia comme langage d’implémentation de la solution. En-fin il est aussi proposé une étude des performances de cette méthode et des limites de l’approximation effectuée.