Backdoors in the Context of Learning

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.