A simple and efficient boolean solver for Constraint Logic Programming

We study in this paper the use of consistency techniques and local propagation methods, originally developed for constraints over finite domains, for solving boolean constraints in Constraint Logic Programming (CLP). To this aim, we first present a boolean CLP language clp(B/FD) built upon a CLP language over finite domains clp(FD) which uses a propagation-based constraint solver. It is based on a single primitive constraint which allows the boolean solver to be encoded at a low level. The boolean solver obtained in this way is both very simple and very efficient: on average it is eight times faster than the CHIP propagation-based boolean solver, i.e. nearly an order of magnitude faster, and infinitely better than the CHIP boolean unification solver. It also performs on average several times faster than special-purpose stand-alone boolean solvers. We then present in a second time several simplifications of the above approach, leading to the design of a very simple and compact dedicated boolean solver. This solver can be implemented in a WAM-based logical engine with a minimal extension limited to four new abstract instructions. This clp(B) system provides a further factor two speedup w.r.t. clp(B/FD).     

Extending constraint logic programming for temporal reasoning

In recent years, several constraint‐based temporal reasoning frameworks have been proposed. They consider temporal points or intervals as domain elements linked by temporal constraints. Temporal reasoning in these systems is based on constraint propagation. In this paper, we argue that a language based on constraint propagation can be a suitable tool for expressing and reasoning about temporal problems. We concentrate on Constraint Logic Programming (CLP) which is a powerful programming paradigm combining the advantages of Logic Programming and the efficiency of constraint solving. However, CLP presents some limitations in dealing with temporal reasoning. First, it uses an “arc consistency” propagation algorithm which is embedded in the inference engine, cannot be changed by the user, and is too weak in many temporal frameworks. Second, CLP is not able to deal with qualitative temporal constraints. We present a general meta CLP architecture which maintains the advantages of CLP, but overcomes these two main limitations. Each architectural level is a finite domain constraint solver(CLP(FD)) that reasons about constraints of the underlying level. Based on this conceptual architecture, we extend the CLP(FD)language and we specialize the extension proposed on Vilain and Kautz’sPoint Algebra, on Allen’s Interval Algebra and on the STP framework by Dechter, Meiri and Pearl. In particular, we show that we can cope effectively with disjunctive constraints even in an interval‐based framework. This revised version was published online in June 2006 with corrections to the Cover Date.     

Naive Bayes for optimal ranking

This paper presents experimental comparisons between the declarative encodings of various computationally hard problems in Answer Set Programming (ASP) and Constraint Logic Programming over Finite Domains (CLP(FD)). The objective is to investigate how solvers in the two domains respond to different problems, highlighting the strengths and weaknesses of their implementations, and suggesting criteria for choosing one approach over the other. Ultimately, the work in this paper is expected to lay the foundations for a transfer of technology between the two domains, for example by suggesting ways to use CLP(FD) in the execution of ASP.     

Mixed Global Constraints and Inference in Hybrid CLP–IP Solvers

The complementing strengths of Constraint (Logic) Programming (CLP) and Mixed Integer Programming (IP) have recently received significant attention. Although various optimization and constraint programming packages at a first glance seem to support mixed models, the modeling and solution techniques encapsulated are still rudimentary. Apart from exchanging bounds for variables and objective, little is known of what constitutes a good hybrid model and how a hybrid solver can utilize the complementary strengths of inference and relaxations. This paper adds to the field by identifying constraints as the essential link between CLP and IP and introduces an algorithm for bidirectional inference through these constraints. Together with new search strategies for hybrid solvers and cut-generating mixed global constraints, solution speed is improved over both traditional IP codes and newer mixed solvers.     

Enhancing CLP branch and bound techniques for scheduling problems

