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

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 V ⊆ N 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 <P₁,v(X)> with P₁ 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 <P₁, 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.

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.