Maximum-weight codeword in a linear code I was dealing with an optimization problem, that happens to be equivalent to finding a max-weight codeword in a linear code, over $\mathbb{F}_2$. In other words, $A$ being the parity-check matrix, and $w(x)$ the Hamming weight of $x$, the problem is $$\max w(x), \text{ s. t. } Ax = 0 \mod 2.$$
I know this problem is NP-Hard but I wondered if it had a specific name, because searching the literature only leads me to the maximum-likelihood decoding problem, which is a more general case, and the methods do not apply to prohibitively large dimensions (here, I deal with a code of length 1000 and dimension 300, which is a very big instance...)
I use the following heuristic to solve it, but I think it could be improved:
I build the parity-check matrix $(A | I_{700})$ (coefficients in $\mathbb{F}_2$), where $A$ is a matrix $700 \times 300$ and since my solution space is its null space, I try to find the largest column set that sums to $0$. To do so, I randomly select a subset $S$ of the columns of $A$. Summing these columns gives a vector $v$. For each component $1 \leq i \leq 700$ such that $v_i = 1$, I add the column $e_i$ ($i$-th 'unit' vector) to the column set. In other words, I use the convenient fact that I have unit vectors in the parity-check matrix to ensure that the final set of columns sums to 0. This operation is repeated and the best set is recorded. This method gives really good solutions if it runs long enough, but relies too much on randomness, and there must be better ideas. (Linear Programming is really bad for this problem, especially for large sizes, unfortunately)
If anyone has ever studied this problem or a similar one, please feel free to give me some references that might be useful.
Thanks in advance
 A: A few words on the computation of the maximum weight:
For practical purposes, the Brouwer-Zimmermann algorithm is the best known algorithm for the computation of the minimum weight of a linear code. It can be adapted in an obvious way to compute the maximum weight. See my description of the algorithm in this answer.
I guess your parameters (length $n = 1000$) will be too large for the algorithm to terminate within a reasonable amount of time unless the maximum weight is very close to $n$. It still might make sense to run the algorithm, since at any point it gives you a lower and upper bound on the maximum weight, which subsequently get sharpened until they coincide.
Addition
I have another idea, which might or might not help in your situation. If you augment the code $C$ by the all-1-vector $\boldsymbol 1$ to a linear code $C'$ (such that $\operatorname{dim} C' = \operatorname{dim} C + 1$), for each original codeword $\boldsymbol c\in C$ of weight $w$ the code $C'$ will also contain the codeword $\boldsymbol c + \boldsymbol 1$ of weight $n-w$. Hence, you could apply the standard Brouwer-Zimmermann algorithm to the code $C'$. (The computer algebra system Magma contains an efficient implementation.) Each lower bound $b$ on the minimum weight of $C'$ will give an upper bound $n - b$ on the maximum weight of $C$.
The lower the minimum distance of $C$, the more useless this approach is...
A: In the context of maximum-likelihood decoding, your problem is equivalent to decoding an all-ones received tuple (assuming a BSC with $p<1/2$, of course).
I don't know of any efficient general method for large dimensions. If the parity-check matrix is sparse (few ones), the approach of LDPC codes (where "messages" are iteratively passed along "connected" nodes which represent the unknown codeword values, the received values and the parity-check equations) might interest you.
