Skip to main content

Binary Linear Programming or Binary Quadratic Programming Model?




  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Muhieddine,

    Since we are doing a nested loop, does that make the model binary quadratic model? or we only call a model quadratic if there is a multiplication of two decision variables in either objective function or constraint?

    To my knowledge one calls a model quadratic only if there is at least one multiplication of two decision variables.

    A binary quadratic programming model would then be one where all decision variables are binary and it has at least one multiplication of the form \(b_i \cdot b_j, i\neq j\). Note that the property \(i \neq j\) is important because \(b_i^2 = b_i\) for a binary variable \(b_i\).

    One could argue that it is possible to generate an equivalent binary linear model by linearizing the product \(b_i \cdot b_j\) (see this stackexchange post for how to perform a possible linearization). However, the presence of the product \(b_i \cdot b_j\) allows for the use of different specialized algorithms. For example, one could decide to not linearize the product but instead solve the continuous relaxation, i.e., the model where all binary variable are made continuous \(b_i \in [0,1]\), by an interior point algorithm for quadratic continuous models. Thus, it definitely makes sense to differ between a binary linear and a binary quadratic programming model.

    Best regards, 

  • Muhieddine Shebaro
    First Comment
    First Question

    Thank you for your clarification!


Please sign in to leave a comment.