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





Automatic

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


rfm/rfm1001