Solving Integer Programming Based on DNA Strand Displacement
摘要
DNA strand displacement (DSD) computing, as a novel bio-computing method, utilizes chemical reactions between DNA molecules for information processing, demonstrating powerful parallel computing capabilities and efficient solutions for discrete problems. This paper explores the application of DSD technology in solving integer programming problems. By designing appropriate chemical reaction networks (CRNs), DNA computation can simulate the optimization process in integer programming, where each DNA molecule represents a potential solution and molecular displacement reactions correspond to steps in the search and optimization process. We propose a strategy for solving both linear and nonlinear integer programming problems using DSD reactions, highlighting the importance of constructing reaction networks and the key role of information transfer between molecules. Compared to traditional computational methods, DSD computing can perform large-scale parallel computation in extremely small spaces, handle more complex constraints, and naturally offers fault tolerance. Through experimental validation, the approach using DNA strand displacement to solve integer programming problems demonstrates its potential in optimization tasks, especially showing significant advantages in solving high-dimensional and large-scale integer programming problems.