École Nationale Supérieure de
Techniques Avancées

Abstract

This report tackles a resolution method to the problem of minimizing a polynomial over binary variables. It explains and describes a method, from an article [1] written by C.Hojny and al., which permits to obtain a linearization which conserves the "integrality" of the polynomial relaxation. This method studies the sub-cycles of the polynomial’s Hasse diagram. This report also describes the implementation of such method in the programming language Julia. Finally, this report presents the results of the implementation, and compares these with the results obtains with the implementation of the standard linearization.