How to use gurobi to describe the process of finding the rank of matrix？
Answered
If have a general square matrix[[1,1,0],[1,1,0],[0,0,0]],I want to find the rank of this matrix(like the function:np.linalg.matrix_rank).How can describe this process use gurobi?Actually the elements in the matrix are related to the vars in the gurobi model.Appreciate your help
-
Hi Wenny,
Consider a matrix M with \( p \) rows. If the matrix has rank \( n \) then its columns span a space of dimension \( n \) where \( n \leq p \). If \( n < p \) then there exists a standard basis vector, \( e_i \in \mathbf{R}^p \) for some \( i \in \{1, \ldots, p\} \) such that \( e_i \) is not in the column span. We can add \( e_i \) to the collection of column vectors to increase the dimension spanned by 1.
Now a set of vectors span \( \mathbf{R}^p \) if and only if each standard basis vector \( e_i \) is in the span of the vectors. So the approach to calculate the matrix rank will be to borrow standard basis vectors to add to our column vector span to ensure that we span \( \mathbf{R}^p \) - but borrowing as few standard basis vectors as possible, with the number borrowed equal to \( p - rank(M) \).
m = gp.Model()
p,q = 3,3 # as an example, overwritten for testing
# uncomment the following 3 lines for testing
#A = np.array([[0,1,0], [0,1,0],[0,2,0],[1,0,0]])
#p=A.shape[0]
#q=A.shape[1]
# the matrix (size = (p,q)) of variables whose rank we want to calculate
M = m.addMVar((p,q), lb=-float("inf"), name="M")
#scalars[i,j] is the scalar for the i-th column of M in linear combination for e_j
scalars = m.addMVar((q,p), lb=-float("inf"), name="scalars")
#e_scalars[i,j] is the scalar for e_i in linear combination for e_j
e_scalars = m.addMVar((p,p), lb=-float("inf"), name="scalars")
#e_borrowed[i] == 1 if e_i is "borrowed" to use in creating full dimensional span
e_borrowed = m.addMVar(p, vtype="B")
#each e_i must be in the span of column vectors + span of "borrowed" basis vectors
m.addConstr(M@scalars + e_scalars == np.eye(p))
# if e_[i] is not borrowed then we cannot use it in linear combinations
m.addConstr((e_borrowed == 0) >> (e_scalars.transpose()==0))
#minimize the number of borrowed basis vectors
m.setObjective(e_borrowed.sum(), gp.GRB.MINIMIZE)
# uncomment the following line for testing
#m.addConstr(M == A)
m.optimize()
rank = p - round(m.ObjVal)
# uncomment the following line for testing
#print("Passed test:", np.linalg.matrix_rank(A) == rank)Because the objective function is needed to calculate the rank you will need to be careful if embedding this in a larger model - i.e. take care so that the other constraints, and any addition to the objective don't disturb the downwards pressure on the e_borrowed variables.
- Riley
1 -
Actually,this line always have an error
m.addConstr((e_borrowed == 0) >> (e_scalars.transpose()==0))
File "src\gurobipy\model.pxi", line 3623, in gurobipy.Model.addConstr
File "src\gurobipy\mlinexpr.pxi", line 706, in gurobipy.MLinExpr.item
File "src\gurobipy\mlinexpr.pxi", line 708, in gurobipy.MLinExpr.item
ValueError: can only convert an array of size 1 to a Python scalarI can't find the problem.I really need your help,thank you so much!
0 -
Hi Wenny,
Apologies, the above code only works with Gurobi 11+. Are you able to upgrade?
Or alternatively replace the line that doesn't work with the following, in order to use an earlier version of Gurobi:
for i in range(p):
for j in range(p):
m.addConstr((e_borrowed[i] == 0) >> (e_scalars[i,j]==0))- Riley
1 -
Thanks for your reply！I upgrade Gurobi and get the right result.
0 -
Hi Riley,
I'm sorry to ask you again.Like you mentioned above，when I embedding this code in a larger model，I need add other object.But this affects the minimization of e_borrowed,so I wonder if there is a solution that doesn't use objective function.For example, whether can use gurobi to simulate the process of matrix simplification, and then calculate the number of non-zero rows to represent the rank.
One additional condition that might simplify the problem，that is my matrix contains only 0-1 variables
0 -
Hi Wenny,
I wonder if there is a solution that doesn't use objective function
There may be, but I have my doubts, and in any case I cannot think of one unfortunately.
- Riley
0
Please sign in to leave a comment.
Comments
6 comments