[4K2-OS-16b] [Organized Session] OS-16

[4K2-OS-16b-03] Solving Various Network Design Problems Using ZDDs

〇Hirofumi Suzuki¹, Masakazu Ishihata¹, Shin-ichi Minato¹ (1. Graduate School of Information Science and Technology, Hokkaido University)

Keywords:Network Design Problem, ZDD, Constraint Satisfaction

Network design is an important issue for several services and systems such as transportation and telecommunication, and is formulated as network design problem using graph structures. Given a graph and constraints, the goal of the problem is to find a constrained subgraph that satisfies given constraints. For some representative constraints, many algorithms have been proposed. However, they are not enough in some applications, because more general and non-mathematical constraints can be required. Therefore, we aim to obtain a set of all constrained subgraphs for supporting to select a suitable one, and propose a unified approach for network design problems. Our approach describes a set of all constrained subgraphs by an equation using some set family operations. To process described equation, we utilize zero-suppressed binary decision diagrams (ZDDs) that manipulate set families in compact form. We applied our approach to some benchmark instances with representative constraints, and obtained sets of all constrained subgraphs in reasonable time.