Quadratic reformulations for the optimization of pseudo-boolean functions
Yves Crama, Sourour Elloumi, Amélie Lambert, Elisabeth Rodríguez-Heck
Abstract
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.