Skip to main content


eCommons@Cornell

eCommons@Cornell >
Faculty of Computing and Information Science >
Computing and Information Science >
Computing and Information Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/12231
Title: Backdoors in the Context of Learning
Authors: Dilkina, Bistra
Gomes, Carla P.
Sabharwal, Ashish
Keywords: constraint satisfaction
problem structure
backdoor variables
clause learning
Issue Date: 9-Apr-2009
Abstract: The concept of backdoor variables has been introduced as a structural property of combinatorial problems that provides insight into the surprising ability of modern satisfiability (SAT) solvers to tackle extremely large instances. Given a backdoor variable set B, a systematic search procedure is guaranteed to succeed in efficiently deciding the problem instance independent of the order in which it explores various truth valuations of the variables in B. This definition is oblivious to the fact that "learning during search" is a key feature of modern solution procedures for various classes of combinatorial problems such as SAT and mixed integer programming (MIP). These solvers carry over often highly useful information from previously explored search branches to newly considered branches. In this work, we extend the notion of backdoors to the context of learning during search. In particular, we prove that the smallest backdoors for SAT that take into account clause learning and order-sensitivity of branching can be exponentially smaller than traditional backdoors oblivious to these solver features. We also provide an experimental comparison between backdoor sizes with and without learning.
URI: http://hdl.handle.net/1813/12231
Appears in Collections:Computing and Information Science Technical Reports

Files in This Item:

File Description SizeFormat
backdoorsLrng.pdf175.98 kBAdobe PDFView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us