How to use gurobi to describe the process of finding the rank of matrix without objective function？
Answered
If have a general square matrix[[1,1,0],[1,1,0],[0,0,0]].(the element is on a binary field--Galois Fields) I want to find the rank of this matrix(like the function:np.linalg.matrix_rank). How can describe this process use gurobi?Appreciate your help. Due to the elements in the matrix are related to the vars in the gurobi model.I can't use the function of Numpy directly.
I tried asking a question in the Gurobi community before and got a small model that worked.https://support.gurobi.com/hc/en-us/community/posts/21492875907857-How-to-use-gurobi-to-describe-the-process-of-finding-the-rank-of-matrix This model has a objective function to get the rank.
When I embedded it in my original big model(already has a objective function),the original model affects the optimization process of the rank-finding process.That is, in this multi-objective optimization problem, the rank is always wrong.
This would render the entire model unusable, since the rank should be a deterministic property of the matrix.But now because the optimization process can't get the best, the rank property becomes uncertain.
My original goal was to maximize a "GObj" that is >= 0. If this value can =1, means the model has a solution. In the big model, the rank is required several times(several rank-finding processes are also related to each other).
In order for the rank process to be optimal. I tried to adjust the priority of the object, but even though I set the priority of the rank-finding very high, I still got a lot of wrong ranks. Similarly, I try not to optimize the "GObj", just limit it to >=1 so that the model can has a solution. I still got a lot of wrong ranks.I also tried to make a lot of small adjustments, but nothing worked.
I wonder, in this case, how can the modeling be done so that the rank-finding procedure is must optimal while maximizing "GObj"? Do I have to figure out how to describe the process of finding the rank of matrix without objective function？
To describe my problem in detail, I wrote a demo and uploaded it to github.https://github.com/wenny-kiki/test_math
I really need your help，thank you so much!
-
Hi Wenny,
I took a look at your repo, and while I understood what was happening in the diagram, it was really unclear what the actual optimization problem is. But I did wonder about the following sentences:
In the process of Diffusion,the number of r and b will decrease.The amount decreased corresponds to the variable in the model-"GCD_r{r}_Red/Blue".This corresponds to a rank found by the model.
Is there some other way to model the decrease without appealing to rank? Granted I'm not across the details but my hunch is that there would be if it's simply measuring a decrease in the count of red and blue. I think it would be worth considering, as the assumption that rank can actually be modeled with constraints alone seems quite optimistic. I would take the lack of responses to your question so far as a sign that people simply don't have an answer, and not that they haven't given it some thought.
You could also try posting on or.stackexchange.com
- Riley
1 -
Hi Riley,
Thank you very much for your reply!I want to explain that I'm using gurobi for cryptanalysis.My optimization goal is to find more rounds of attack routes.In my demo,there are only two rounds of attack.
I could model the decrease without appealing to rank or construting a matrix(I've searched for an optimal attack route in this way),but that would lose some accuracy.
So far I can think of a way to model the decrease exactly, and the easiest way is to construct a matrix and find its rank. Otherwise, the situation to judge is actually more complicated(Probably as hard as finding the rank of a matrix with just constraints).If I can implement this process, I may find a longer and better attack route.
as the assumption that rank can actually be modeled with constraints alone seems quite optimistic
I think so(I have done something to try).what a pity...I have another idea, which may not be very mature, because I don't know how gurobi internally computes the inequality to get the optimization goal.
Does gurobi support the concept of "hierarchical optimization"?That is, in the main optimization process, there are sub-optimization processes based only on partial inequalities. The suboptimization process is similar to a black box for the main optimization process.Some variables of the main optimization process are used as inputs to the sub-optimization process, which can lead to a determined output.
I think this is a bit different from gurobi multi-objective optimization that I am currently working with. Multi-objective optimization is to find the optimal values of all objectives under the condition that all inequalities are satisfied. "Hierarchical optimization" can get the optimization of partial inequalities, and the input and output of the subprocess are related to the main process.
If gurobi had supported "hierarchical optimization", my model might have worked.
Thanks again for your help.I will try posting on or.stackexchange.com.
0 -
Hi Wenny,
If gurobi had supported "hierarchical optimization", my model might have worked.
I think "hierarchical optimization" is a broad term, possibly meaning different things to different people. I think we can say that Gurobi supports it in the same way we support Benders Decomposition (which some would say is hierarchical in that you have a master problem and sub-problem(s) which feed information between each other). I expect you can use Gurobi for this but you would have to implement the approach yourself.
- Riley
1 -
Hi Riley,
Thank you so much!That might be a good direction to try.I will try to learn Benders Decomposition and use it in gurobi.
0 -
Hi Riley,
Unfortunately, I found a new problem while doing the tests.I can't deal with it myself but to trouble you again. I'm sorry and your help will be much appreciated!
I find that the following program does not always get the correct rank on a binary field(Galois Fields).
import gurobipy as gp
import numpy as np
import galois
if __name__ == '__main__':
m = gp.Model()
A = np.random.randint(0,2,(8,8), dtype="B")
print(np.array2string(A, separator=', '))
p=A.shape[0]
q=A.shape[1]
M = m.addMVar((p, q), vtype="B", name="M")
scalars = m.addMVar((q, p), lb=-float("inf"), vtype="I", name="scalars")
e_scalars = m.addMVar((p, p), lb=-float("inf"), vtype="I", name="e_scalars")
e_borrowed = m.addMVar(p, vtype="B", name="borrowed")
m.addConstr(M == A)
m.addConstr(M@scalars + e_scalars == np.eye(p))
m.addConstr((e_borrowed == 0) >> (e_scalars.transpose()==0))
m.setObjective(e_borrowed.sum(), gp.GRB.MINIMIZE)
m.optimize()
rank = p - round(m.ObjVal)
print("The rank on a general field:"+str(np.linalg.matrix_rank(A)))
print("gurobi got the result：", rank)
GF = galois.GF(2, repr="poly")
A=GF(A)
print("The rank on a binary field:"+str(np.linalg.matrix_rank(A)))
At first I thought that by setting the type of the variable M to Binary I would be able to perform operations on Galois Fields by default. But now I find many counter-examples, such as[[0, 0, 0, 1, 0, 0, 1, 0],
[1, 1, 0, 0, 0, 0, 1, 1],
[1, 0, 0, 0, 1, 1, 1, 0],
[1, 1, 1, 1, 0, 1, 1, 0],
[1, 0, 1, 0, 0, 0, 1, 0],
[1, 1, 1, 1, 0, 0, 0, 1],
[0, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 0]]The output is
The rank on a general field:8
gurobi got the result： 7
The rank on a binary field:8
I wonder if gurobi supports operations on Galois Fields? If yes, what is wrong with the above code that results in the wrong rank?Thanks again for your help！
Wenny
0 -
Hi Wenny,
I'm not quite sure why the approach doesn't extend to GF2, but leave it with me, I will find time to look at it over the weekend.
- Riley
0 -
Hi Riley,
This condition is not necessary.I changed the type of the variable.
M = m.addMVar((p, q), vtype="B", name="M")
scalars = m.addMVar((q, p), lb=-float("inf"), name="scalars")
e_scalars = m.addMVar((p, p), lb=-float("inf"), name="e_scalars")
e_borrowed = m.addMVar(p, vtype="B", name="borrowed")But I still get the wrong answer,such as:
[[0, 0, 0, 0, 1, 0, 0, 0],
[0, 1, 0, 1, 1, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 1, 0],
[0, 1, 1, 1, 1, 1, 1, 0],
[1, 1, 1, 0, 1, 0, 0, 0],
[1, 0, 1, 1, 0, 0, 1, 0],
[1, 1, 1, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 0, 0]]The output is:
The rank on a general field:7
gurobi got the result： 7
The rank on a binary field:6Do you know why that is？Thank you so much!
-Wenny
0 -
Hi Wenny,
The approach needs to be adjusted to handle the modulo of Galois fields. I think it this approach can be modified by adding some variables:
modulo_aux = m.addMVar((p,p), lb=-float("inf"), vtype="I", name="modulo_aux")and the adjusting the quadratic equality constraint:
m.addConstr(M@scalars + e_scalars == np.eye(p) + 2*modulo_aux)
Having not ever encountered Galois fields before today I'm not 100% confident but the experimental evidence is stacking up.
I also think you will need to have the vtype of scalars and e_scalars as integer, as you originally had it.
- Riley
0 -
Hi Riley,
Thank you very much for your answer!So far, the code has always passed the test.
-Wenny
0
Please sign in to leave a comment.
Comments
9 comments