NDLI: Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search

Content Provider	Springer Nature Link
Author	Sabharwal, Ashish Dilkina, Bistra Gomes, Carla P.
Copyright Year	2014
Abstract	There has been considerable interest in the identification of structural properties of combinatorial problems that lead to efficient algorithms for solving them. Some forms of structure, such as properties of the underlying constraint graph, are “easily” identifiable. Others, such as backdoor sets, are of interest because they capture key aspects of state-of-the-art constraint solvers as well as of many real-world problem instances. While backdoors were originally introduced to capture propagation based simplification mechanisms of solvers, they have recently been studied also in the context of tractable syntactic classes such as 2CNF and Horn. These syntactic classes, however, do not capture key aspects of solvers such as empty clause (i.e., violated constraint) detection. We show that incorporating inconsequential sounding features such as empty clause detection has a dramatic impact on both the complexity of finding a backdoor of size k (which becomes harder in the worst case) and on the size of the resulting backdoor (which can become arbitrarily smaller). Empirically, we show that commonly employed polynomial-time “dynamic” constraint propagation mechanisms, such as unit propagation, pure literal elimination, and probing, often lead to much smaller backdoor sets in real-world domains than “statically” defined classes such as Horn and RHorn, thereby capturing structure much more succinctly. We also reveal the inherent limits of the simpler concept of deletion backdoors, specifically by looking at renamable Horn sub-formulas. Finally, we extend the notion of backdoors to incorporate learning during search—a key aspect of nearly all state-of-the-art systematic SAT solvers—and show, both theoretically and empirically, that this drastically reduces the size of the resulting backdoor set. Our results suggest that structural notions explored for designing efficient algorithms for combinatorial problems should capture both statically and dynamically identifiable properties of the combinatorial problem being solved.
Ending Page	431
Page Count	33
Starting Page	399
File Format	PDF
ISSN	10122443
e-ISSN	15737470
Journal	Annals of Mathematics and Artificial Intelligence
Issue Number	4
Volume Number	70
Language	English
Publisher	Springer International Publishing
Publisher Date	2014-03-15
Publisher Place	Cham
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Horn RHorn Backdoor sets Clause learning Problem solving (heuristics, search strategies, etc.) Search Computer Science Artificial Intelligence (incl. Robotics) Mathematics Statistical Physics, Dynamical Systems and Complexity Boolean satisfiability
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Artificial Intelligence

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Computation of renameable horn backdoors for quantified boolean formulas

On the relation among answer set solvers

Boolean lexicographic optimization: algorithms & applications

Limitations of restricted branching in clause learning

Heuristics as Markov chains

Set-structured and cost-sharing heuristics for classical planning

Conformant planning as a case study of incremental QBF solving

Learning cluster-based structure to solve constraint satisfaction problems

Learning dynamic algorithm portfolios

Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search

Similar Documents

Computation of renameable horn backdoors for quantified boolean formulas

On the relation among answer set solvers

Boolean lexicographic optimization: algorithms & applications

Limitations of restricted branching in clause learning

Heuristics as Markov chains

Set-structured and cost-sharing heuristics for classical planning

Conformant planning as a case study of incremental QBF solving

Learning cluster-based structure to solve constraint satisfaction problems

Learning dynamic algorithm portfolios

Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search