We investigate various solution approaches for the uncon-strained minimization of a pseudo-boolean function. Moreprecisely, we assume that the original function is expressedas a real-valued polynomial in 0-1 variables, of degree threeor more, and we consider a generic family of two-step ap-proaches for its minimization. First, a quadratic reformu-lation step aims at transforming the minimization probleminto an equivalent constrained or unconstrained quadratic0-1 minimization problem (where “equivalent” means herethat a minimizer of the original function can be easily de-duced from a minimizer of the reformulation). Second, anoptimization step handles the obtained equivalent quadraticproblem.We provide a unified presentation of several quadratic re-formulation schemes proposed in the literature, e.g., (An-thony et al. 2017; Buchheim and Rinaldi 2007; Rodr ́ıguez-Heck 2018; Rosenberg 1975), and we review several meth-ods that can be applied in the optimization step, includinga standard linearization procedure (Fortet 1959) and moreelaborate convex quadratic reformulations, as in (Billionnetand Elloumi 2007; Billionnet, Elloumi, and Lambert 2012,2016; Elloumi, Lambert, and Lazare 2021). We discuss theimpact of the reformulation scheme on the efficiency of theoptimization step and we illustrate our discussion with somecomputational results on different classes of instances.

Jan 3, 20220 citations

Quadratizations of symmetric pseudo-Boolean functions: sub-linear bounds on the number of auxiliary variables

Endre Boros, Yves Crama, Elisabeth Rodríguez-Heck

The problem of minimizing a pseudo-Boolean function with no additional constraints arises in a variety of applications.A quadratization is a quadratic reformulation of the nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques.Using the well-known result that a pseudo-Boolean function can be uniquely expressed as a multilinear polynomial, any pseudo-Boolean function can be quadratized by providing a quadratization for negative monomials and one for positive monomials.A desirable property for a quadratization is to introduce small number of auxiliary variables.For the case of negative monomials there exists a quadratization using a single auxiliary variable which is, in addition, submodular.However, much less is known for positive monomials.The best lower bound on the number of variables required by a quadratization in the literature is n-1 2 .We present here new quadratizations of the positive monomial that significantly improve this lower bound decreasing it to a logarithmic bound.This lower bound is derived from a more general result, stating that a quadratization with a logarithmic number of variables can be defined for exact kout-of-n functions, which is a more general class of symmetric functions.Moreover, for exact k-out-of-n functions we also prove that a logarithmic number of variables is necessary when requiring certain symmetry conditions to the quadratization.Finally, we provide quadratizations for general symmetric functions using O( √ n) auxiliary variables.This upper bound nicely matches a lower bound of Ω( √ n) variables that was recently introduced.

ISAIMJan 4, 20187 citations