Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Optimization Letters

Optimal quadratic reformulations of fourth degree Pseudo-Boolean functions

Amit Verma, Mark W. Lewis

Published Aug 3, 2019• 25 citations
Publisher
DOI
10.1007/s11590-019-01460-7

Related papers

A decomposition method for minimizing quadratic pseudo-Boolean functions

Alain Billionnet, Brigitte Jaumard

Operations Research Letters•Jun 1, 1989•22 citations

Functionally redundant constraints for Boolean quadratic-type optimization problems

Petro I. Stetsyuk

Cybernetics and Systems Analysis•Nov 1, 2005•4 citations

Solving Non-Linear Pseudo-Boolean Optimization Problems by Constraint Integer Programming.

Michael Winkler

ISAIM•Jan 1, 2016•0 citations

Quantum algorithms for learning the algebraic normal form of quadratic Boolean functions

Xuexuan Hao, Fengrong Zhang, Shixiong Xia +1 more

Quantum Information Processing•Jul 30, 2020•7 citations

Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions

Sung-Soon Choi, Kyomin Jung, Jeong Han Kim

Journal of Computer and System Sciences•Sep 1, 2010•15 citations

Quadratic reformulations for the optimization of pseudo-boolean functions

Yves Crama, Sourour Elloumi, Amélie Lambert +1 more

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, 2022•0 citations
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.