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.
Article
Concerning a Decision-Diagram-Based Solution to the Generalized Directed Rural Postman Problem
Mathematics Faculty Publications
Document Type
Article
Publication Date
6-1-2020
Disciplines
Abstract
Citation Information
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.