• Gurobi Staff

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

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.

• Gurobi Staff

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

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.

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 gpimport numpy as npimport galoisif __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:8gurobi got the result： 7The 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?

Wenny

• Gurobi Staff

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

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:7gurobi got the result： 7The rank on a binary field:6

Do you know why that is？Thank you so much!

-Wenny

• Gurobi Staff

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")

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

Hi Riley,

Thank you very much for your answer!So far, the code has always passed the test.

-Wenny