On the Implementation of a Logic Language for NP Search and Optimization Problems

On the Implementation of a Logic Language for NP Search and Optimization Problems

Sergio Greco (University of Calabria, Italy), Cristian Molinaro (University of Calabria, Italy), Irina Trubitsyna (University of Calabria, Italy) and Ester Zumpano (University of Calabria, Italy)
DOI: 10.4018/978-1-60566-242-8.ch084
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

It is well known that NP search and optimization problems can be formulated as DATALOG¬ (datalog with unstratified negation; Abiteboul, Hull, & Vianu, 1994) queries under nondeterministic stable-model semantics so that each stable model corresponds to a possible solution (Gelfond & Lifschitz, 1988; Greco & Saccà, 1997; Kolaitis & Thakur, 1994). Although the use of (declarative) logic languages facilitates the process of writing complex applications, the use of unstratified negation allows programs to be written that in some cases are neither intuitive nor efficiently valuable. This article presents the logic language NP Datalog, a restricted version of DATALOG¬ that admits only controlled forms of negation, such as stratified negation, exclusive disjunction, and constraints. NP Datalog has the same expressive power as DATALOG¬, enables a simpler and intuitive formulation for search and optimization problems, and can be easily translated into other formalisms. The example below shows how the vertex cover problem can be expressed in NP Datalog.
Chapter Preview
Top

Introduction

It is well known that NP search and optimization problems can be formulated as DATALOG¬ (datalog with unstratified negation; Abiteboul, Hull, & Vianu, 1994) queries under nondeterministic stable-model semantics so that each stable model corresponds to a possible solution (Gelfond & Lifschitz, 1988; Greco & Saccà, 1997; Kolaitis & Thakur, 1994). Although the use of (declarative) logic languages facilitates the process of writing complex applications, the use of unstratified negation allows programs to be written that in some cases are neither intuitive nor efficiently valuable. This article presents the logic language NP Datalog, a restricted version of DATALOG¬ that admits only controlled forms of negation, such as stratified negation, exclusive disjunction, and constraints. NP Datalog has the same expressive power as DATALOG¬, enables a simpler and intuitive formulation for search and optimization problems, and can be easily translated into other formalisms. The example below shows how the vertex cover problem can be expressed in NP Datalog.

Example 1. Given an undirected graph G = <N, E>, a subset of the vertexes VN is a vertex cover of G if every edge of G has at least one end in V. The problem can be formulated in terms of the NP Datalog query <P1,v(X)> with P1 defined as follows:v(X) ⊆ node(X)edge(X,Y) ⇒ v(X) ∨ v(Y),where the output relation v gives a vertex cover, ⊆ denotes the subset relation, and ⇒ is used to define constraint. The first rule guesses a subset v of the relation node whereas the latter constraint verifies the vertex cover condition: It states that if X and Y are two connected nodes, then X or Y or both must be in the cover. The optimization problem computing a cover with minimum cardinality can be simply expressed by means of the query <P1, min|v(X)|>.

The evaluation of logic programs with stable-model semantics can be carried out by means of current ASP (answer set programming) systems that compute the semantics of DATALOG¬ programs. An alternative solution consists of reducing problems expressed by means of logic formalisms (usually extensions of datalog) into equivalent SAT problems and evaluating the target problems by means of SAT solvers. In this article, a different solution, based on the rewriting of logic programs into constraint programming, is proposed. More specifically, the implementation of NP Datalog consists of translating NP Datalog queries into OPL (optimization programming language; Van Hentenryck, 1999; Van Hentenryck, Michel, Perron, & Regin, 1999), a constraint language well suited for solving both search and optimization problems, and then executing the target OPL code by means of the ILOG OPL Studio platform.

Example 2. The optimization query of Example 1 is translated into the following OPL code.

var boolean v[node];
minimize sum (x in node) v[x]
subject to {
forall (<x,y> in edge) 
1 ⇒ (v[x] + v[y] > 0); 
}

where the second statement expresses the optimization condition (minimizes the cardinality of v), while the last one corresponds to the vertex cover condition.

Top

Np Datalog

Familiarity is assumed with disjunctive logic programs, disjunctive deductive databases, (disjunctive) stable-model semantics, and computational complexity (Abiteboul et al., 1994; Gelfond & Lifschitz, 1991; Johnson, 1990). In this section, the language NP Datalog is presented. This language restricts the use of unstratified negation of DATALOG¬ without loss of its expressive power and can be executed more efficiently or easily translated into other formalisms. NP Datalog extends DATALOG¬s (datalog with stratified negation) with two simple forms of unstratified negation embedded into built-in constructs: exclusive disjunction, used in partition rules, and constraint rules.

Key Terms in this Chapter

Answer Set Programming (ASP): A programming paradigm that uses logic to express and solve search problems. Given a search problem, a logic theory can be designed so that models of this theory represent problem solutions.

Stable-Model Semantics: Declarative semantics for logic programs with negation.

Constraint Programming (CP): A programming paradigm that expresses a problem by means of a set of constraints that must be satisfied by the solutions of the problem.

Optimization Programming Language (OPL): A modeling language to represent optimization problems.

Disjunctive Datalog Program: A set of (disjunctive datalog) rules of the form A1 ? … ? Ak ? B1, ..., Bm, not Bm+1, …, not Bn, k+n>0, where A1, …, Ak, B1, …, Bn are atoms of the form p(t1, ..., th), p is a predicate symbol of arity h, and the terms t1,..., th are constants or variables. A not-free (?-free) program is called positive (or normal). Predicate symbols are partitioned into two distinct sets: base predicates (also called EDB predicates) and derived predicates (also called IDB predicates). Base predicates correspond to database relations defined over a given domain and they do not appear in the head of any rule; derived predicates are defined by means of rules.

Constraint Logic Programming (CLP): A programming paradigm that extends logic programming by a mechanism for constraints modeling and processing.

SAT: The Boolean satisfiability problem. It consists of determining a satisfying variable assignment, V, for a Boolean function, f, or determining that no such V exists. SAT is one of the central NP-complete problems.

Complete Chapter List

Search this Book:
Reset