  This paper presents a logic language for expressing NP search and
optimization problems. Specifically, first a language obtained by extending
(positive) Datalog with intuitive and efficient constructs (namely, stratified
negation, constraints and exclusive disjunction) is introduced. Next, a further
restricted language only using a restricted form of disjunction to define
(non-deterministically) subsets (or partitions) of relations is investigated.
This language, called NP Datalog, captures the power of Datalog with
unstratified negation in expressing search and optimization problems. A system
prototype implementing NP Datalog is presented. The system translates NP
Datalog queries into OPL programs which are executed by the ILOG OPL
Development Studio. Our proposal combines easy formulation of problems,
expressed by means of a declarative logic language, with the efficiency of the
ILOG System. Several experiments show the effectiveness of this approach.
