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

Quadratic 0-1 optimization

Gintaras Palubeckis

Published Jan 1, 1990• 4 citations
Publisher
DOI
10.3233/inf-1990-1106

Related papers

Bivalent quadratic optimization with sum-of-square of quadratic penalties

Tongli Zhang, Yong Xia

Journal of Combinatorial Optimization•Aug 1, 2025•0 citations

Quadratic Convex Reformulation for discrete quadratic optimization : Basic results and recent extensions

Sourour Elloumi

We consider problem (QP) of minimizing a quadratic function subject to linear or quadratic constraints. Variables are integer and bounded. This very general problem can model many classical problems in Combinatorial Optimization.A major difference between (QP) and integer linear programs lies in the fact that, in general, its continuous relaxation is an NP-hard optimization problem. To overcome this difficulty, the Convex Quadratic Reformulation approach transforms (QP) into a problem (QP'), equivalent to (QP), but whose continuous relaxation is a convex problem. To compute a global optimal solution to (QP) it becomes possible to solve (QP') by an implicit enumeration algorithm based on continuous convex optimization.We make an overview of recent developments in this approach. We show in particular how positive semidefinite relaxations can be used to build the most interesting equivalent problems (QP'). In the case of binary variables, we give a vision of classical linearization as a special case of Convex Quadratic Reformulation.Finally, we illustrate the generality and the computational efficiency of the Quadratic Convex Reformulation approach for several combinatorial optimization problems.

•Oct 28, 2014•0 citations

Quadratic Optimization in 0–1 Variables

Alain Billionnet

Wiley eBooks•Jan 21, 2013•1 citation

Persistency in quadratic 0–1 optimization

Alain Billionnet, Alain Sutter

Mathematical Programming•Feb 1, 1992•18 citations

A hybrid algorithm for quadratically constrained quadratic optimization problems

Hongyi Zhou, Sirui Peng, Qian Li +1 more

Abstract Quadratically Constrained Quadratic Programs (QCQPs) are an important class of optimization problems with diverse real-world applications. In this work, we propose a variational quantum algorithm for general QCQPs. By encoding the variables in the amplitude of a quantum state, the requirement for the qubit number scales logarithmically with the dimension of the variables, which makes our algorithm suitable for current quantum devices. Using the primal-dual interior-point method in classical optimization, we can deal with general quadratic constraints. Our numerical experiments on typical QCQP problems, including Max-Cut and optimal power flow problems, demonstrate better performance of our hybrid algorithm over classical counterparts.

arXiv:2309.10564•Physica Scripta•May 16, 2024•2 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
We consider problem (QP) of minimizing a quadratic function subject to linear or quadratic constraints. Variables are integer and bounded. This very general problem can model many classical problems in Combinatorial Optimization.A major difference between (QP) and integer linear programs lies in the fact that, in general, its continuous relaxation is an NP-hard optimization problem. To overcome this difficulty, the Convex Quadratic Reformulation approach transforms (QP) into a problem (QP'), equivalent to (QP), but whose continuous relaxation is a convex problem. To compute a global optimal solution to (QP) it becomes possible to solve (QP') by an implicit enumeration algorithm based on continuous convex optimization.We make an overview of recent developments in this approach. We show in particular how positive semidefinite relaxations can be used to build the most interesting equivalent problems (QP'). In the case of binary variables, we give a vision of classical linearization as a special case of Convex Quadratic Reformulation.Finally, we illustrate the generality and the computational efficiency of the Quadratic Convex Reformulation approach for several combinatorial optimization problems.
Abstract Quadratically Constrained Quadratic Programs (QCQPs) are an important class of optimization problems with diverse real-world applications. In this work, we propose a variational quantum algorithm for general QCQPs. By encoding the variables in the amplitude of a quantum state, the requirement for the qubit number scales logarithmically with the dimension of the variables, which makes our algorithm suitable for current quantum devices. Using the primal-dual interior-point method in classical optimization, we can deal with general quadratic constraints. Our numerical experiments on typical QCQP problems, including Max-Cut and optimal power flow problems, demonstrate better performance of our hybrid algorithm over classical counterparts.
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.