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.