Optimization and Relaxation in Constraint Logic Languages

Abstract

Optimization and relaxation are two important operations that naturally arise in many applications involving constraints, e.g., engineering design, scheduling, decision support, etc. In optimization, we are interested in finding the optimal (i.e., best) solutions to a set of constraints with respect to an objective function. In many applications, optimal solutions may be difficult or impossible to obtain, and hence we are interested in finding suboptimal solutions, by either relaxing the constraints or relaxing the objective function. The contribution of this paper lies in providing a logical framework for performing optimization and relaxation in a constraint logic programming language. Our proposed framework is called preference logic programming (PLP), and its use for optimization was discussed in [8]. Essentially, in PLP we can designate certain predicates as optimization predicates, and we can specify the objective function by stating preference criteria for determining the optimal solutions to these predicates. This paper extends the PLP paradigm with facilities to formulate relaxation problems in a natural manner. We introduce the concept of a relaxation goal, and discuss its use for preference relaxation. Our model-theoretic semantics of relaxation is based on simple concepts from modal logic: Essentially, each world in the possible-worlds semantics for a preference logic program is a model for the constraints of the program, and an ordering over these worlds is determined by the objective function. Optimization can then be expressed as truth in strongly optimal worlds, while relaxation becomes truth in suitably-defined suboptimal worlds. We also present an operational semantics for relaxation as well as correctness results. Our conclusion is that the concept of preference provides a unifying framework for formulating optimization as well as relaxation problems.