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 problems in combinatorics by efficient enumeration.
A wide range of combinatorial problems in operations research falls under arc routing problems, a domain which focuses on arc or edge features rather than node or vertex attributes. The generalized directed rural postman problem is a generic type of problem with the goal of finding the shortest path utilizing at least an edge from each category in a graph with labeled edges. Another is the undirected rural postman problem, a well-known problem in arc routing that seeks to determine a minimum cost walk that traverses a certain set of required edges on a given graph. The problems, arising in numerous real-world applications, are nondeterministic polynomial-time hard.
In brief, an extension to the frontier-based 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. Results are juxtaposed against standard integer programming in establishing the relative superiority of the new technique.
A solution to the undirected rural postman problem based on the zero-suppressed binary decision diagram is also presented. Through an extension to the frontier-based search method of diagram construction, the approach solves the problem by efficient enumeration, producing all feasible routes in addition to the optimal route. Instances of the problem put forward in literature are then solved as benchmark for the decision-diagram-based solution. As reasonable time is consumed, the method also proves to be a practicable candidate in solving the problem.
Given the aforementioned routines, the study expands the utility of the zero-suppressed binary decision diagram through advancing an original graph measure -- the relative isolation probability of a vertex -- in seeking to interpret a consequential edge metric from a vertex-centric perspective. Concisely, the probability of relative isolation pertains to the likelihood of a vertex to be disconnected from all designated source vertices in a graph with probability-weighted edges. A two-step algorithm for efficient calculation is presented and evaluated. Contained within the procedure is a Monte Carlo simulation and the use of the zero-suppressed binary decision diagram, efficiently constructed through the frontier-based search. The novel measure is then computed for a diverse set of graphs, serving as benchmark for the proposed method. In closing, case studies on real-world networks are performed to ensure the consistency of the experimental with the actual.