#### DMCA

## Look-Back Techniques and Heuristics in DLV: Implementation and Evaluation ⋆

### Citations

1841 | The stable model semantics for logic programming
- Gelfond, Lifschitz
- 1988
(Show Context)
Citation Context ...at the new look-back techniques significantly improve the performance of DLV, being performance-wise competitive even with respect to “native” QBF solvers. 1 Introduction Answer Set Programming (ASP) =-=[1, 2]-=- is a purely-declarative programming paradigm based on nonmonotonic reasoning and logic programming. The idea of answer set programming is to represent a given computational problem by a logic program... |

1347 | Chaff: Engineering an efficient SAT solver
- Moskewicz, Madigan, et al.
- 2001
(Show Context)
Citation Context ...iche di ottimizzazione.” DLV did not incorporate any “look-back” techniques, like “backjumping” procedures and “look-back” heuristics. By “backjumping” [4] we refer to an optimized recovery upon inconsistency during the search where, instead of restoring the state of the search up to the previous choice and then “flipping” its value, we try to “jump over” choices that are not relevant for the inconsistency we met. This is done by means of a reason calculus, which records information about the literals (“reasons”) whose truth has caused the truth of other derived literals. Look-back heuristics [5] further strengthen the potential of backjumping by using the information made explicit by the reasons. The idea of such family of heuristics is to preferably choose atoms which frequently caused inconsistencies, thus focusing on “critical” atoms. This significantly differ from classical ASP heuristics that use information arising from the simplification part (“look-head”) of the algorithm. Such look-back optimization techniques and heuristics have been shown, on other research areas, to be very effective on “big” benchmarks coming from applications, like planning and formal verification. In t... |

1034 | Classical negation in logic programs and disjunctive databases
- Gelfond, Lifschitz
- 1991
(Show Context)
Citation Context ...cial on large benchmarks stemming from applications. In this paper, we focus on the experimental evaluation of the look-back algorithms and heuristics that have been implemented in DLV. We have conducted a wide experimental analysis considering both randomly-generated and structured instances of the 2QBF problem (the canonical problem for the complexity classes ΣP2 and Π P 2 ). The results show that the new look-back techniques significantly improve the performance of DLV, being performance-wise competitive even with respect to “native” QBF solvers. 1 Introduction Answer Set Programming (ASP) [1, 2] is a purely-declarative programming paradigm based on nonmonotonic reasoning and logic programming. The idea of answer set programming is to represent a given computational problem by a logic program whose answer sets correspond to solutions, and then use an answer set solver to find such solutions [3]. The language of ASP is very expressive, allowing for both disjunction in the head of the rules and nonmonotonic negation in the body, and able to represent every property in the second level of the polynomial hierarchy. Therefore, ASP is strictly more powerful than propositional logic unless P... |

454 | The DLV System for Knowledge Representation and Reasoning
- Leone, Pfeifer, et al.
- 2006
(Show Context)
Citation Context ...bove-mentioned look-back techniques and heuristics in DLV; in this section, we report on their experimental evaluation. Compared Methods. For our experiments, we have compared several versions of DLV =-=[15]-=-, which differ on the employed heuristics and the use of backjumping. For having a broader picture, we have also compared our implementations to the competing systems GnT and CModels3, and with the QB... |

379 | Hybrid algorithms for the constraint satisfaction problem
- Prosser
- 1993
(Show Context)
Citation Context ...appresentazione di conoscenza: estensioni e tecniche di ottimizzazione.”DLV did not incorporate any “look-back” techniques, like “backjumping” procedures and “look-back” heuristics. By “backjumping” =-=[4]-=- we refer to an optimized recovery upon inconsistency during the search where, instead of restoring the state of the search up to the previous choice and then “flipping” its value, we try to “jump ove... |

200 | Conflict-driven answer set solving
- Gebser, Kaufmann, et al.
- 2007
(Show Context)
Citation Context ...in DLV, and ultimately, about their efficiency in the disjunctive ASP setting. Such methods have been already used in other ASP systems which (i) do not allow for disjunction in the head of the rules =-=[6, 7]-=-, or (ii) apply such methods only indirectly after a transformation to a propositional satisfiability problem [8]. The resulting system, called DLV LB , is therefore the first implementation of disjun... |

