 # Binary Quadratic Problem (BQP) Reformulation Method

What is BQP Reformulation?
Linearisation
Convexification
Automatic

## What is BQP Reformulation?

First things first, binary quadratic problems (BQPs) are problems containing only binary variables with a quadratic objective function and linear constraints. Octeract Engine currently offers two methods for reformulating BQPs - linearisation and convexification. The subsequent reformulations can then be solved more easily using linear optimisation or convex optimisation techniques, respectively.

## Linearisation

The idea here is to replace bilinear terms of the form, where $${x}\cdot{y}$$, where $$x,y\in\{0,1\}$$ are binary variables, by a new variable $$w$$, while adding new linear constraints as necessary. With this method, there are two cases:

• Case 1: $${x}={y}$$
Since $$x$$ is a binary variable, the term $$x^2$$ can be directly replaced by a new binary variable $$w$$ which appears linearly.
• Case 2: $${x}\neq{y}$$
In this case, we replace the term $${x}\cdot{y}$$ by a new binary variable $$w$$, and we add the linear constraints:
• $$w-x\le\,{0}$$
• $$w-y\le\,{0}$$
• $$x+y-w\le\,{1}$$

## Convexification

With this method, the idea is to add a correction term to the objective function, making it convex. To get a better idea of what this looks like, let the original objective function be of the form $$f(x)=c+a^{T}x+x^{T}Qx,$$ where $$x,a\in\mathbb{R}^{n}$$ and $$Q\in\mathbb{R}^{{n}\times{n}}$$ be the smallest eigenvalue of the Hessian matrix $$\text{Hess}f$$. It’s important to note that if $$e$$ is non-negative, then $$f$$ is already convex. Hence, we can assume $$e<0$$.

Now let the new objective function be $$\widetilde{f}(x):=f(x)-e\sum_{i}(x_{i}^{2}-x_{i}).$$

Then we can derive that $$\text{Hess}\widetilde{f}=\text{Hess}f-2e\,I$$

where $$I$$ is the $${n}\times{n}$$ identity matrix. We can readily conclude that the eigenvalues of $$\text{Hess}\widetilde{f}$$ are non-negative and hence $$\widetilde{f}$$ is convex.

## Automatic

If this value is selected, the Octeract Engine will first try to reformulate BQPs by linearisation and, if unsuccessful, it will try convexification.