Convert Binary Linear Program to Convex Quadratic Program
AnsweredDear specialists,
I have seen some simple cases that convert a Binary Linear Program (BLP) to a Convex Quadratic Program (CQP) by relaxing the binary variables to continuous ones and introducing some extra variables, such as in this post https://qr.ae/psu9Wr. I manually checked that the optimal solution of the CQP* is also the optimal solution of the BLP*, but I don't know what the technique is called so that I can search more about it (Q1). And I wonder whether this is just a nice case where the optimality gap is 1 (CQP*/BLP*=1) (Q2). I guess that the optimality gap is not guaranteed 1, otherwise it proves P=NP.
Then, I searched some literature and found the method of relaxing a BLP to a Semidefinite Program (SDP) but only some particular problems like Maxcut, Coloring problems are showcased. I wonder whether this is the most used way for BLP relaxation (Q3), and whether all BLP can be relaxed to SDP generally (Q4).
Could you please confirm my guesses or point out my mistakes in Q1, Q2, Q3, and Q4?
Thank you very much!

Hi Shengzhi,
I have seen some simple cases that convert a Binary Linear Program (BLP) to a Convex Quadratic Program (CQP) by relaxing the binary variables to continuous ones and introducing some extra variables, such as in this post https://qr.ae/psu9Wr. I manually checked that the optimal solution of the CQP* is also the optimal solution of the BLP*, but I don't know what the technique is called so that I can search more about it (Q1).
I am not aware of a special name for the technique and most often this reformulation is a bad idea, because you are rewriting every binary variable by a product of 2 continuous variables which are more prone to numerical issues.
And I wonder whether this is just a nice case where the optimality gap is 1 (CQP*/BLP*=1) (Q2).
The optimal solution is guaranteed to be the same for both formulations (up to tolerances).
I guess that the optimality gap is not guaranteed 1, otherwise it proves P=NP.
This does not prove P = NP, because you are replacing a mixedinteger programm by a nonconvex quadratic one. One could argue that this makes the model even more complex. Of course there are exceptions where the nonconvex quadratic formulation performs well but these are rather rare.
Please note that in the post you linked, the author drops the nonconvex relationships \(y_i = x_i\cdot(1x_i)\) out of the model. I don't know why this should be allowed. Maybe for specific models there is a technique to compute the \(x_i\) values out of the \(y_i\) values, but in general this is not possible; in particular not when \(x_i\) appears somewhere else in the model.
I wonder whether this is the most used way for BLP relaxation (Q3)
In general, BLP relaxations are solved via the BranchandBound algorithm. I recommend having a look at our MixedInteger Tutorials. You can learn all basics that you need to know to dive into the mathematical optimization world.
and whether all BLP can be relaxed to SDP generally (Q4)
I am not aware of a general technique to relax a BLP to an SDP. But maybe someone in the Forum knows more about this topic.
I hope this helps.
Best regards,
Jaromił0 
Jaromił Najman. Thank you for this very detailed answer! I will check more on this top.
0
Please sign in to leave a comment.
Comments
2 comments