2020/04/07 by Christian Puchert, Puchert, Christian, Andreas M. Tillmann +1
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #Information Theory (cs.IT) #Optimization and Control (math.OC) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2004.03387
openalex publication_date 2020/04/07 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
In recent years, several integer programming (IP) approaches were developed\nfor maximum-likelihood decoding and minimum distance computation for binary\nlinear codes. Two aspects in particular have been demonstrated to improve the\nperformance of IP solvers as well as adaptive linear programming decoders: the\ndynamic generation of forbidden-set (FS) inequalities, a family of valid\ncutting planes, and the utilization of so-called redundant parity-checks\n(RPCs). However, to date, it had remained unclear how to solve the exact RPC\nseparation problem (i.e., to determine whether or not there exists any violated\nFS inequality w.r.t. any known or unknown parity-check). In this note, we prove\nNP-hardness of this problem. Moreover, we formulate an IP model that combines\nthe search for most violated FS cuts with the generation of RPCs, and report on\ncomputational experiments. Empirically, for various instances of the minimum\ndistance problem, it turns out that while utilizing the exact separation IP\ndoes not appear to provide a computational advantage, it can apparently be\navoided altogether by combining heuristics to generate RPC-based cuts.\n