In this paper, we propose a constraint logic programming (CLP) approach to the solution of a job shop scheduling problem in the field of production planning in orthopaedic hospital departments. A pure CLP on finite domain (CLP(FD)) approach to the problem has been developed, leading to disappointing results. In fact, although CLP(FD) has been recognized as a suitable tool for solving combinatorial problems, it presents some drawbacks for optimization problems. The main reason concerns the fact that CLP(FD) solvers do not effectively handle the objective function and cost‐based reasoning through the simple branch and bound scheme they embed. Therefore, we have proposed an improvement of the standard CLP branch and bound algorithm by exploiting some well‐known operations research results. The branch and bound we integrate in a CLP environment is based on the optimal solution of a relaxation of the original problem. In particular, the relaxation used for the job shop scheduling problem considered is the well‐known shifted bottleneck procedure considering single machine problems. The idea is to decompose the original problem into subproblems and solve each of them independently. Clearly, the solutions of each subproblem may violate constraints among different subproblems which are not taken into account. However, these solutions can be exploited in order to improve the pruning of the search space and to guide the search by defining cost‐based heuristics. The resulting algorithm achieves a significant improvement with respect to the pure CLP(FD) approach that enables the solution of problems which are one order of magnitude greater than those solved by a pure CLP(FD) algorithm. In addition, the resulting code is less dependent on the input data configuration. Copyright © 2001 John Wiley & Sons, Ltd.     

Nicolog: A simple yet powerful cc(FD) language

In this paper, we describe Nicolog, a language with capabilities similar to recently developed constraint logic programming (CLP) languages such as CLP(BNR), clp(FD), and cc(FD). Central to Nicolog are projection constraints (PCs), a sublanguage for compiling and optimizing constraint propagation in numeric and Boolean domains. PCs are an interesting generalization of the indexical constraints introduced in cc(FD) and also found in clp(FD). Nicolog compiles a very general class of built-in constraints into equivalent sets of PCs, allowing an arbitrary mixture of integer (easily extensible to real) and Boolean operations. Nicolog also lets the user program PCs directly, making it possible to implement new sophisticated propagation procedures. We show that PCs are a simple, efficient, and flexible way to implement most of the propagation procedures possible in other FD CLP systems. These include procedures for cardinality, constructive disjunction, implication, and mixed Boolean/numeric constraints. Empirical results with a simple prototype Nicolog implementation based on the WAM architecture show it can solve hard problems with speed comparable to the fastest existing CLP systems.     

Numeric semantics of class diagrams with multiplicity and uniqueness constraints

We translate class diagrams with multiplicity constraints and uniqueness attributes to inequalities over non-negative integers. Based on this numeric semantics we check the satisfiability and consistency of class diagrams and compute minimal models. We show that this approach is efficient and provides succinct user feedback in the case of errors. In an experimental section we demonstrate that general off-the-shelf solvers for integer linear programming perform as well on real-world and synthetic benchmarks as specialised algorithms do, facilitating the extension of the formal model by further numeric constraints like cost functions. Our results are embedded in a research programme on reasoning about class diagrams and are motivated by applications in configuration management. Compared to other (for instance logic-based) approaches our aim is to hide the complexity of formal methods behind familiar user interfaces like class diagrams and to concentrate on problems that can be solved efficiently in order to be able to provide immediate feedback to users.     

Meta-Level interpretation of constraint languages a case study: Logical primitives

This paper provides a detailed presentation of a Prolog-written meta-level interpreter for a constraint logic programming (CLP) language for expressing equalities and disequalities of finite trees, as well as non-negative integers (arities). The logical interpretation of the Prolog primitive functor (whose arguments are trees and arity) is used to illustrate the interactions among constraints pertaining to multiple domains. The paper’s objective is to provide insights about CLP language design and to present a modularized, incrementally-expandable meta-processor for this class of languages.     

用CLP技术解决动画自动生成中的布局规划问题*

以本实验室研制的一个多重论域的约束逻辑程序设计系统BPUCLP为基础,提出用约束逻辑程序(Constraint Logic Programming,CLP)解决布局规划问题。该方法用几何模型表示对象,用算术约束描述对象间的位置关系,并通过BPUCLP的约束求解机制为各个位置变量取值。该方法实现了二维人物初始布局规划和三维卧室家具布局规划。实验证明该方法是有效的。     

