I'm going through an article with title "Solving constrained quadratic binary problems via quantum adiabatic evolution" (reference 1). And there are several points confusing me a lot.
This article is aimed to solve the CBQP (constrained binary quadratic programming) with the following format.
\begin{align} &\min &x^{T}Qx \cr &\text{subject to} &Ax\leq b \end{align} and $x\in \lbrace0,1\rbrace^{n}$, where $Q\in Z^{n\times n}$ and $A\in Z^{m\times n}$. Let's call this optimization problem the problem $P$.
The outline is like this. Suppose there is a UBQP (Unconstrained binary quadratic programming) oracle, and with the successive application of LP(linear programming), the lagrangian dual of $P$ (or lower bound of $P$ can be provided) can be solved. And then with the branch-bound-approach, the problem $P$ can be solved.
I can understand almost of it until the section 5 counting the solution density on page 9. I'm not exactly sure how the branch-bound process is combined with the optimization process to finally tackle this problem. Could anyone point a direction or share some thoughts? Any comments would be greatly appreciated.
References
- Ronagh, P., Woods, B., & Iranmanesh, E. (2015). Solving constrained quadratic binary problems via quantum adiabatic evolution. arXiv preprint:1509.05001.
