Convert Binary Linear Program to Convex Quadratic Program

Answered

shengzhi lai

• April 26, 2024 08:44

Dear 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 Max-cut, 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!

Related to

• QCP

0

• 

  Jaromił Najman

  Gurobi Staff

  • April 30, 2024 07:51
  • Edited

  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 mixed-integer 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(1-x_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 Branch-and-Bound algorithm. I recommend having a look at our Mixed-Integer 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
• 

  shengzhi lai

  • April 30, 2024 08:22

  

  

  

  Jaromił Najman. Thank you for this very detailed answer! I will check more on this top.

  0

Please sign in to leave a comment.