Skip to main content

Binary Quadratic Programming

Answered

Comments

1 comment

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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

Please sign in to leave a comment.