We are given an $n \times (n + k)$ matrix $A$, with entries in GF(2), of the form $A =[I_n\ B]$, where $I_n$ is the $n \times n$ identity matrix, and $B$ has no "zero" rows or columns.
The problem is to partition the columns of $A$ into at most $m$ subsets, each of size at most $b$, such that the number of critical subsets is minimized (with minimum $m$), where a critical subset is a subset of the set of columns such that if we remove it from $A$ the reduced matrix has rank less than $n$.
By the phrase "minimum m" I mean that we want to partition using minimum subsets (at the max we can use $m$ subsets) without sacrificing the number of critical subsets. For example, suppose we are getting the optimum config (i.e number of critical subsets is minimum) with $m_1$ subsets ($m_1$ < $m$), then we need not use all the $m$ subsets. In real world these $m$ subsets are $m$ boxes. If I can get the optimum config with less than $m$ boxes, I need not use the remaining ones, they can be saved. Our aim is to solve the problem for any $n$,$k$,$m$,$b$ and any $A$ matrix with the mentioned properties i.e. we want to design a general polynomial time algorithm or prove that the general algorithm is NP-Complete.
The problem seems NP-Complete to me. It a special case of "set cover/maximum coverage problem" and that's why it is becoming very difficult to reduce from the general set cover/maximum coverage problem.
The elaborate problem definition/relevant discussion can be found at https://math.stackexchange.com/questions/57412/optimization-problem-for-a-parity-check-code. As we could not reach to any solution there, I am posting it here.