• Gurobi Staff

You can reformulate the product of 2 binary variables $$x\cdot y$$ via linear constraints by introducing an additional binary variable $$z$$ and adding the constraints

\begin{align*} z &\leq x\\ z &\leq y\\ z &\geq x + y -1 \end{align*}

For any binary $$x$$, it holds that $$x^2 = x$$. Thus, you can formulate any BQP as a Binary Linear Program and solve it using standard MIP techniques. This is what Gurobi does as a basic approach. Thus, you get binary results (up to a defined tolerance).

There are also other reformulations and adjustments one could apply to BQPs such as Convexification.

I don't know the SDPT3 solver but maybe it is using some different technique which relies on the solution of a continuous master problem which can result in continuous values. Still, the continuous values of the binary variables should not exceed some pre-defined tolerance, i.e., there should be very close to the actual binary solution values.

Best regards,
Jaromił

Hello lin chen,

May I have the reference paper or book of the screenshot in your post? I am working on relaxing a binary linear program. Thank you!

• Gurobi Staff

You can find good resources in the stackexchange post How to linearize the product of two binary variables?