NDLI: Learning from conflicts in propositional satisfiability

Please wait, while we are loading the content...

Learning from conflicts in propositional satisfiability

Content Provider	Springer Nature Link
Author	Hamadi, Youssef Jabbour, Saïd Saïs, Lakhdar
Copyright Year	2011
Abstract	Learning is a general concept, playing an important role in many Artificial intelligence domains. In this paper, we address the learning paradigm used to explain failures or conflicts encountered during search. This explanation, derived by conflict analysis, and generally expressed as a new constraint, is usually used to dynamically avoid future occurrences of similar situations. Before focusing on clause learning in Boolean satisfiability (SAT), we first overview some important works on this powerful reasoning tool in other domains such as constraint satisfaction and truth maintenance systems. Then, we present a comprehensive survey of the most important works having led to what is called today—conflict driven clause learning (CDCL)—which is one of the key components of modern SAT solvers. In theory, current SAT solvers with clause learning are as powerful as general resolution proof systems. In practice, real-world SAT instances with millions of variables and clauses are now in the scope of this solving paradigm.
Starting Page	15
Ending Page	32
Page Count	18
File Format	PDF
ISSN	16194500
Journal	4OR
Volume Number	10
Issue Number	1
e-ISSN	16142411
Language	English
Publisher	Springer-Verlag
Publisher Date	2011-12-28
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Satisfiability Conflict learning Constraint satisfaction Industrial and Production Engineering Optimization Operations Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Management Science and Operations Research Management Information Systems Computational Theory and Mathematics

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

Integrating operations research in constraint programming

Optimization of modular machining lines

Constraint programming-based column generation

What we can learn from conflicts in propositional satisfiability

Nonsmooth optimization: theory and algorithms

Matheuristics for combinatorial optimization problems: applications to services and production systems

Simulation-based optimization in port logistics

On scheduling with the non-idling constraint

Letter to the Editors

Learning from conflicts in propositional satisfiability

Similar Documents

Integrating operations research in constraint programming

Optimization of modular machining lines

Constraint programming-based column generation

What we can learn from conflicts in propositional satisfiability

Nonsmooth optimization: theory and algorithms

Matheuristics for combinatorial optimization problems: applications to services and production systems

Simulation-based optimization in port logistics

On scheduling with the non-idling constraint

Letter to the Editors

Learning from conflicts in propositional satisfiability