# Binary Quadratic Problem (BQP) Reformulation Method

## 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}\)

### Option Associated with Linearisation

## 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}}\). Let \(e\) 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.

### Option Associated with Convexification

## Sherali and Smith Linearisation

If this value is selected, the Octeract Engine linearizes the BQP following Sherali and Smith, “An improved linearization strategy for zero-one quadratic programming problems”, 2007.

### Option Associated with Sherali and Smith Linearisation

## Automatic

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