Learning to Select Branching Rules in the DPLL Procedure for Satisfiability

By Michail G. Lagoudakis, Michael L. Littman. 2001

105 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Frank Hutter
2. Holger H. Hoos
3. Yoshua Bengio
4. Kevin Leyton-Brown
5. Lihong Li
6. Lars Kotthoff
7. Lin Xu
8. Quoc V. Le

In Computational Theory and Mathematics

1. Frank Hutter
2. Holger H. Hoos
3. Kevin Leyton-Brown
4. Lars Kotthoff
5. Yuri Malitsky
6. Lin Xu
7. Aaron Klein
8. Marius Thomas Lindauer

In Computer Networks and Communications

1. Frank Hutter
2. Holger H. Hoos
3. Kevin Leyton-Brown
4. Yuri Malitsky
5. Lin Xu
6. Lars Kotthoff
7. Bistra N. Dilkina
8. Katharina Eggensperger

Citations in the corpus

• Learning Combinatorial Optimization Algorithms over Graphs (2017, methodology): “[26] Lagoudakis, Michail G and Littman, Michael L.”
• Instance-Specific Algorithm Configuration (2014, methodology): “A similar approach was later presented in [64], but instead of choosing a single heuristic, this approach tries to learn the best branching heuristic to use at each node of a complete tree search.”
• Boosting as a Metaphor for Algorithm Design (2003, unknown): “Markov Decision ProcessesPerhaps most related to our paper is work by Lagoudakis and Littman ([7, 8]).”
• Algorithm Selection for Combinatorial Search Problems: A Survey (2012, background): “A very common application domain are combinatorial search problems such as SAT (Xu et al., 2008; Lagoudakis & Littman, 2001; Silverthorn & Miikkulainen, 2010), constraints (Minton, 1996; Epstein et al., 2002; O’Mahony et al., 2008), Mixed Integer Programming (Xu, Hutter, Hoos, & Leyton-Brown,…”
• Learning to Solve QBF (2007, methodology): “Among existing work on using learning to solve SAT the method that comes closest to our approach is probably (Lagoudakis & Littman 2001).”
• A unifying framework for computational reinforcement learning theory (2009, background): “…Barto 1996], discrete optimization problems such as job-shop scheduling and Boolean satisfiability [Zhang and Dietterich 1995; Boyan and Moore 2000; Lagoudakis and Littman 2001], channel allocation [Singh and Bertsekas 1997], algorithm selection [Lagoudakis and Littman 2000], option pricing…”
• SATzilla: Portfolio-based Algorithm Selection for SAT (2008, methodology): “Lagoudakis and Littman (2001) employed reinforcement learning to solve an algorithm selection problem at each decision point of a DPLL solver for SAT in order to select a branching rule.”