Show simple item record

dc.contributor.authorDilkina, Bistra
dc.contributor.authorGomes, Carla P.
dc.contributor.authorSabharwal, Ashish
dc.description.abstractThe 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.en_US
dc.subjectconstraint satisfactionen_US
dc.subjectproblem structureen_US
dc.subjectbackdoor variablesen_US
dc.subjectclause learningen_US
dc.titleBackdoors in the Context of Learningen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record