Binary Quadratic Programming
AnsweredHow Gurobi get the binary results?
The general BQP problem I am solving is above, where the binary variables relaxed into continuous. I could get binary results directly with Gurobi solver in CVX, where the constraint is strengthened by adding 0<=x_i <=1.
However, when I change the solver to the default solver  SDPT3, the results are continuous. I just wonder how Gurobi change the continuous results into binary.
I knew there might be something like Gaussian Randomization, but I just wonder how it could satisfy the linear constraints at the same time.
I wish you could help me about this. Thank you !

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 predefined tolerance, i.e., there should be very close to the actual binary solution values.
Best regards,
Jaromił0 
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!
0 
You can find good resources in the stackexchange post How to linearize the product of two binary variables?
0 
Sorry to respond you so late.
The figure comes from the work https://scholar.google.com/scholar?hl=en&as_sdt=0%2C5&q=Binary+quadratic+optimization+Nissfolk%2C&btnG=
Additionally, you can check the following paper where an efficient method is proposed to solve the BQP problem which guarantees to approach local optimum https://ieeexplore.ieee.org/abstract/document/9923617
0
Please sign in to leave a comment.
Comments
4 comments