A Novel Approach to Search for All Solutions of a Non-Negative Linear Diophantine Equation  
Author Shin-Guang Chen

 
Co-Author(s)

 
Abstract Solving non-negative linear Diophantine equation is the basis for solving most optimization problems. A typical form of such equation is expressed as: a1x1 + a2x2 + : : : + anxn = k. When ai = 1 for all i, the mathematical results show that the number of solutions for such equation is equivalent to the number of distinct terms in a multinomial equation, which would be (kn+k-1). Therefore, the optimal complexity for such search is of O((kn+k-1)). However, there are very limited methods existed in the literature to tackle such kind of problems. This paper proposes a novel and efficient approach to search for all solutions of a non-negative linear Diophantine equation. The complexity of the proposed approach would be no greater than O((kn+k-1)). Several examples are explored to show the application of the proposed approach.

 
Keywords Linear equation, network reliability, minimal path, fast enumeration, backtrack
   
    Article #:  2455
 
Proceedings ISSAT International Conference on Reliability and Quality in Design 2018
August 2-4, 2018 - Toronto, Ontario, Canada