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.


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


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

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


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

Option Associated with Automatic

Was this helpful?
Please make sure you fill the comments section before sending.

Thank you for your comments.
Please contact us if you need any further support.