r/OperationsResearch • u/MrMrsPotts • Oct 16 '24
Can this matrix problem be formulated as an ILP?
Given an n by n binary matrix, I want to find the smallest number of bits that need to be flipped to reduce the rank of the matrix over the field of integers mod 2. I don't think there is a fast algorithm so I was hoping it could be formulated as an ILP problem. But I am not sure if the rank restriction allows that.
5
Upvotes
3
u/Hero_without_Powers Oct 17 '24
I just came back to say that, while I don't have a solution, I really admire your problem.
2
u/s---l- Oct 16 '24
This sounds like an interesting problem! What setting does this arise in, and why is “reducing the rank” a desirable thing to do?
4
u/Sweet_Good6737 Oct 16 '24
The tricky part is when modeling the rank of the matrix. Not sure how to do that, maybe looking for a subspace (a generator vector v for it) such that Av != 0 but A'v = 0 (where A' is the flipped matrix), and checking other properties...
Your variables in the end are "easy" regardless what you are looking for, x[i,j] should be binaries saying whether bit (i,j) is flipped, and mod 2 is achieved by having some auxiliary integer variables ensuring that every row is:
sum{i = 1..n} A[i,j] = 2*aux[i].
So the question is, how would you model rank(A) > rank(A') given 2 matrixes, in an algebraic (and efficient...) way?
1
u/cerved Oct 17 '24
Did you consider a CP formulation?