Qualitative reasoning with directional relations

Qualitative spatial reasoning (QSR) pursues a symbolic approach to reasoning about a spatial domain. Qualitative calculi are defined to capture domain properties in relation operations, granting a relation algebraic approach to reasoning. QSR has two primary goals: providing a symbolic model for human common-sense level of reasoning and providing efficient means for reasoning. In this paper, we dismantle the hope for efficient reasoning about directional information in infinite spatial domains by showing that it is inherently hard to decide consistency of a set of constraints that represents positions in the plane by specifying directions from reference objects. We assume that these reference objects are not fixed but only constrained through directional relations themselves. Known QSR reasoning methods fail to handle this information.     

Constraint Logic Programming and Integer Programming approaches and their collaboration in solving an assignment scheduling problem

Generalised Assignment Problems (GAP), traditionally solved by Integer Programming techniques, are addressed in the light of current Constraint Programming methods. A scheduling application from manufacturing, based on a modified GAP, is used to examine the performance of each technique under a variety of problem characteristics. Experimental evidence showed that, for a set of assignment problems, Constraint Logic Programming (CLP) performed consistently better than Integer Programming (IP). Analysis of the CLP and IP processes identified ways in which the search was effective. The insight gained from the analysis led to an Integer Programming approach with significantly improved performance. Finally, the issue of collaboration between the two contrasting approaches is examined with respect to ways in which the solvers can be combined in an effective manner.     

A Comparative Study of Eight Constraint Programming Languages Over the Boolean and Finite Domains

This paper compares the efficiency of a number of Constraint Logic Programming (CLP) systems in the setting of finite domains as well as a specific aspect of their expressiveness (that concerning reification and meta-constraints). There are two key reasons for adopting CLP technology for solving a problem. The first is its expressiveness enabling a declarative solution with readable code which is vital for maintenance and the second is the provision of an efficient implementation for the computationally expensive procedures. However, CLP systems differ significantly both in how solutions may be expressed and the efficiency of their execution and it is important that both these factors are taken into account when choosing the best CLP system for a particular application. This paper aids this choice by illustrating differences between the systems, indicating their particular strengths and weaknesses.     

Constraint-based deductive model checking

We show that constraint logic programming (CLP) can serve as a conceptual basis and as a practical implementation platform for the model checking of infinite-state systems. CLP programs are logical formulas (built up from constraints) that have both a logical interpretation and an operational semantics. Our contributions are: (1) a translation of concurrent systems (imperative programs) into CLP programs with the same operational semantics; and (2) a deductive method for verifying safety and liveness properties of the systems which is based on the logical interpretation of the CLP programs produced by the translation. We have implemented the method in a CLP system and verified well-known examples of infinite-state programs over integers, using linear constraints here as opposed to Presburger arithmetic as in previous solutions. Published online: 18 July 2001     

Cost-based Filtering for Shorter Path Constraints

Many real world problems, e.g. personnel scheduling and transportation planning, can be modeled naturally as Constrained Shortest Path Problems (CSPPs), i.e., as Shortest Path Problems with additional constraints. A well studied problem in this class is the Resource Constrained Shortest Path Problem. Reduction techniques are vital ingredients of solvers for the CSPP, that is frequently NP-hard, depending on the nature of the additional constraints. Viewed as heuristics, these techniques have not been studied theoretically with respect to their efficiency, i.e., with respect to the relation of filtering power and running time. Using the concepts of Constraint Programming, we provide a theoretical study of cost-based filtering for shorter path constraints on acyclic, on undirected, and on directed graphs that do not contain negative cycles. We then show empirically how reasoning about path-substructures in combination with CP-based Lagrangian relaxation can help to improve significantly over previously developed problem-tailored filtering algorithms for the resource constrained shortest path problem and investigate the impact of required-edge detection, undirected versus directed filtering, and the choice of the algorithm optimizing the Lagrangian dual.     

