On Continuous Local BDD-Based Search for Hybrid SAT Solving

02/02/2021

On Continuous Local BDD-Based Search for Hybrid SAT Solving

Anastasios Kyrillidis, Moshe Vardi, Zhiwei Zhang

Keywords:

Abstract Paper Similar Papers

Abstract: We explore the potential of continuous local search (CLS) in SAT solving by proposing a novel approach for finding a solution of a hybrid system of Boolean constraints. The algorithm is based on CLS combined with belief propagation on binary decision diagrams (BDDs). Our framework accepts all Boolean constraints that admit compact BDDs, including symmetric Boolean constraints and small-coefficient pseudo-Boolean constraints as interesting families. We propose a novel algorithm for efficiently computing the gradient needed by CLS. We study the capabilities and limitations of our versatile CLS solver, GradSAT, by applying it on many benchmark instances. The experimental results indicate that GradSAT can be a useful addition to the portfolio of existing SAT and MaxSAT solvers for solving Boolean satisfiability and optimization problems.

The video of this talk cannot be embedded. You can watch it here:

https://slideslive.com/38948230

(Link will open in new window)

0

0

0

0

Share

This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment

no comments yet

Similar Papers

06/12/2020

Finding the Homology of Decision Boundaries with Active Learning

Weizhi Li, Gautam Dasarathy, Karthi Natesan Ramamurthy, Visar Berisha

Keywords Paper

Algorithms -> AutoML; Applications -> Fairness, Accountability, and Transparency; Optimization -> Stochastic Optimization, Algorithms -> Classification

0

0

0

0

3:27

26/04/2020

Transferring Optimality Across Data Distributions via Homotopy Methods

Matilde Gargiani, Andrea Zanelli, Quoc Tran Dinh and
Moritz Diehl, Frank Hutter

Keywords Paper

deep learning, numerical optimization, transfer learning

0

0

0

0

5:25

13/04/2021

Alternating direction method of multipliers for quantization

Tianjian Huang, Prajwal Singhania, Maziar Sanjabi and
Pabitra Mitra, Meisam Razaviyayn

Keywords Paper

1

0

0

0

2:43

26/04/2020

Meta-Learning Acquisition Functions for Transfer Learning in Bayesian Optimization

Michael Volpp, Lukas P. Fröhlich, Kirsten Fischer and
Andreas Doerr, Stefan Falkner, Frank Hutter, Christian Daniel

Keywords Paper

Transfer Learning, Meta Learning, Bayesian Optimization, Reinforcement Learning

0

0

0

0

5:05

06/12/2021

Deep Conditional Gaussian Mixture Model for Constrained Clustering

Laura Manduchi, Kieran Chin-Cheong, Holger Michel and
Sven Wellmann, Julia Vogt

Keywords Paper

machine learning, robustness, generative model, clustering, representation learning

0

0

0

0

14:14

02/02/2021

Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies

Giulia Zarpellon, Jason Jo, Andrea Lodi, Yoshua Bengio

Keywords Paper

0

0

0

0

17:58

02/02/2021

Partial-Label and Structure-constrained Deep Coupled Factorization Network

Yan Zhang, Zhao Zhang, Yang Wang and
Zheng Zhang, Li Zhang, Shuicheng Yan, Meng Wang

Keywords Paper

0

0

0

0

13:39

12/07/2020

Conditional gradient methods for stochastically constrained convex minimization

Maria-Luiza Vladarean, Ahmet Alacaoglu, Ya-Ping Hsieh, Volkan Cevher

Keywords Paper

Optimization - Convex

0

0

0

0

14:50

06/12/2020

Deep Variational Instance Segmentation

Jialin Yuan, Chao Chen, Fuxin Li

Keywords Paper

Algorithms -> Multitask and Transfer Learning, Applications -> Computer Vision

0

0

0

0

3:23

06/12/2020

Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization

Sam Daulton, Max Balandat, Eytan Bakshy

Keywords Paper

0

0

0

0

3:20

02/02/2021

Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints

Brian Brubach, Darshan Chakrabarti, John P. Dickerson and
Aravind Srinivasan, Leonidas Tsepenekas

Keywords Paper

0

0

0

0

17:56

03/05/2021

Differentiable Segmentation of Sequences

Erik Scharwächter, Jonathan Lennartz, Emmanuel Müller

Keywords Paper

warping functions, concept drift, change point detection, segmented models, segmentation, gradient descent

0

1

0

0

5:10

15/06/2020

Learning nonlinear loop invariants with gated continuous logic networks

Jianan Yao, Gabriel Ryan, Justin Wong and
Suman Jana, Ronghui Gu

Keywords Paper

Loop Invariant Inference, Continuous Logic Networks, Program Verification

0

0

0

0

14:18

06/12/2020

Interior Point Solving for LP-based prediction+optimisation

Jayanta Mandi, Tias Guns

Keywords Paper

0

0

0

1

3:28

02/02/2021

Progression Heuristics for Planning with Probabilistic LTL Constraints

Ian Mallett, Sylvie Thiebaux, Felipe Trevizan

Keywords Paper

0

0

0

0

18:23

06/12/2021

Model Selection for Bayesian Autoencoders

Ba-Hien Tran, Simone Rossi, Dimitrios Milios and
Pietro Michiardi, Edwin Bonilla, Maurizio Filippone

Keywords Paper

optimization, self-supervised learning, generative model, representation learning

0

0

0

0

10:49

06/12/2021

An online passive-aggressive algorithm for difference-of-squares classification

Lawrence Saul

Keywords Paper

machine learning, online learning

0

0

0

0

14:00

15/11/2020

