I'm trying to solve the following optimization problem.
A is a rectangular matrix with coefficients in the finite field Z/2Z (size less than 1000 X 1000). I have a system of the form A.X = Y (X and Y are vectors). And I'm looking for X such that the Hamming weight of Y is maximal.
In the best case, there would be a solution with Y_i = 1 for all i, and I would find it using the Gauss algorithm. But I know it's not the case.
So far, I haven't found a better algorithm than a random/greedy local search, but I'm sure I can use some maths to get a better solution. I've considered running a Gauss algorithm starting with B = (1,...,1) and somehow backtrack when a run into a contradiction (and switch the b_i that prevent me to get a solution). Could matrix factorization help somehow?