Accelerating exact and approximate inference for (distributed) discrete optimization with GPUs
From MaRDI portal
Publication:1706596
Abstract: Discrete optimization is a central problem in artificial intelligence. The optimization of the aggregated cost of a network of cost functions arises in a variety of problems including (W)CSP, DCOP, as well as optimization in stochastic variants such as the tasks of finding the most probable explanation (MPE) in belief networks. Inference-based algorithms are powerful techniques for solving discrete optimization problems, which can be used independently or in combination with other techniques. However, their applicability is often limited by their compute intensive nature and their space requirements. This paper proposes the design and implementation of a novel inference-based technique, which exploits modern massively parallel architectures, such as those found in Graphical Processing Units (GPUs), to speed up the resolution of exact and approximated inference-based algorithms for discrete optimization. The paper studies the proposed algorithm in both centralized and distributed optimization contexts. The paper demonstrates that the use of GPUs provides significant advantages in terms of runtime and scalability, achieving up to two orders of magnitude in speedups and showing a considerable reduction in execution time (up to 345 times faster) with respect to a sequential version.
Recommendations
- Parallel exact inference on the cell broadband engine processor
- Publication:3489478
- Efficient inference in Bayes networks as a combinatorial optimization problem
- Sampling-based SAT/ASP multi-model optimization as a framework for probabilistic inference
- Distributed Gibbs: a linear-space sampling-based DCOP algorithm
Cites work
- scientific article; zbMATH DE number 48812 (Why is no real title available?)
- A dynamic programming approach for consistency and propagation for knapsack constraints
- AND/OR branch-and-bound on a computational grid
- Adopt: asynchronous distributed constraint optimization with quality guarantees
- Algorithm for optimal winner determination in combinatorial auctions
- Approximations in Distributed Optimization
- Autonomous agents coordination: action languages meet CLP(\(\mathcal {FD}\)) and Linda
- BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Bucket elimination: A unifying framework for reasoning
- Computational protein design as an optimization problem
- Constrained community-based gene regulatory network inference
- Emergence of Scaling in Random Networks
- Global Grammar Constraints
- Handbook of constraint programming.
- KI 2004: Advances in Artificial Intelligence
- Memory intensive AND/OR search for combinatorial optimization in graphical models
- Mini-buckets: a general scheme for bounded inference
- Network-based heuristics for constraint-satisfaction problems
- Networks of constraints: Fundamental properties and applications to picture processing
- Principles and Practice of Constraint Programming – CP 2004
- Principles of Constraint Programming
- Reasoning with probabilistic and deterministic graphical models. Exact algorithms
- Semiring-based constraint satisfaction and optimization
- Solving knapsack problems on GPU
- The state of the art of nurse rostering
Cited in
(4)- Fast parallel \(\alpha \)-stable distribution function evaluation and parameter estimation using OpenCL in GPGPUs
- Differential privacy of hierarchical census data: an optimization approach
- Efficiently approximating high-dimensional Pareto frontiers for tree-structured networks using expansion and compression
- scientific article; zbMATH DE number 7378698 (Why is no real title available?)
This page was built for publication: Accelerating exact and approximate inference for (distributed) discrete optimization with GPUs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1706596)
