AND/OR Branch-and-Bound on a Computational Grid
Authors: Lars Otten, Rina Dechter
JAIR 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We conduct extensive empirical evaluation on hundreds of CPUs, the first of its kind, with overall positive results. In a significant number of cases parallel speedup is close to the theoretical maximum and we are able to solve many very complex problem instances orders of magnitude faster than before; yet analysis of certain results also serves to demonstrate the inherent limitations of the approach due to the aforementioned redundancies. |
| Researcher Affiliation | Academia | Lars Otten EMAIL Rina Dechter EMAIL Department of Computer Science University of California, Irvine Irvine, CA 92697, U.S.A. |
| Pseudocode | Yes | Algorithm 1 AND/OR Branch-and-Bound (AOBB) Given: Optimization problem (X, D, F, max, Q) and pseudo tree T with root Xo , heuristic h . Output: cost of optimal solution ... Algorithm 2 Master process for fixed-depth parallelization. ... Algorithm 3 Master process for variable-depth parallelization. |
| Open Source Code | Yes | The full source code of our C++ implementation is accessible under an open-source GPL license at http://github.com/lotten/daoopt , which also has the problem instances used for evaluation available for download. |
| Open Datasets | Yes | The full source code of our C++ implementation is accessible under an open-source GPL license at http://github.com/lotten/daoopt , which also has the problem instances used for evaluation available for download. ... Linkage analysis ( pedigree ): ... have been included in recent inference competitions (Darwiche, Dechter, Choi, Gogate, & Otten, 2008; Elidan & Globerson, 2010). ... Haplotype inference ( large Fam ): ... (Fishelson, Dovgolevsky, & Geiger, 2005; Allen & Darwiche, 2008). ... Protein side-chain prediction ( pdb ): ... (Yanover, Schueler-Furman, & Weiss, 2008). ... Grid networks ( 75): ... From the original set of problems used in the UAI 08 Evaluation, only a handful proved difficult enough for inclusion here (Darwiche et al., 2008). |
| Dataset Splits | No | We compiled one common set of 17,000 sample subproblems, drawn from previous fixed-depth parallel experiments on instances from all different problem domains considered. Namely, we sample subproblems from fixed-depth parallel runs of the four different problem classes (see Section 5). We select at most 250 subproblems from each run so that the resulting set is not overly skewed towards harder problem instances or larger problem classes. The end result is a sample set with approx. 40% linkage, 25% side-chain prediction, 25% haplotyping and 10% grid network subproblem instances. For the purpose of this article we learn one global prediction model which will be the basis for the experimental evaluation in Section 5. ... Figure 6 compares the actual complexity (in terms of required AOBB node expansions) of all subproblem samples against the predicted complexity, using 5-fold cross validation. While the paper describes how it splits an optimization problem into subproblems for parallel processing, and uses 5-fold cross-validation for a secondary complexity prediction model, it does not provide traditional training/test/validation splits for the primary optimization problem instances being solved. |
| Hardware Specification | Yes | Experimental evaluation was conducted on an in-house cluster of 27 computer systems, each with dual 2.67 GHz Intel Xeon X5650 6-core CPUs and 24 GB of RAM, running a recent 64-bit Linux operating system. This makes for a total of 324 CPU cores with 2GB of available RAM per core. ... The master host of our parallel scheme as well as the Condor HT grid scheduler was a separate, dedicated 2.83 GHZ Intel Xeon X3363 quad-core system with 16 GB of RAM. |
| Software Dependencies | No | The full source code of our C++ implementation is accessible under an open-source GPL license at http://github.com/lotten/daoopt... Internally, Superlink-Online is built upon a specific grid software package, also called middleware, the Condor HT distributed workload management system for high-throughput computing (formerly just Condor, cf. Thain, Tannenbaum, & Livny, 2002, 2005)... While programming language (C++) and a grid management system (Condor HT) are mentioned, specific version numbers for these or other libraries/operating systems are not provided. |
| Experiment Setup | Yes | In our experiments (cf. Section 5) we will mostly rely on an idealized grid environment (i.e., with a stable number of processors and little to no interference from other users), but also some carefully designed simulations. ... The i-bound values for the heuristic in our experiments were chosen according to two criteria: Feasibility: Larger i-bounds imply a larger mini-bucket structure (size exponential in i), so the limit of 2 GB memory per core implies a natural boundary. For instance, the large domain sizes of up to k = 81 render i = 3 the highest possible value for pdb instances (cf. Section 5.4.3). ... We choose to conduct all experiments with 20, 100, and 500 CPUs, to capture and assess small-, medium-, and relatively large-scale parallelism. |