Concave extensions for nonlinear 0-1 maximization problems

A well-known linearization technique for nonlinear 0-1 maximization problems can be viewed as extending any polynomial in 0-1 variables to a concave function defined on [0,1]’n. Some properties of this ‘standard’ concave extension are investigated. Polynomials for which the standard extension coincides with the concave envelope are characterized in terms of integrality of a certain polyhedron or balancedness of a certain matrix. The standard extension is proved to be identical to another type of concave extension, defined as the lower envelope of a class of affine functions majorizing the given polynomial.