Weight constraint programs with evaluable functions

In the current practice of Answer Set Programming (ASP), evaluable functions are represented as special kinds of relations. This often makes the resulting program unnecessarily large when instantiated over a large domain. The extra constraints needed to enforce the relation as a function also make the logic program less transparent. In this paper, we consider adding evaluable functions to answer set logic programs. The class of logic programs that we consider here is that of weight constraint programs, which are widely used in ASP. We propose an answer set semantics to these extended weight constraint programs and define loop completion to characterize the semantics. Computationally, we provide a translation from loop completions of these programs to instances of the Constraint Satisfaction Problem (CSP) and use the off-the-shelf CSP solvers to compute the answer sets of these programs. A main advantage of this approach is that global constraints implemented in such CSP solvers become available to ASP. The approach also provides a new encoding for CSP problems in the style of weight constraint programs. We have implemented a prototype system based on these results, and our experiments show that this prototype system competes well with the state-of-the-art ASP solvers. In addition, we illustrate the utilities of global constraints in the ASP context.     

A uniform random test data generator for path testing

Path-oriented Random Testing (PRT) aims at generating a uniformly spread out sequence of random test data that execute a single control flow path within a program. The main challenge of PRT lies in its ability to build efficiently such a test suite in order to minimize the number of rejects (test data that execute another control flow path). We address this problem with an original divide-and-conquer approach based on constraint reasoning over finite domains, a well-recognized Constraint Programming technique. Our approach first derives path conditions by using backward symbolic execution and computes a tight over-approximation of their associated subdomain by using constraint propagation and constraint refutation. Second, a uniform random test data generator is extracted from this approximated subdomain. We implemented this approach and got experimental results that show the practical benefits of PRT based on constraint reasoning. On average, we got a two-order magnitude CPU time improvement over standard Random Testing on a set of paths extracted from classical benchmark programs.     

MiniBrass: Soft constraints for MiniZinc

Over-constrained problems are ubiquitous in real-world decision and optimization problems. Plenty of modeling formalisms for various problem domains involving soft constraints have been proposed, such as weighted, fuzzy, or probabilistic constraints. All of them were shown to be instances of algebraic structures. In terms of modeling languages, however, the field of soft constraints lags behind the state of the art in classical constraint optimization. We introduce MiniBrass, a versatile soft constraint modeling language building on the unifying algebraic framework of partially ordered valuation structures (PVS) that is implemented as an extension of MiniZinc and MiniSearch. We first demonstrate the adequacy of PVS to naturally augment partial orders with a combination operation as used in soft constraints. Moreover, we provide the most general construction of a c-semiring from an arbitrary PVS. Both arguments draw upon elements from category theory. MiniBrass turns these theoretical considerations into practice: It offers a generic extensible PVS type system, reusable implementations of specific soft constraint formalisms as PVS types, operators for complex PVS products, and morphisms to transform PVS. MiniBrass models are compiled into MiniZinc to benefit from the wide range of solvers supporting FlatZinc. We evaluated MiniBrass on 28 “softened” MiniZinc benchmark problems with six different solvers. The results demonstrate the feasibility of our approach.     

Bridging qualitative spatial constraints and feature-based parametric modelling: Expressing visibility and movement constraints

We present a concept for integrating state-of-the-art methods in geometric and qualitative spatial representation and reasoning with feature-based parametric modelling systems. Using a case-study involving a combination of topological, visibility, and movement constraints, we demonstrate the manner in which a parametric model may be constrained by the spatial aspects of conceptual design specifications and higher-level semantic design requirements. We demonstrate the proposed methodology by applying it to architectural floor plan layout design, where a number of spaces with well defined functionalities have to be arranged such that particular functional design constraints are maintained. The case-study is developed by an integration of the declarative spatial reasoning system CLP(QS) (CLP(QS) – a declarative spatial reasoning system. www.spatial-reasoning.com.) with the parametric CAD system FreeCAD.