Skip to main content

Convert Binary Linear Program to Convex Quadratic Program

Answered

Comments

2 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
    Curious
    Conversationalist

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

    0

Please sign in to leave a comment.