BDD-Constrained Search: A Unified Approach to Constrained Shortest Path Problems
Authors: Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, Masaaki Nagata
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We conducted experiments to evaluate our BCS algorithm in situations where the problems in the DAGOPTPATH are solved with additional constraints. ... Experimental results are shown in Tab.2, where width is the width of the BDD, and the steps is the actual number of updating processes executed on the problem. BCS time and BDD time are running time for BCS algorithm and BDD construction, respectively. We can see that for all settings the proposed method can find the optimal path faster than CPLEX. |
| Researcher Affiliation | Collaboration | Masaaki Nishino1 and Norihito Yasuda2 and Shin-ichi Minato2,3 and Masaaki Nagata1 1NTT Communication Science Laboratories, NTT Corporation 2ERATO Minato Discrete Structure Manipulation System Project, Japan Science and Technology Agency 3Graduate School of Information Science and Technology, Hokkaido University |
| Pseudocode | Yes | Algorithm 1 BDD-constrained search algorithm |
| Open Source Code | No | Our BCS algorithm was implemented in C++, and we used the CUDD library4 to construct the BDDs representing logical constraints. |
| Open Datasets | Yes | We use four datasets, DAG, Knapsack, Edit distance, and Part-of-speech (POS) tagging... DAG is the task of finding a shortest path in the DAG that represents the citation network of high energy physics phenomenology papers on ar Xiv1. 1https://snap.stanford.edu/data/cit-HepPh.html ... Edit distance is the DAG used in the computation of the edit distance between two strings. The two strings are selected from the DBLPdataset2 which is frequently used in evaluating edit distance computation methods (e.g., (Wang, Li, and Feng 2012; Zhang et al. 2010)). 2http://www.informatik.uni-trier.de/ ley/db/ ... POS tagging is the DAG created when applying the HMM-based POS tagging algorithm to a word sequence. We use the HMM-based POS tagger contained in the Natural Language Toolkit Python library3. 3http://www.nltk.org/ |
| Dataset Splits | No | The paper describes the datasets used for the experiments but does not explicitly specify train/validation/test splits or their proportions for reproducibility. |
| Hardware Specification | Yes | All experiments were run on a Linux server with a Xeon X5680 3.33 GHz CPU and 48 GB RAM. |
| Software Dependencies | Yes | Our BCS algorithm was implemented in C++, and we used the CUDD library4 to construct the BDDs representing logical constraints. We compared our algorithm with CPLEX 12.5.1.0, a state-of-the-art commercial general purpose ILP solver. |
| Experiment Setup | Yes | Constraints We set two different constraints Checkpoint and Disjunction on each dataset. For Checkpoint constraints, we first randomly select edges with probability ρ, and then partition the set of selected edges into L groups. We used the pairs of parameters (L, ρ) = (3, 0.01) and (5, 0.05) in experiments. We mention these two settings as CHK1 and CHK2, respectively. For Disjunction constraints, we first select the k-best edges that have higher scores, and then randomly generate disjunctive pairs of the selected edges with pair probability γ. We used the pairs of parameters (k, γ) = (50, 0.01) and (100, 0.8) in the experiments. We mention these two constraints as DIS1 and DIS2, respectively. ... We design a 0-1 knapsack problem that consists of 200 items, and the cost and the weight of an item are randomly selected from the range [1, 100]. We set the size of the knapsack to 1000. |