168 | Answer set planning
- Lifschitz
- 1999
(Show Context)
Citation Context ...The idea of answer set programming is to represent a given computational problem by a logic program whose answer sets correspond to solutions, and then use an answer set solver to find such solutions =-=[3]-=-. The language of ASP is very expressive, allowing for both disjunction in the head of the rules and nonmonotonic negation in the body, and able to represent every property in the second level of the ... |

139 | On the Computational Cost of Disjunctive Logic Programming: Propositional Case
- Eiter, Gottlob
- 1995
(Show Context)
Citation Context ...rchy. This choice is motivated by the fact that many real-world, structured (i.e., fixed) instances in this complexity class are available for 2QBF on QBFLIB [18], and moreover, studies on the location of hard instances for randomly generated 2QBFs have been reported in [19–21]. The problem 2QBF is to decide whether a quantified Boolean formula (QBF) Φ = ∀X∃Y φ, where X and Y are disjoint sets of propositional variables and φ = D1 ∧ . . . ∧ Dk is a CNF formula over X ∪ Y , is valid. The transformation from 2QBF to disjunctive logic programming is a slightly altered form of a reduction used in [22]. The propositional disjunctive logic program Pφ produced by the transformation requires 2 ∗ (|X |+ |Y |) + 1 propositional predicates (with one dedicated predicate w), and consists of the following rules. Rules of the form v∨v. for each variable v ∈ X ∪Y . Rules of the form y ← w. y ← w. for each y ∈ Y . Rules of the form w ← v1, . . . , vm, vm+1, . . . , vn. for each disjunction v1∨...∨vm∨¬vm+1∨...∨¬vn in φ. The rule← not w. The 2QBF formula Φ is valid iff PΦ has no answer set [22]. We have selected both random and structured QBF instances. The random 2QBF instances have been generated f... |

78 | The TSP phase transition - Gent, Walsh - 1996 |

57 | A Distributed Algorithm to Evaluate Quantified Boolean Formulae
- Feldmann, Monien, et al.
(Show Context)
Citation Context ...ng answer set candidates using the completion of the input program and loop formulas obtained during the computation, the second for verifying if the candidate model is indeed an answer set. • ssolve =-=[17]-=-: is a search based native QBF solver that won the QBF Evaluation in 2004 on random (or probabilistic) benchmarks (performing very well also on non-random, or fixed, benchmarks), and performed globall... |

37 | Bounded model construction for monadic second-order logics
- Ayari, Basin
- 2000
(Show Context)
Citation Context ...s used in the QBF Evaluation 2004 and 2005. – Ayari-MutexP - These QBFs encode instances to problems related to the formal equivalence checking of partial implementations of circuits, as presented in =-=[24]-=-. – Letz-Tree - These instances consist of simple variable-independent subprograms generated according to the pattern: ∀x1x3...xn−1∃x2x4...xn(c1 ∧ . . . ∧ cn−2) where ci = xi ∨ xi+2 ∨ xi+3, ci+1 = ¬xi... |

35 | Disjunctive answer set programming via satisfiability, in:
- Lierler
- 2005
(Show Context)
Citation Context ...n other ASP systems which (i) do not allow for disjunction in the head of the rules [6, 7], or (ii) apply such methods only indirectly after a transformation to a propositional satisfiability problem =-=[8]-=-. The resulting system, called DLV LB , is therefore the first implementation of disjunctive ASP featuring backjumping and look-back heuristics. Importantly, our system provides several options regard... |

34 | Experimenting with Heuristics for Answer Set Programming. In: IJCAI
- Faber, Leone, et al.
- 2001
(Show Context)
Citation Context ...back), which are computed as side-effects of the backjumping technique. We assume that a ground ASP program P and an interpretation I have been fixed. We first recall the “standard” DLV heuristic hUT =-=[12]-=-, which has recently been refined to yield the heuristic hDS [13], which is more “specialized” for hard disjunctive programs (like 2QBF). These are look-ahead heuristics, that is, the heuristic value ... |

