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 !
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
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 -
Post is closed for comments.
Comments
5 comments