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

Cybernetics and Systems Analysis

Functionally redundant constraints for Boolean quadratic-type optimization problems

Petro I. Stetsyuk

Published Nov 1, 2005• 4 citations
Publisher
DOI
10.1007/s10559-006-0029-z

Related papers

Optimal quadratic reformulations of fourth degree Pseudo-Boolean functions

Amit Verma, Mark W. Lewis

Optimization Letters•Aug 3, 2019•25 citations

The spherical constraint in Boolean quadratic programs

Jérôme Malick

Journal of Global Optimization•Jun 5, 2007•21 citations

Quadratic Optimization in 0–1 Variables

Alain Billionnet

This chapter introduces some theoretical and algorithmic aspects of quadratic optimization in bivalent variables, which is, in general, an NP-hard problem. It discusses the central problem of quadratic optimization in 0–1 variables without constraints. The chapter reviews some results in the constraint case. It also discusses a property of pseudo-Boolean functions that is relatively rare in optimization. The chapter examines a formulation of the problem of maximizing a quadratic pseudo-Boolean functions (qpBf) using a mixed integer linear program. It focuses on the optimization of a function of bivalent variables subject to some constraints. This optimization model is extremely general and the chapter limits to the problem of optimizing a quadratic pseudo-Boolean function with linear constraints. The chapter shows that the optimal value of the dual Lagrangian problem is equal to the optimal value of the continuous relaxation of the classical linearization of the initial problem.

Wiley eBooks•Jul 10, 2014•2 citations

A Characterization of Binary Quadratic Optimization Problems

최혜지

•Jan 1, 2018•0 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.

ISAIM•Jan 4, 2018•7 citations

Binary Unconstrained Quadratic Optimization Problem

Gary A. Kochenberger, Fred Glover, Haibo Wang

Springer eBooks•Jan 1, 2013•9 citations
This chapter introduces some theoretical and algorithmic aspects of quadratic optimization in bivalent variables, which is, in general, an NP-hard problem. It discusses the central problem of quadratic optimization in 0–1 variables without constraints. The chapter reviews some results in the constraint case. It also discusses a property of pseudo-Boolean functions that is relatively rare in optimization. The chapter examines a formulation of the problem of maximizing a quadratic pseudo-Boolean functions (qpBf) using a mixed integer linear program. It focuses on the optimization of a function of bivalent variables subject to some constraints. This optimization model is extremely general and the chapter limits to the problem of optimizing a quadratic pseudo-Boolean function with linear constraints. The chapter shows that the optimal value of the dual Lagrangian problem is equal to the optimal value of the continuous relaxation of the classical linearization of the initial problem.
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.