32 | A.: SAT-based planning in complex domains: Concurrency, constraints and nondeterminism.
- Castellini, Giunchiglia, et al.
- 2003
(Show Context)
Citation Context ...l, 160 and 140 instances per set, respectively. About the structured instances, we have analyzed: – Narizzano-Robot - These are real-word instances encoding the robot navigation problems presented in =-=[23]-=-, as used in the QBF Evaluation 2004 and 2005. – Ayari-MutexP - These QBFs encode instances to problems related to the formal equivalence checking of partial implementations of circuits, as presented ... |

29 | Answer set programming with clause learning.
- Ward, JSchlipf
- 2004
(Show Context)
Citation Context ...in DLV, and ultimately, about their efficiency in the disjunctive ASP setting. Such methods have been already used in other ASP systems which (i) do not allow for disjunction in the head of the rules =-=[6, 7]-=-, or (ii) apply such methods only indirectly after a transformation to a propositional satisfiability problem [8]. The resulting system, called DLV LB , is therefore the first implementation of disjun... |

29 | Using Database Optimization Techniques for Nonmonotonic Reasoning. DDLP’99
- Faber, Leone, et al.
(Show Context)
Citation Context ...ith partial interpretations in the next sections. 4 Note that ground(P) is usually not the full Ground(P); rather, it is a subset (often much smaller) of it having precisely the same answer sets as P =-=[9]-=- 5 Note that for reasons of presentation, the description here is quite simplified w.r.t. the “real” implementation. A more detailed description can be found in [11].bool ModelGenerator ( Interpretat... |

26 |
Gnt—a solver for disjunctive logic programs, in:
- Janhunen, Niemelä
- 2004
(Show Context)
Citation Context ...ddisjunctive programs. • dlv.ds.bj: DLV with hDS and backjumping. • dlv.mf: DLV with hMF LB .7 • dlv.mf.af: DLV with h MF,AF LB . • dlv.lf: DLV with hLF LB . • dlv.lf.af: DLV with h LF,AF LB . • gnt =-=[16]-=-: The solver GnT, based on the Smodels system, can deal with disjunctive ASP. One instance of Smodels generates candidate models, while another instance tests if a candidate model is stable. • cm3 [8]... |

19 | Experimental Analysis of the Computational Cost of Evaluating Quantified Boolean Formulae. In: - Cadoli, Giovanardi, et al. - 1997 |

18 | A Backjumping Technique for Disjunctive Logic Programming.
- Ricca, Faber, et al.
- 2006
(Show Context)
Citation Context ..., we illustrate the original model generation algorithm of DLV (which is based on chronological backtracking); then, we briefly describe a backjumping technique that has been implemented in the system=-=[10]-=-; and, we detail how the model generation algorithm has been changed to introduce it. Finally, we report a description of all the heuristics, including the new ones based look-back techniques, that ha... |

17 |
V.: Classical Negation
- Gelfond, Lifschitz
- 1991
(Show Context)
Citation Context ...at the new look-back techniques significantly improve the performance of DLV, being performance-wise competitive even with respect to “native” QBF solvers. 1 Introduction Answer Set Programming (ASP) =-=[1, 2]-=- is a purely-declarative programming paradigm based on nonmonotonic reasoning and logic programming. The idea of answer set programming is to represent a given computational problem by a logic program... |

16 |
Enhancing Efficiency and Expressiveness in Answer Set Programming Systems.
- Faber
- 2002
(Show Context)
Citation Context ...precisely the same answer sets as P [9] 5 Note that for reasons of presentation, the description here is quite simplified w.r.t. the “real” implementation. A more detailed description can be found in =-=[11]-=-.bool ModelGenerator ( Interpretation& I ) { I = DetCons ( I ); if ( I == L ) then return false; if ( “no atom is undefined in I” ) then return IsAnswerSet(I); Select an undefined atom A using a heur... |

16 | A model for generating random quantified boolean formulas. In:
- Chen, Interian
- 2005
(Show Context)
Citation Context ... both random and structured QBF instances. The random 2QBF instances have been generated following recent phase transition results for QBFs [19– 21]. In particular, the generation method described in =-=[21]-=- has been employed and the generation parameters have been chosen according to the experimental results reported in the same paper. First, we have generated 10 different sets of instances, each of whi... |

10 |
On the Computational Cost of Disjunctive
- Eiter, Gottlob
- 1995
(Show Context)
Citation Context ...propositional variables and φ = D1 ∧ . . . ∧ Dk is a CNF formula over X ∪ Y , is valid. The transformation from 2QBF to disjunctive logic programming is a slightly altered form of a reduction used in =-=[22]-=-. The propositional disjunctive logic program Pφ produced by the transformation requires 2 ∗ (|X| + |Y |) + 1 propositional predicates (with one dedicated predicate w), and consists of the following r... |

4 | Solving Hard Problems for the Second Level of the Polynomial Hierarchy: Heuristics and Benchmarks.
- Faber, Leone, et al.
- 2005
(Show Context)
Citation Context ... heuristic values of an atom Q depends on both the effect of taking Q and not Q, the decision between Q and not Q is based on the UT atoms criteria. Enhanced Heuristic of DLV (hDS). The heuristic hDS =-=[14]-=- is based on hUT , and is different from hUT only for pairs of literals which are not ordered by hUT . The idea of the additional criterion is that interpretations having a “higher degree of supported... |

4 |
The Stable Model Semantics for Logic Programming. In: Logic Programming:
- Gelfond, Lifschitz
- 1988
(Show Context)
Citation Context ...cial on large benchmarks stemming from applications. In this paper, we focus on the experimental evaluation of the look-back algorithms and heuristics that have been implemented in DLV. We have conducted a wide experimental analysis considering both randomly-generated and structured instances of the 2QBF problem (the canonical problem for the complexity classes ΣP2 and Π P 2 ). The results show that the new look-back techniques significantly improve the performance of DLV, being performance-wise competitive even with respect to “native” QBF solvers. 1 Introduction Answer Set Programming (ASP) [1, 2] is a purely-declarative programming paradigm based on nonmonotonic reasoning and logic programming. The idea of answer set programming is to represent a given computational problem by a logic program whose answer sets correspond to solutions, and then use an answer set solver to find such solutions [3]. The language of ASP is very expressive, allowing for both disjunction in the head of the rules and nonmonotonic negation in the body, and able to represent every property in the second level of the polynomial hierarchy. Therefore, ASP is strictly more powerful than propositional logic unless P... |

3 |
A.: QBF Solvers Evaluation page (2002) http://www. qbflib.org/qbfeval/index.html
- Narizzano, Tacchella
(Show Context)
Citation Context ...r the second level of the polynomial hierarchy. This choice is motivated by the fact that many real-world, structured (i.e., fixed) instances in this complexity class are available for 2QBF on QBFLIB =-=[18]-=-, and moreover, studies on the location of hard instances for randomly generated 2QBFs have been reported in [19–21]. The problem 2QBF is to decide whether a quantified Boolean formula (QBF) Φ = ∀X∃Y ... |

3 | T.: The QSAT Phase Transition. In: AAAI - Gent, Walsh - 1999 |

2 |
QBF Solvers Evaluation page
- Narizzano, Tacchella
- 2002
(Show Context)
Citation Context .... Benchmark Programs and Data. The proposed heuristic aims at improving the performance of DLV on disjunctive ASP programs. Therefore we focus on hard programs in this class, which is known to be able to express each problem of the complexity class ΣP2 /Π P 2 . All of the instances that we have considered in our benchmark analysis have been derived from instances for 2QBF, the canonical problem for the second level of the polynomial hierarchy. This choice is motivated by the fact that many real-world, structured (i.e., fixed) instances in this complexity class are available for 2QBF on QBFLIB [18], and moreover, studies on the location of hard instances for randomly generated 2QBFs have been reported in [19–21]. The problem 2QBF is to decide whether a quantified Boolean formula (QBF) Φ = ∀X∃Y φ, where X and Y are disjoint sets of propositional variables and φ = D1 ∧ . . . ∧ Dk is a CNF formula over X ∪ Y , is valid. The transformation from 2QBF to disjunctive logic programming is a slightly altered form of a reduction used in [22]. The propositional disjunctive logic program Pφ produced by the transformation requires 2 ∗ (|X |+ |Y |) + 1 propositional predicates (with one dedicated pre... |