Creating model takes too much time when big matrices are used
AnsweredHi All
I have a problem that minimizes the following:
minimize trace(A^TBA)
where the matrices A and B have the following dimension
A = (3038 x 2000)
B = (3038 x 3038)
I write the objective function as
m.setObjective(np.trace(np.dot(np.dot(np.transpose(A),B),A)))
It takes couple of hours for Gurobi to model this objective. Is there any faster way?
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
Hi,
In the following I assume that you want to create a linear expression where the coefficients are given by the trace of \(A^T B A\) and the matrices \(A\) and \(B\) hold some linear expressions of the form \(a_{ij} x_i \) and \(b_{ij} x_i \).
It is recommended to avoid the construction of large linear expressions via single summation. This is done when you execute the \(\texttt{dot}\) and \(\texttt{trace}\) function on matrices holding linear expression instead of (floating) numbers only.
You can avoid this overhead by working with (floating) numbers only in the matrices \(A\) and \(B\). Then you compute the diagonal of \(A^T B A\) as \(\texttt{D = np.diagonal(np.dot(np.dot(np.transpose(A),B),A))}\). Finally, you construct the large linear expression as \(\texttt{myExpr=LinExpr(D,myVars)}\) where \(\texttt{myVars}\) is a list of variables which have to be used to compute the trace in your code.
Here is an example:A = np.random.rand(3038,2000)
B = np.random.rand(3038,3038)
D = np.diagonal(np.dot(np.dot(np.transpose(A),B),A))
myVars = []
for i in range(0,2000)
myVars.append(m.addVar(ub=1,vtype=GRB.CONTINUOUS,name="myVar"+str(i)))
myExpr = LinExpr(D,myVars)
m.setObjective(myExpr)Please let me know if this helped.
Best regards,
Jaromił1 -
-
Hi Jaromił,
Thank you for your help. I think there was one thing that I missed mentioning is that in the expression trace(A^TBA), matrix B is a matrix with Gurobi variables on the diagonal. Ex,
B = [b_1 0 0,.....; 0 b_2 0,...; 0 0 b_3,.....] where b_i are binary Gurobi variables.
Whereas, matrix A is defined something like:
A = np.random.rand(3038,2000)
This complicates finding trace(A^TBA) as B has Gurobi variables.
0 -
-
-
Hi Sagnik,
I understand. This can still be done efficiently as you are interested in the trace only. When you perform the multiplication of \(A^T B A = M\), you see that the diagonal elements of \(M\) are given as \(m_{ii} = \sum_{j=1}^{3038} a_{ji}^2 b_j\). The trace is then given as \( tr = b_1 \cdot (\sum_{i=1}^{2000} a_{1i}^2) + \dots + b_{3038} (\cdot \sum_{i=1}^{2000} a_{3038i}^2)\). This can be then computed efficiently as
A = np.random.rand(3038,2000)
coeffList = [] # here we will store our coefficients, e.g., c_1 = a_1i^2 + ... + a_3038i^2
for i in range(0,3038):
myList = A[i]*A[i] # compute the squares
coeff = sum(myList) # compute the actual coefficient
coeffList.append(coeff)
b = []
for i in range(0,3038):
b.append(m.addVar(vtype=GRB.BINARY,name="myVar"+str(i)))
myExpr = LinExpr(coeffList,b)Note that now the computation of the coefficient is taking the longest. There may be a faster way of computing the coefficients, but keep in mind that in general, performing operations with matrices has a cubic complexity (which is pretty much).
Best regards,
Jaromił0 -
-
Hi Jaromił,
I tried two different ways:
1. First, I tried writing $\textrm{trace}A'BA$ as $\textrm{trace}BAA'$ and then computing $\textrm{trace}BM$ where $M=AA'$ computed offline. This still took a lot of time.
2. I tried your method and it works!
Thank you a lot,
Sagnik
0 -
-
Dear Jaromił,
I am trying to efficiently compute tr(A'B' B A) where B is a dense (large) matrix with gurobi variables as in the example by Sagnik and A is a numpy matrix (array). Do you have an idea how to efficiently compute the trace of this matrix product using the gurobi api?
Thank you.
C.
0 -
-
-
Hi,
What exactly do you mean by large and dense? If your matrices are fully dense, then there is no good way to avoid high computational times for construction of the expression. The advantage in Sagnik's problem was that the variable matrix \(B\) was a diagonal one and thus, most of the entries when computing the trace were 0.
In your case, one would have to compute every entry of \(A^T B^T B A\) in order to compute the final trace. One possible trick would be to compute the trace as \(tr(A^T A B^T B)\), i.e., compute the coefficient matrix \(A^T A\) and then the variable matrix \(B^T B\). Still, if your matrices are large and dense, there is no trick to do it fast. Moreover, you will obtain quadratic expressions which cannot be handled as efficiently as linear ones posing an additional obstacle.
Best regards,
Jaromił0 -
-
Thank you for you reply, Jaromił!
the dimension of B is about 300,000 x 10. It already takes a while to setup mVar(B) at least with the python api. Actually, your trick that involves creating B'B matrix was what i tried and indeed it speeds up problem construction. Maybe you could give me a hint on what's the fastest way to set up this expressions through the python api. I think creating the constraints for B'B is yet another bottleneck in terms of speed in my problem formulation. Do you know what would be the fastest way to formulate these constraints? Generally, could i gain a lot of speed if i move the entire problem creation step to cpp rather than python?
Thank you very much!
C.
0 -
-
-
Hi,
Do you know what would be the fastest way to formulate these constraints?
With these dimensions, the minimum complexity to compute the dense matrix multiplication would be \(300000^2\) which is way too much, given that all entries are Gurobi variable objects. Before proceeding, I would recommend to try to come up with an alternative formulation to avoid working with such dense and large matrices. With these dimensions, you should also avoid working with bilinear products. You should try to avoid any unnecessary computation and use properties such as \(b_i^2=b_i\) if \(b\) is binary.
Generally, could i gain a lot of speed if i move the entire problem creation step to cpp rather than python?
Working with C++ or C may be faster if correct data structures are used and memory allocations are performed manually (be aware of memory leaks). Just working with \(\texttt{std::vector}\) instead of a Python list won't gain you a lot of performance.
The main bottleneck in your case remains the density and size of your matrices. You could try to come up with a straight formula for your case of the trace of \(A^T A B^T B\). Sagnik, above, did not have to perform the full matrix multiplications in order to compute the trace which made it possible to boost the construction time. This comparison is a bit unfair given that his dimensions and problem density were way lower.
Best regards,
Jaromił0 -
-
Thank you very much, Jaromił.
0 -
Post is closed for comments.
Comments
10 comments