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

ISAIM

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

Michael Winkler

Published Jan 1, 2016• 0 citations
OpenAlex

Related papers

Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods

Pierre Bonami, Oktay Günlük, Jeff Linderoth

Mathematical Programming Computation•Feb 24, 2018•40 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 decomposition method for minimizing quadratic pseudo-Boolean functions

Alain Billionnet, Brigitte Jaumard

Operations Research Letters•Jun 1, 1989•22 citations

Bounds for Binary Integer Programming via Unconstrained Quadratic Pseudo-Boolean Optimization

Sirilak Phonin, Chulin Likasiri

This research proposes a method for finding bounds in binary integer programming (BIP) and quadratic binary integer programming (QBIP). Our approach utilizes a max-flow technique within the framework of quadratic pseudo-Boolean optimization. We apply Lagrange multipliers to transform these problems into a quadratic pseudo-Boolean format, enabling us to create a corresponding network. We develop sufficient conditions under which a flow can or cannot be established in this network. The upper bound of the original problem is obtained through a feasible flow within the network. Additionally, we provide the optimality conditions for the solutions discussed in this paper. We have derived the closed forms for the various functions and values commonly used in our proposed method, as well as a lower bound for both BIP and QBIP, which can assist in solving these problems. This paper includes examples that illustrate both networks containing flows and those that do not, as well as examples that demonstrate lower and upper bound solutions as identified by our method. Furthermore, since our approach can also be applied to Quadratic Unconstrained Binary Optimization (QUBO), we provide the closed forms for the frequently used functions and values in that context, along with an example showcasing its application to a quadratic unconstrained optimization problem.

Mathematics•Aug 17, 2026•1 citation

Binary Unconstrained Quadratic Optimization Problem

Gary A. Kochenberger, Fred Glover, Haibo Wang

Springer eBooks•Jan 1, 2013•9 citations

Integer programming using a single atom

Kapil Goswami, Peter Schmelcher, Rick Mukherjee

Abstract Integer programming (IP), as the name suggests is an integer-variable-based approach commonly used to formulate real-world optimization problems with constraints. Currently, quantum algorithms reformulate the IP into an unconstrained form through the use of binary variables, which is an indirect and resource-consuming way of solving it. We develop an algorithm that maps and solves an IP problem in its original form to any quantum system possessing a large number of accessible internal degrees of freedom that are controlled with sufficient accuracy. This work leverages the principle of superposition to solve the optimization problem. Using a single Rydberg atom as an example, we associate the integer values to electronic states belonging to different manifolds and implement a selective superposition of different states to solve the full IP problem. The optimal solution is found within a few microseconds for prototypical IP problems with up to eight variables and four constraints. This also includes non-linear IP problems, which are usually harder to solve with classical algorithms when compared to their linear counterparts. Our algorithm for solving IP is benchmarked by a well-known classical algorithm (branch and bound) in terms of the number of steps needed for convergence to the solution. This approach carries the potential to improve the solutions obtained for larger-size problems using hybrid quantum–classical algorithms.

arXiv:2402.16541•Quantum Science and Technology•Jul 24, 2024•4 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.
This research proposes a method for finding bounds in binary integer programming (BIP) and quadratic binary integer programming (QBIP). Our approach utilizes a max-flow technique within the framework of quadratic pseudo-Boolean optimization. We apply Lagrange multipliers to transform these problems into a quadratic pseudo-Boolean format, enabling us to create a corresponding network. We develop sufficient conditions under which a flow can or cannot be established in this network. The upper bound of the original problem is obtained through a feasible flow within the network. Additionally, we provide the optimality conditions for the solutions discussed in this paper. We have derived the closed forms for the various functions and values commonly used in our proposed method, as well as a lower bound for both BIP and QBIP, which can assist in solving these problems. This paper includes examples that illustrate both networks containing flows and those that do not, as well as examples that demonstrate lower and upper bound solutions as identified by our method. Furthermore, since our approach can also be applied to Quadratic Unconstrained Binary Optimization (QUBO), we provide the closed forms for the frequently used functions and values in that context, along with an example showcasing its application to a quadratic unconstrained optimization problem.
Abstract Integer programming (IP), as the name suggests is an integer-variable-based approach commonly used to formulate real-world optimization problems with constraints. Currently, quantum algorithms reformulate the IP into an unconstrained form through the use of binary variables, which is an indirect and resource-consuming way of solving it. We develop an algorithm that maps and solves an IP problem in its original form to any quantum system possessing a large number of accessible internal degrees of freedom that are controlled with sufficient accuracy. This work leverages the principle of superposition to solve the optimization problem. Using a single Rydberg atom as an example, we associate the integer values to electronic states belonging to different manifolds and implement a selective superposition of different states to solve the full IP problem. The optimal solution is found within a few microseconds for prototypical IP problems with up to eight variables and four constraints. This also includes non-linear IP problems, which are usually harder to solve with classical algorithms when compared to their linear counterparts. Our algorithm for solving IP is benchmarked by a well-known classical algorithm (branch and bound) in terms of the number of steps needed for convergence to the solution. This approach carries the potential to improve the solutions obtained for larger-size problems using hybrid quantum–classical algorithms.