Mixed Integer Linear Programming Method for Energy-Based Model Trapping Sets Enumerating
Vasiliy S. Usatyuk, Sergey I. Egorov · 2024
The paper introduces an efficient method for identifying trapping sets in codes on the graphs, employing a mixed linear programming approach. The method guarantees a comprehensive search, essential for nonlinear channels in communication systems, energy-based models, natural language processing DNN, metric learning and other intricate dynamic systems. An in-depth analysis of symmetry and asymmetry properties of dynamic systems, represented by trapping sets TS(a, 0)-codewords and TS(a, b)-pseudocodewords respectively, offers a thorough understanding of their dynamics. Implemented in Python, the proposed method is publicly available on GitHub and supports both the Community Edition version, with restrictions on the number of conditions, and the Commercial Edition CPLEX. The technique involves solving a mixed integer linear programming problem using a predefined list of variable nodes participating in the shortest (short) cycles with small Extrinsic Message Degree values within the code graph. These cycles, akin to topological invariants, represent multidimensional voids formed by code and pseudo-code words. Consequently, the method can be viewed as an approach for constructing topological complexes and calculating topological invariants. The method was applied to search for trapping sets in LDPC codes, utilizing the mathematical linear programming package IBM CPLEX Optimization Studio version 22.1.0.0 The computations ran on a 16-core AMD Ryzen 3950X processor with 128GB KF3200 DDR4 RAM, utilizing 32 threads. In the Margulis code (2640, 1320), the proposed method identified the trapping set TS(6,6) in just 0.29 seconds. Notably, compared to the Velasquez-Subramani method, the proposed method achieved a speedup of 15082 times. Leveraging its high speed and thorough search capabilities, the method successfully identified trapping sets TS(62,16) and TS(52,14) for the first time in the Margulis code (4896, 2474). Finally, employing the proposed method with CPLEX Community Edition version 22.1.1.0, we discovered trapping sets, specifically$TS(102,2)$and$TS(108,4)$, within the Mackay LDPC code (408,204). These findings necessitated a brute-force trapping set search, demanding more than 10101operations.