Berge-acyclic multilinear 0-1 optimization problems

The problem of optimizing a multilinear polynomial f in 0–1 variables arises in applications from many different areas. We are interested in resolution methods based on reformulating the polynomial problem into an equivalent linear one, an approach that attempts to draw benefit from the extensive literature in integer linear programming. More precisely, we characterize instances for which the classical standard linearization procedure guarantees integer optimal solutions. We show that the standard linearization polytope P_H is integer if and only if the hypergraph H defined by the higher-degree monomials of f is Berge-acyclic, or equivalently, when the matrix defining P_H is balanced. This characterization follows from more general conditions that guarantee integral optimal vertices for a relaxed formulation depending on the sign pattern of the monomials of f.