Accelerating exact and approximate inference for (distributed) discrete optimization with GPUs
From MaRDI portal
Publication:1706596
DOI10.1007/S10601-017-9274-1zbMATH Open1395.90187arXiv1608.05288OpenAlexW3105349602MaRDI QIDQ1706596FDOQ1706596
Authors: Ferdinando Fioretto, Enrico Pontelli, William Yeoh, Rina Dechter 
Publication date: 22 March 2018
Published in: Constraints (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1608.05288
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
- Emergence of Scaling in Random Networks
- Title not available (Why is that?)
- Handbook of constraint programming.
- Autonomous agents coordination: action languages meet CLP(\(\mathcal {FD}\)) and Linda
- Principles and Practice of Constraint Programming – CP 2004
- Network-based heuristics for constraint-satisfaction problems
- The state of the art of nurse rostering
- Principles of Constraint Programming
- Networks of constraints: Fundamental properties and applications to picture processing
- Algorithm for optimal winner determination in combinatorial auctions
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- A dynamic programming approach for consistency and propagation for knapsack constraints
- Computational protein design as an optimization problem
- Mini-buckets: a general scheme for bounded inference
- Solving knapsack problems on GPU
- Semiring-based constraint satisfaction and optimization
- Bucket elimination: A unifying framework for reasoning
- Adopt: asynchronous distributed constraint optimization with quality guarantees
- Approximations in Distributed Optimization
- BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm
- Global Grammar Constraints
- Memory intensive AND/OR search for combinatorial optimization in graphical models
- KI 2004: Advances in Artificial Intelligence
- Reasoning with probabilistic and deterministic graphical models. Exact algorithms
- AND/OR branch-and-bound on a computational grid
- Constrained community-based gene regulatory network inference
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
- Title not available (Why is that?)
Uses Software
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)
