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.