Restricted Boltzmann Machines for Maximum Satisfiability - IPAM at UCLA

Explore the application of machine learning techniques to discrete combinatorial optimization in this 56-minute lecture from the Artificial Intelligence and Discrete Optimization Workshop at IPAM. Delve into Vinod Nair's presentation on using Restricted Boltzmann Machines for Maximum Satisfiability (MaxSAT) problems. Discover how this approach leverages high-throughput matrix multiplication capabilities of modern neural network accelerators to tackle challenging combinatorial optimization tasks. Learn about the construction of a Restricted Boltzmann Machine with an equilibrium distribution that assigns probabilities to Boolean assignments based on the number of clauses they satisfy. Examine the use of chain-parallel, device-parallel block Gibbs sampling for searching the space of satisfying assignments, combined with periodic improvements using classical heuristics. Analyze timed results on MaxSAT Evaluation problem instances from 2018 to 2021, along with an ablation study. Gain insights into how this stochastic search approach exploits horizontally-scaled accelerator parallelism, opening new avenues for studying combinatorial optimization problems.