  In recent years, several integer programming (IP) approaches were developed
for maximum-likelihood decoding and minimum distance computation for binary
linear codes. Two aspects in particular have been demonstrated to improve the
performance of IP solvers as well as adaptive linear programming decoders: the
dynamic generation of forbidden-set (FS) inequalities, a family of valid
cutting planes, and the utilization of so-called redundant parity-checks
(RPCs). However, to date, it had remained unclear how to solve the exact RPC
separation problem (i.e., to determine whether or not there exists any violated
FS inequality w.r.t. any known or unknown parity-check). In this note, we prove
NP-hardness of this problem. Moreover, we formulate an IP model that combines
the search for most violated FS cuts with the generation of RPCs, and report on
computational experiments. Empirically, for various instances of the minimum
distance problem, it turns out that while utilizing the exact separation IP
does not appear to provide a computational advantage, it can apparently be
avoided altogether by combining heuristics to generate RPC-based cuts.
