Paper Info
Title
Bdd-Constrained Search: A Unified Approach To Constrained Shortest Path Problems
Abstract
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.
Year
Venue
Field
2015
PROCEEDINGS OF THE TWENTY-NINTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE
Dynamic programming,Mathematical optimization,Shortest path problem,Computer science,Binary decision diagram,Directed acyclic graph,Integer programming,Artificial intelligence,Knapsack problem,Solver,Time complexity,Machine learning
DocType
Citations 
PageRank 
Conference
2
0.40
References 
Authors
13
4
Name
Order
Citations
PageRank
Masaaki Nishino12810.34
Norihito Yasuda27212.56
Shin-ichi Minato372584.72
Masaaki Nagata457377.86