1. Home
2. Docs
3. Math blog
4. BQP Reformulations

# BQP Reformulations

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 $$xy$$, 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 $$xy$$ by a new binary variable $$w$$, and we add the linear constraints:
• $$w-x\leq 0$$
• $$w-y\leq 0$$
• $$x+y-w\leq 1$$
##### Relevant options
• BQP_REFORMULATION_METHOD = LINEAR
• BQP_REFORMULATION_METHOD = SSLINEAR (Sherali-Smith)

## 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+\alpha^Tx+x^TQx, x\alpha\in\mathbb{R}^n,Q\in\mathbb{R}^{n\times n}$$

Let $$e$$ be the smallest eigenvalue of the Hessian matrix $$Hessf$$. Obviously, if $$e$$is non-negative, then $$f$$ is already convex. Hence, we assume $$e\lt0$$.

Now let the new objective function be

$$\tilde f(x) := f(x) – e \sum_i(x_i^2-x_i)$$

Then we can derive that

$$Hess\tilde f=Hess f-2e I$$

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

##### Relevant option
• BQP_REFORMULATION_METHOD = QUADRATIC

## 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.

## Automatic

If BQP_REFORMULATION_METHOD = AUTOMATIC, the Octeract Engine will use black magic to figure out which method is most likely to work well for your problem.