Binary Linear Programming or Binary Quadratic Programming Model?

Answered

Muhieddine Shebaro

• March 28, 2024 00:27
• Edited

I am confused on the criteria on calling a model a binary linear programming model or a binary quadratic programming model.

For example:

If one of the constraints involves a binary adjacency matrix:

A'ij = 0  ∀(i,j) ∈ N^2 (double nested loop over A')

and in the objective function:

sum(sum((A'ij-Aij)/2)))

where A' is the binary decision matrix and A is a constant binary adjacency matrix of same size.

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?

 

Thank you in advance

 

 

Related to

• Nonlinear

0

• 

  Jaromił Najman

  Gurobi Staff

  • March 28, 2024 08:32

  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, 
  Jaromił

  1
• 

  Muhieddine Shebaro

  • March 28, 2024 08:48

  

  

  Thank you for your clarification!

  0

Please sign in to leave a comment.