This is basically a retranslation of the problem into algebraic language. We are given an $n\times(n+k)$ matrix $A$ with entries in $GF(2)$ of the form $A=(I_n\mid B)$, where the matrix $B$ has no zero rows or columns (in practice it can probably be carefully designed, but the question is about finding a working general approach).

The problem at hand is to partition the columns of $A$ into at most $m$ subsets of size at most $b$ with the following property (so obviously $mb\ge n+k$): the removal of any single one of the subsets of columns in the partition leaves us a matrix $A'$ that is of full rank $n$.

The OP seems to be willing to relax the design goal somewhat and offers as an alternative goal to minimize the number of 'critical' partitions whose removal violates the rank criterion. This may be necessary for some combinations of parameters (and a bad value of $B$). OTOH from the point of view of the probable application (if $m$ is 'large') one might also want to optimize the chanches that the removal of any two (or more) partitions of columns still leaves a full rank matrix, but that is a generalization of the original question.

My guess is that an accurate general algorithm may have prohibitively high complexity and offer a natural greedy algorithm of keeping assigning columns to partitions unless the rank condition is violated and hoping for the best (increasing $m$ on the fly if need be). Add reruns and a non-deterministic starting order to the mix.

This is basically a retranslation of the problem into algebraic language. We are given an $n\times(n+k)$ matrix $A$ with entries in $GF(2)$ of the form $A=(I_n\mid B)$, where the matrix $B$ has no zero rows or columns (in practice it can probably be carefully designed, but the question is about finding a working general approach).

The problem at hand is to partition the columns of $A$ into at most $m$ subsets of size at most $b$ with the following property (so obviously $mb\ge n+k$): the removal of any single one of the subsets of columns in the partition leaves us a matrix $A'$ that is of full rank $n$.

The OP seems to be willing to relax the design goal somewhat and offers as an alternative goal to minimize the number of 'critical' partitions whose removal violates the rank criterion. This may be necessary for some combinations of parameters (and a bad value of $B$), so it is understandable, given that he seems to be looking for a general method. OTOH from the point of view of the probable application (if $m$ is 'large') one might also want to optimize the chanches that the removal of any two (or more) partitions of columns still leaves a full rank matrix, but that is a generalization of the original question.

My guess is that an accurate general algorithm may have prohibitively high complexity and offer a natural greedy algorithm of keeping assigning columns to partitions unless the rank condition is violated and hoping for the best (increasing $m$ on the fly if need be). Add reruns and a non-deterministic starting order to the mix.