BDD-Constrained Search: A Unified Approach to Constrained Shortest Path Problems


  • Masaaki Nishino NTT Corporation
  • Norihito Yasuda Japan Science and Technology Agency
  • Shin-ichi Minato Hokkaido University
  • Masaaki Nagata NTT Corporation



Dynamic programming (DP) is a fundamental tool used to obtain exact, optimal solutions for many combinatorial optimization problems. Among these problems, important ones including the knapsack problems and the computation of edit distances between string pairs can be solved with a kind of DP that corresponds to solving the shortest path problem on a directed acyclic graph (DAG). These problems can be solved efficiently with DP, however, in practical situations, we want to solve the customized problems made by adding logical constraints to the original problems. Developing an algorithm specifically for each combination of a problem and a constraint set is unrealistic. The proposed method, BDD-Constrained Search (BCS), exploits a Binary Decision Diagram (BDD) that represents the logical constraints in combination with the DAG that represents the problem. The BCS runs DP on the DAG while using the BDD to check the equivalence and the validity of intermediate solutions to efficiently solve the problem. The important feature of BCS is that it can be applied to problems with various types of logical constraints in a unified way once we represent the constraints as a BDD. We give a theoretical analysis on the time complexity of BCS and also conduct experiments to compare its performance to that of a state-of-the-art integer linear programming solver.




How to Cite

Nishino, M., Yasuda, N., Minato, S.- ichi, & Nagata, M. (2015). BDD-Constrained Search: A Unified Approach to Constrained Shortest Path Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1).



AAAI Technical Track: Heuristic Search and Optimization