Document Type
Article
Publication Date
6-2020
Abstract
Decision-diagram-based solutions for discrete optimization have been persistently studied. Among these is the use of the zero-suppressed binary decision diagram, a compact graph-based representation for a specified family of sets. Such a diagram may work out combinatorial problems by efficient enumeration. In brief, an extension to the frontierbased search approach for zero-suppressed binary decision diagram construction is proposed. The modification allows for the inclusion of a class-determined constraint in formulation. Variations of the generalized directed rural postman problem, proven to be nondeterministic polynomial-time hard, are solved on some rapid transit systems as illustration. Lastly, results are juxtaposed against standard integer programming in establishing the relative superiority of the new technique.
Recommended Citation
R. Tan, J. Kawahara , K. Ikeda, A. Garciano, K. See. (2020), Concerning a Decision-Diagram-Based Solution to the Generalized Directed Rural Postman Problem. International Journal of Computer Science, 47, 302-309.