Satune: Synthesizing Efficient SAT Encoders

Hamed Gorjiara, Guoqing Harry Xu, Brian Demsky

Keywords Paper

Auto-tuning, SAT encoding, Constraint Solvers

0

0

0

0

15:23

06/12/2021

Local Hyper-Flow Diffusion

Kimon Fountoulakis, Pan Li, Shenghao Yang

Keywords Paper

optimization, graph learning, clustering

0

0

0

0

14:24

14/09/2020

Learning Representations from Dendrograms

Morteza Haghir Chehreghani, Mostafa Haghir Chehreghani

Keywords Paper

0

0

0

0

14:44

18/07/2021

Batch Value-function Approximation with Only Realizability

Tengyang Xie, Nan Jiang

Keywords Paper

Algorithms, Multitask and Transfer Learning, Algorithms, Unsupervised Learning; Applications, Image Segmentation, Theory, RL, Decisions and Control Theory

0

0

0

0

5:05

26/04/2020

Locally Constant Networks

Guang-He Lee, Tommi S. Jaakkola

Keywords Paper

0

0

0

0

4:44

06/12/2021

Estimating the Unique Information of Continuous Variables

Ari Pakman, Amin Nejatbakhsh, Dar Gilboa and
Abdullah Makkeh, Luca Mazzucato, Michael Wibral, Elad Schneidman

Keywords Paper

deep learning, optimization, generative model

0

0

0

0

12:39

03/05/2021

Implicit Convex Regularizers of CNN Architectures: Convex Optimization of Two- and Three-Layer Networks in Polynomial Time

Tolga Ergen, Mert Pilanci

Keywords Paper

deep learning, polynomial time, convex duality, $\ell_1$ norm, group sparsity, Convex optimization, non-convex optimization

0

0

0

0

11:14

18/07/2021

Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs

Tolga Ergen, Mert Pilanci

Keywords Paper

Optimization, Convex Optimization

0

0

0

0

5:40

02/02/2021

Submodular Span, with Applications to Conditional Data Summarization

Lilly Kumari, Jeff Bilmes

Keywords Paper

0

0

0

0

16:22

26/08/2020

Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning

Zhenzhang Ye, Thomas Möllenhoff, Tao Wu, Daniel Cremers

Keywords Paper

0

0

0

0

13:50

06/12/2021

Row-clustering of a Point Process-valued Matrix

Lihao Yin, Ganggang Xu, Huiyan Sang, Yongtao Guan

Keywords Paper

machine learning, clustering

0

0

0

0

14:30

02/02/2021

An Information-Theoretic Framework for Unifying Active Learning Problems

Quoc Phong Nguyen, Bryan Kian Hsiang Low, Patrick Jaillet

Keywords Paper

0

0

0

0

14:53

12/07/2020

Stochastic Flows and Geometric Optimization on the Orthogonal Group

Krzysztof Choromanski, David Cheikhi, Jared Davis and
Valerii Likhosherstov, Achille Nazaret, Achraf Bahamou, Xingyou Song, Mrugank Akarte, Jack Parker-Holder, Jacob Bergquist, YUAN GAO, Aldo Pacchiano, Tamas Sarlos, Adrian Weller, Vikas Sindhwani

Keywords Paper

Optimization - Non-convex

0

0

0

0

13:44

06/12/2021

NTopo: Mesh-free Topology Optimization using Implicit Neural Representations

Jonas Zehnder, Yue Li, Stelian Coros, Bernhard Thomaszewski

Keywords Paper

deep learning, optimization, machine learning, self-supervised learning, representation learning

0

0

0

0

9:24

06/12/2020

Gaussian Gated Linear Networks

David Budden, Adam Marblestone, Eren Sezener and
Tor Lattimore, Greg Wayne, Joel Veness

Keywords Paper

0

0

0

0

3:28

02/02/2021

Pareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints

Anh Viet Do, Frank Neumann

Keywords Paper

0

0

0

0

16:47

03/05/2021

Mixed-Features Vectors and Subspace Splitting

Alejandro Pimentel-Alarcón, Daniel L Pimentel-Alarcón

Keywords Paper

0

0

0

0

13:27

12/07/2020

A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton

Risheng Liu, Pan Mu, Xiaoming Yuan and
Shangzhi Zeng, Jin Zhang

Keywords Paper

Optimization - Non-convex

0

0

0

0

13:51

06/12/2020

Dual Instrumental Variable Regression

Krikamol Muandet, Arash Mehrjou, Si Kai Lee, Anant Raj

Keywords Paper

0

0

0

0

3:04

12/07/2020

dS^2LBI: Exploring Structural Sparsity on Deep Network via Differential Inclusion Paths

Yanwei Fu, Chen Liu, Donghao Li and
Xinwei Sun, Jinshan ZENG, Yuan Yao

Keywords Paper

Deep Learning - Algorithms

0

0

0

1

12:45

02/02/2021

Robust Model Compression Using Deep Hypotheses

Omri Armstrong, Ran Gilad-Bachrach

Keywords Paper

0

0

0

0

17:26

18/07/2021

Asynchronous Decentralized Optimization With Implicit Stochastic Variance Reduction

Kenta Niwa, Guoqiang Zhang, W. Bastiaan Kleijn and
Noboru Harada, Hiroshi Sawada, Akinori Fujino

Keywords Paper

Optimization, Distributed and Parallel Optimization

0

0

0

0

5:41

12/07/2020

Expert Learning through Generalized Inverse Multiobjective Optimization: Models, Insights and Algorithms

Chaosheng Dong, Bo Zeng

Keywords Paper

Learning Theory

0

0

0

0

12:11