Stochastic Constraint Programming with And-Or Branch-and-Bound
Authors: Behrouz Babaki, Tias Guns, Luc de Raedt
IJCAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 5 Experiments We investigate the following questions: Q1: Does our proposed method improve over existing approaches? Q2: What is the impact of bounding depth on the efficiency of search? Q3: What is the interplay between bounding and constraint propagation? We used two problems in our experiments: Knapsack (based on an example from [Hnich et al., 2011]) [...] Investment [...] Table 1 shows the results. [...] Figure 2 shows that even the shallow bound is much better than no bound. [...] Figure 3 shows that in the absence of bounds, tightening the constraint leads to more failures and fewer nodes; meaning that the search space becomes smaller. |
| Researcher Affiliation | Academia | 1Department of Computer Science, KU Leuven, Belgium 2Department of Business Technology and Operations, VUB, Belgium |
| Pseudocode | Yes | Algorithm 1 And-Or search over domain D following |
| Open Source Code | Yes | The code and data are available online 3. 3https://github.com/Behrouz-Babaki/Factored SCP |
| Open Datasets | No | We used two problems in our experiments: Knapsack (based on an example from [Hnich et al., 2011]) [...] Other distribution parameters for both problems were generated randomly |
| Dataset Splits | No | The paper describes problems like Knapsack and Investment and their setup, but does not provide details on specific training, validation, or test dataset splits. |
| Hardware Specification | No | We ran the experiments on Linux machines with 32 GB of memory. |
| Software Dependencies | Yes | The CP solver used is Gecode-4.4.0 and the MIP solver is Gurobi-6.51. We used the the ACE2 package to compile the Bayesian networks into arithmetic circuits, and ported the inference library to C++ for integration with Gecode. |
| Experiment Setup | No | The time-out used was 1800 seconds. |