How to refactor binary quadratic constraint to linear form when using MVar

Answered

Hancheng Li

April 19, 2023 14:54

• 
• 
• 

I'm trying to refactor this quadratic constraint to linear form:
var_1 = var_2 · var_3
where var_1 is a dimension (a * b) binary MVar, var_2 is a dimension (a * c) binary MVar, and var_3 is a dimension (c * b) binary MVar

I see from https://support.gurobi.com/hc/en-us/community/posts/7015136566801/comments/8261130871057 that we can convert product of two binary variables to sum, but I couldn't figure out an efficient way to make it work for matrices. I want to avoid using addConstrs and looping over individual terms, as the problem I'm solving has pretty big dimensions and for loop blows up runtime significantly.

Thanks in advance!

Related to

• Matrix API

0

• 

  Simranjit Kaur

  • Gurobi Staff

  April 21, 2023 09:20 Edited

  Hi Hancheng,

  If \(x,y\) and \(z\) are (a,c), (c,b) and (a,b) dimensional matrices, and \(z  = x*y\), then each term of z will be a sum of k terms \[ z_{ij} = \sum_{k=0}^{c-1} x_{i,k} y_{k,j} \]

  We can write \( z = w0 + w1 +...+ w(c-1) \), where \(wn\) is a (a,b) dimensional matrix obtained from multiplying the nth column and nth row of matrices x and y, respectively. 

  For example, if a,b and c are 2, then \( z = w0 + w1 \), where \[ w0 = \begin{bmatrix} x_{00} \\  x_{10} \end{bmatrix} * \begin{bmatrix} y_{00} & y_{01} \end{bmatrix}  = \begin{bmatrix}x_{00}y_{00} & x_{00}y_{01}\\ x_{10}y_{00} & x_{10}y_{01}\end{bmatrix}\]

  \[ w1 =  \begin{bmatrix} x_{01} \\ x_{11} \end{bmatrix} * \begin{bmatrix} y_{10} & y_{11} \end{bmatrix}  = \begin{bmatrix}x_{01}y_{10} & x_{01}y_{11}\\ x_{11}y_{10} & x_{11}y_{11}\end{bmatrix}\]

  Once expressed in this form, we can linearise the terms of w matrices using the logic of this post as follows:

  import gurobipy as gp
  from gurobipy import GRB
  import numpy as np
  a = 2
  b = 3
  c = 2
  
  m = gp.Model()
  
  Z = m.addMVar((a,b), vtype=GRB.BINARY, name="z" )
  X = m.addMVar((a,c), vtype=GRB.BINARY, name="x" )
  Y = m.addMVar((c,b), vtype=GRB.BINARY, name="y" )
  
  # add auxillary variables W to linearise the products in Z
  W = dict()
  for i in range(c):
      W[i] = m.addMVar((a,b), vtype=GRB.BINARY, name="w"+str(i) )
  
      # get ith column of X and ith row of Y
      Xi = X[:,i]
      Yi = Y[i,:]
  
      # add linearization constraints to linearise terms
      m.addConstr( W[i] <= Xi[:,np.newaxis] )
      m.addConstr( W[i] <= Yi )
      m.addConstr( W[i] >= Xi[:,np.newaxis] + Yi - 1)
  
  # add constraint Z = W0 + W1 + .. + W(c-1)
  m.addConstr( Z == sum( W[i] for i in range(c) ) )

  Another option is to keep the quadratic constraint without linearizing the terms 

  m.addConstr( Z == X @ Y )

  and solve the quadratic model with the parameter setting NonConvex=2. 

   

  Regards,

  Simran

  1

Please sign in to leave a comment.