论文标题
与二进制线性代码的冗余奇偶校验检查相关的禁止剪切的确切分离
Exact separation of forbidden-set cuts associated with redundant parity checks of binary linear codes
论文作者
论文摘要
近年来，开发了几种整数编程方法（IP）方法，以最大程度地解码和二进制线性代码的最小距离计算。特别是有两个方面已被证明是为了提高IP解决器的性能以及自适应线性编程解码器：禁止设定（FS）不平等的动态生成，有效切割平面的家族以及所谓的冗余奇迹检查（RPC）的利用。但是，迄今为止，尚不清楚如何解决确切的RPC分离问题（即确定是否存在任何违反FS不平等的W.R.T.在此注释中，我们证明了此问题的NP固定性。此外，我们制定了一个IP模型，该模型将搜索大多数违反FS削减的搜索与RPC的产生结合在一起，并报告计算实验。从经验上讲，对于最小距离问题的各种实例，事实证明，尽管使用确切的分离IP似乎没有提供计算优势，但显然可以通过结合启发式方法来产生基于RPC的切割，从而完全避免它。
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.
