Binary Quadratic Programming
Answered
How 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 pre-defined 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