Principles and Practice of Constraint Programming — CP96

We introduce the notion of confluence for Constraint Handling Rules (CHR), a powerful language for writing constraint solvers. With CHR one simplifies and solves constraints by applying rules. Confluence guarantees that a CHR program will always compute the same result for a given set of constraints independent of which rules are applied. We give a decidable, sufficient and necessary syntactic condition for confluence.Confluence turns out to be an essential syntactical property of CHR programs for two reasons. First, confluence implies correctness (as will be shown in this paper). In a correct CHR program, application of CHR rules preserves logical equivalence of the simplified constraints. Secondly, even when the program is already correct, confluence is highly desirable. Otherwise, given some constraints, one computation may detect their inconsistency while another one may just simplify them into a still complex constraint.As a side-effect, the paper also gives soundness and completeness results for CHR programs. Due to their special nature, and in particular correctness, these theorems are stronger than what holds for the related families of (concurrent) constraint programming languages.

Numerous arc consistency algorithms have been developed for filtering constraint satisfaction problems (CSP). But, few of them considered the semantic of the constraints. Arc consistency algorithms work with a queue containing element to reconsider. Then, some constraints may be checked many times. Recently, Liu has proposed an improved specific version AC5+ of the AC5 algorithm. AC5+ deals with a subclass of functional constraints, called “Increasing Functional Constraints (IFC)”. It allows some IFC constraints of a CSP to be checked only once, when achieving arc consistency. In this paper, we propose a labelling arc consistency method (LAC) for filtering CSPs containing functional constraints. LAC uses two concepts:arc consistency and label-arc consistency. It allows all functional constraints to be checked only once, and some general constraints to be checked at most twice. Although, the complexity of LAC is still in O(ed) for functional constraints, where e is the number of constraints and d the size of the largest domain, the technique used in LAC leads to improve the performances and the effectiveness of classical arc consistency algorithms for CSPs containing functional constraints. The empirical results presented show the substantial gain brought by the LAC method.

A wavelength-routed, optical network employs all-optical channels (lightpaths) on multiple wavelengths to establish a rearrangeable interconnection pattern (virtual topology) for transport of data. A lightpath may span multiple fiber-links, and may be routed optically at an intermediate node without undergoing electronic conversion. We examine the problem of establishing a set of lightpaths in an optical network, which employs a passive wavelength routing device called a Latin Router (LR). Latin Routers are attractive for optical network design because of their fault-tolerance and low cost, but make traditional routing algorithms difficult to implement due to the complexity of the constraints they impose on legitimate routes and colors. We employ a local search algorithm to search the space of virtual topologies in order to satisfy a maximum number of given lightpath requests. We use the same algorithm to maximize the number of single-hop connections for a given network. We show that the algorithm can satisfy a high percentage of lightpaths under low to moderate network loads. Experiments reveal that we can establish O(N) lightpaths in an optical network with N nodes. We believe that our work is the first known attempt at designing optical wide-area networks using Latin Routers.

While CNF propositional satisfiability (SAT) is a sub-class of the more general constraint satisfaction problem (CSP), conventional wisdom has it that some well-known CSP look-back techniques — including backjumping and learning — are of little use for SAT. We enhance the Tableau SAT algorithm of Crawford and Auton with look-back techniques and evaluate its performance on problems specifically designed to challenge it.The Random 3-SAT problem space has commonly been used to benchmark SAT algorithms because consistently difficult instances can be found near a region known as the phase transition. We modify Random 3-SAT in two ways which make instances even harder. First, we evaluate problems with structural regularities and find that CSP look-back techniques offer little advantage. Second, we evaluate problems in which a hard unsatisfiable instance of medium size is embedded in a larger instance, and we find the look-back enhancements to be indispensable. Without them, most instances are “exceptionally hard” — orders of magnitude harder than typical Random 3-SAT instances with the same surface characteristics.

In the last twenty years, many algorithms and heuristics were developed to find solutions in constraint networks. Their number increased to such an extent that it quickly became necessary to compare their performances in order to propose a small number of “good” methods. These comparisons often led us to consider FC or FC-CBJ associated with a “minimum domain” variable ordering heuristic as the best techniques to solve a wide variety of constraint networks.In this paper, we first try to convince once and for all the CSP community that MAC is not only more efficient than FC to solve large practical problems, but it is also really more efficient than FC on hard and large random problems. Afterwards, we introduce an original and efficient way to combine variable ordering heuristics. Finally, we conjecture that when a good variable ordering heuristic is used, CBJ becomes an expensive gadget which almost always slows down the search, even if it saves a few constraint checks.

We investigate a class of set constraints that is used for the type analysis of concurrent constraint programs. Its constraints are inclusions between first-order terms (without set operators) interpreted over non-empty sets of finite trees. We show that this class has the independence property. We give a polynomial algorithm for entailment. The independence property is a fundamental property of constraint systems. It says that the constraints cannot express disjunctions, or, equivalently, that negated conjuncts are independent from each other. As a consequence, the satisfiability of constraints with negated conjuncts can be directly reduced to entailment.

The paper describes a simple modeling and programming approach for speeding up constraint propagation. The idea, although similar to redundant constraints, is based on the concept of redundant modeling. We define CSP model and model redundancy formally, and show how mutually redundant models can be combined and connected using channeling constraints. The combined model contains the original but redundant models as sub-models. Channeling constraints allow the sub-models to cooperate during constraint-solving by propagating constraints freely amongst the sub-models. This extra level of pruning and propagation activities becomes the source of execution speedup. We apply our method to the design and construction of a real-life nurse rostering system. Experimental results provide empirical evidence in line with our prediction.

In this paper, we formulate train rescheduling as constraint satisfaction problem and describe a constraint propagation approach to tackle it. Algorithms for timetable verifications and train rescheduling are designed under a coherent framework. We define two optimality criteria that correspond to minimizing passenger delay and the number of station visit modifications respectively for rescheduling. Two heuristics are then proposed to speed up and direct the search towards the optimal solutions. The feasibility of our proposed algorithms and heuristics are confirmed with experimentation using real-life data.

There has been considerable research interest into the solubility phase transition, and its effect on search cost for backtracking algorithms. In this paper we show that a similar easy-hard-easy pattern occurs for local search, with search cost peaking at the phase transition. This is despite problems beyond the phase transition having fewer solutions, which intuitively should make the problems harder to solve. We examine the relationship between search cost and number of solutions at different points across the phase transition, for three different local search procedures, across two problem classes (CSP and SAT). Our findings show that there is a significant correlation, which changes as we move through the phase transition.

In this paper we investigate which constraints may be derived from a given set of constraints. We show that, given a set of relations $$\mathcal{R}$$ , all of which are invariant under some set of permutations P, it is possible to derive any other relation which is invariant under P, using only the projection, Cartesian product, and selection operators, together with the effective domain of $$\mathcal{R}$$ , provided that the effective domain contains at least three elements. Furthermore, we show that the condition imposed on the effective domain cannot be removed. This result sharpens an earlier result of Paredaens [13], in that the union operator turns out to be superfluous. In the context of constraint satisfaction problems, this result shows that a constraint may be derived from a given set of constraints containing the binary disequality constraint if and only if it is closed under the same permutations as the given set of constraints.

Recent improvements in constraint programming have made it possible to tackle hard problems in a practical way. Before this, these problems were solved only by specialized programs often complex to implement. Scheduling problems and more especially the job-shop problem belong to this class. In this paper we explain a relatively simple constraint system, which enables us to solve 10 × 10 problems efficiently. The method described here, based on evaluations which come as close as possible to release and due dates of jobs to be scheduled, requires no prior knowledge of the problem being processed, in particular, no bounds over optimum value (consequently no specific algorithm to find approximate solutions). We also comment on the results of experiments on known problems. As far as we know, the system outlined here is the only one that, using just constraint solving and an exhaustive enumeration strategy, can completely solve orb3[AC91] in less than half an hour computational time.

Constraint propagation algorithms vary in the strength of propagation they apply. This paper investigates a simple configuration for adaptive propagation—the process of varying the strength of propagation to reflect the dynamics of search. We focus on two propagation methods, Arc Consistency (AC) and Forward Checking (FC). AC-based algorithms apply a stronger form of propagation than FC-based algorithms; they invest greater computational effort to detect inconsistent values earlier. The relative payoff of maintaining AC during search as against FC may vary for different constraints and for different intermediate search states. We present a scheme for Adaptive Arc Propagation (AAP) that allows the flexible combination of the two methods. Metalevel reasoning and heuristics are used to dynamically distribute propagation effort between the two. One instance of AAP, Anti-Functional Reduction (AFR), is described in detail here. AFR achieves precisely the same propagation as a pure AC algorithm while significantly improving its average performance. The strategy is to gradually reduce the scope of AC propagation during backtrack search to exclude those arcs that may be subsequently handled as effectively by FC. Experimental results confirm the power of AFR and the validity of adaptive propagation in general.

The constraint satisfaction community has developed a number of heuristics for variable ordering during backtracking search. For example, in conjunction with algorithms which check forwards, the Fail-First (FF) and Brelaz (Bz) heuristics are cheap to evaluate and are generally considered to be very effective. Recent work to understand phase transitions in NP-complete problem classes enables us to compare such heuristics over a large range of different kinds of problems. Furthermore, we are now able to start to understand the reasons for the success, and therefore also the failure, of heuristics, and to introduce new heuristics which achieve the successes and avoid the failures. In this paper, we present a comparison of the Bz and FF heuristics in forward checking algorithms applied to randomly-generated binary CSP's. We also introduce new and very general heuristics and present an extensive study of these. These new heuristics are usually as good as or better than Bz and FF, and we identify problem classes where our new heuristics can be orders of magnitude better. The result is a deeper understanding of what helps heuristics to succeed or fail on hard random problems in the context of forward checking, and the identification of promising new heuristics worthy of further investigation.

The goal of this paper is twofold. First, we introduce a class of local search procedures for solving optimization and constraint problems. These procedures are based on various heuristics for choosing variables and values in order to examine a general neighborhood. Second, four combinations of heuristics are empirically evaluated by using the graph-coloring problem and a real world application — the frequency assignment problem. The results are also compared with those obtained with other approaches including simulated annealing, Tabu search, constraint programming and heuristic graph coloring algorithms. Empirical evidence shows the benefits of this class of local search procedures for solving large and hard instances.

This paper presents a defeasible constraint solver for the domain of linear equations, disequations and inequalities over the body of rational/real numbers. As extra requirements resulting from the incorporation of the solver into an Incremental Hierarchical Constraint Solver (IHCS) scenario we identified: a)the ability to refer to individual constraints by a label, b) the ability to report the (minimal) cause for the unsatisfiability of a set of constraints, and c) the ability to undo the effects of a formerly activated constraint.We develop the new functionalities after starting the presentation with a general architecture for defeasible constraint solving, through a solved form algorithm that utilizes a generalized, incremental variant of the Simplex algorithm, where the domain of a variable can be restricted to an arbitrary interval. We demonstrate how generalized slacks form the basis for the computation of explanations regarding the cause of unsatisfiability and/or entailment in terms of the constraints told, and the possible deactivation of constraints as demanded by the hierarchy handler.

The constraint programming community has recently begun to address certain types of optimization problems. These problems tend to be discrete or to have discrete elements. Although sensitivity analysis is well developed for continuous problems, progress in this area for discrete problems has been limited. This paper proposes a general approach to sensitivity analysis that applies to both continuous and discrete problems. In the continuous case, particularly in linear programming, sensitivity analysis can be obtained by solving a dual problem. One way to broaden this result is to generalize the classical idea of a dual to that of an “inference dual,” which can be defined for any optimization problem. To solve the inference dual is to obtain a proof of the optimal value of the problem. Sensitivity analysis can be interpreted as an analysis of the role of each constraint in this proof. This paper shows that traditional sensitivity analysis for linear programming is a special case of this approach. It also illustrates how the approach can work out in a discrete problem by applying it to 0–1 linear programming (linear pseudo-boolean optimization).

‘Constraint hierarchy’ is a nonmonotonic system that allows programmers to describe over-constrained real-world problems by specifying constraints with hierarchical preferences, and has been applied to various areas. An important aspect of constraint hierarchies is the existence of efficient satisfaction algorithms based on local propagation. However, past local-propagation algorithms have been limited to multi-way equality constraints. We overcome this by reformulating constraint hierarchies with a more strict definition, and proposing generalized local propagation as a theoretical framework for studying constraint hierarchies and local propagation. Then, we show that global semi- monotonicity in satisfying hierarchies turns out to be a practically useful property in generalized local propagation. Finally, we discuss the relevance of generalized local propagation with our previous DETAIL algorithm for solving hierarchies of multi-way equality constraints.

We present a general methodology for transforming between HCLP and PCSP in both directions. HCLP and PCSP each have advantages when modelling problems, and each have advantages when implementing models and solving them. Using the work presented in this paper, the appropriate paradigm can be used for each of these steps, with a meaning-preserving transformation in between if necessary.

Many combinatorial search problems can be expressed as ‘constraint satisfaction problems’, and this class of problems is known to be NP-complete in general. In this paper we investigate restricted classes of constraints which give rise to tractable problems. We show that any set of constraints must satisfy a certain type of algebraic closure condition in order to avoid NP-completeness. We also describe a simple test which can be applied to establish whether a given set of constraints satisfies a condition of this kind. The test involves solving a particular constraint satisfaction problem, which we call an ‘indicator problem’.

In a recent paper, the concept of “free amalgamation” has been introduced as a general methodology for interweaving solution structures for symbolic constraints, and it was shown how constraint solvers for two components can be lifted to a constraint solver for the free amalgam. Here we discuss a second general way for combining solution domains, called rational amalgamation. In praxis, rational amalgamation seems to be the preferred combination principle if the two solution structures to be combined are “rational” or “non-wellfounded” domains. It represents, e.g., the way how rational trees and rational lists are interwoven in the solution domain of Prolog III, and a variant has been used by W. Rounds for combining feature structures and hereditarily finite non-wellfounded sets. We show that rational amalgamation is a general combination principle, applicable to a large class of structures. As in the case of free amalgamation, constraint solvers for two component structures can be combined to a constraint solver for their rational amalgam. From this algorithmic point of view, rational amalgamation seems to be interesting since the combination technique for rational amalgamation avoids one source of non-determinism that is needed in the corresponding scheme for free amalgamation.

We study the problems of deciding consistency and performing variable elimination for disjunctions of linear inequalities and inequations with at most one inequality per disjunction. This new class of constraints extends the class of generalized linear constraints originally studied by Lassez and McAloon. We show that deciding consistency of a set of constraints in this class can be done in polynomial time. We also present a variable elimination algorithm which is similar to Fourier's algorithm for linear inequalities.

Following the work of Wallace, who introduced the use of directed arc-consistency in MAX-CSP algorithms using DAC counts, we present a number of improvements of DAC usage for the P-EFC3 algorithm. These improvements include: (i) a better detection of dead-ends, (ii) a more effective form for value pruning, and (iii) a different heuristic criterion for value ordering. Considering the new DAC usage, we have analyzed some static variable ordering heuristics previously suggested, and we propose new ones which have been shown effective. The benefits of our proposal has been assessed empirically solving random CSP instances, showing a clear performance gain with respect to previous approaches.

We consider the Weighted Constraint Satisfaction Problem which is a central problem in Artificial Intelligence. Given a set of variables, their domains and a set of constraints between variables, our goal is to obtain an assignment of the variables to domain values such that the weighted sum of satisfied constraints is maximized. In this paper, we present a new approach based on randomized rounding of semidefinite programming relaxation. Besides having provable worst-case bounds, our algorithm is simple and efficient in practice, and produces better solutions than other polynomial-time algorithms such as greedy and randomized local search.

E-GENET shows certain success on extending GENET for non-binary CSP's. However, the generic constraint representation scheme of E-GENET induces the problem of storing too many penalty values in constraint nodes and the min-conflicts heuristic is not efficient enough on some problems. To overcome these two weaknesses and further improve the performance, we propose several modifications. All of them together can boost the efficiency of E-GENET without resorting to modifying the underlying network model or the convergence procedure in an ad hoc manner. The performance of modified E-GENET also compares well against that of CHIP.

We propose in this paper a novel way of looking at local search algorithms for combinatorial optimization problems which better suits constraint programming by performing branch- and-bound search at their core. We concentrate on neighborhood exploration and show how the framework described yields a more efficient local search and opens the door to more elaborate neighborhoods. Numerical results are given in the context of the traveling salesman problem with time windows. This work on neighborhood exploration is part of ongoing research to develop constraint programming tabu search algorithms applied to routing problems.

This paper describes an Evolutionary Algorithm that repairs to solve Constraint Satisfaction Problems. Knowledge about properties of the constraints network can permit to define a fitness function which is used to improve the stochastic search. A selection mechanism which exploits this fitness function has been defined. The algorithm has been tested by running experiments on randomly generated 3-colouring graphs, with different constraints networks. We have also designed a specialized operator “permutation”, which permits to improve the performance of the classic crossover operator, reducing the generations number and a faster convergence to a global optimum, when the population is staying in a local optimum. The results suggest that the technique may be successfully applied to other CSP.

In this paper we introduce the concept of existential variables in finite domain constraint problems. A variable is existential if, once instantiated the other variables, one can always find a value for it such that all constraints are satisfied. In other words, existential variables (and the constraints they are connected to) do not add any information to the rest of the constraint problem. We use the notion of existential variable to achieve what we call incremental k-consistency, which means that different levels of (strong) consistency are obtained on different subparts of the problem, but all lower than or equal to k. At the end, the overall problem can be solved by a backtrack-bounded search, and the complexity of the search will be as if (or smaller) the CSP were k-consistent everywhere. We also consider (1,k)-consistency, which is a form of local consistency which is more powerful than arc-consistency while still removing just domain elements (and thus never adding any new constraint), and we discuss how to get a similar algorithm also for this form of consistency.

This paper investigates logical characterizations of some aspects of concurrent constraint (cc) computations. It contains both negative and positive results.We show that intuitionistic logic enables to observe the so-called stores of a concurrent constraint agent, but neither its successes nor its suspensions, even in the monotonic and deterministic case. On the other hand, IMALL (intuitionistic multiplicative and additive linear logic) does enable the observation of successes (but not that of suspensions): we consider a non-monotonic and non-deterministic version of cc, lcc, and we show that the successes of an lcc computation can be characterized logically; this holds also for cc, since cc can be faithfully translated into lcc.

A globally consistent labeling is a compact representation of the complete solution space for a constraint satisfaction problem (CSP). Constraint satisfaction is NP-complete and so is the construction of globally consistent labelings for general problems. However, for binary constraints, it is known that when constraints are convex, path-consistency is sufficient to ensure global consistency and can be computed in polynomial time. We show how in continuous domains, this result can be generalized to ternary and in fact arbitrary n-ary constraints using the concept of (3,2)-relational consistency. This leads to polynomial-time algorithms for computing globally consistent labelings for a large class of numerical constraint satisfaction problems.

We present an experimental comparison of three modified DeltaBlue algorithms for local-propagation-based constraint solving. Our three modified methods are respectively called DeltaDown method, DeltaUp method and DeltaCost method. These methods were designed to speed up the planning phase or the evaluation phase of the original DeltaBlue method using additional cost functions to break a tie of the walkabout strength. Our cost functions are respectively called up cost and down cost. These cost functions can give us information about the upstream and the downstream constraints. Our experiments show that DeltaUp method brings us a considerable improvement of the total performance of DeltaBlue method using a small overhead of keeping the cost function.

In this paper, we propose an extension of the Jaffar-Lassez Constraint Logic Programming scheme that operates with unions of constraint theories with different signatures and decides the satisfiability of mixed constraints by appropriately combining the constraint solvers of the component theories. We describe the extended scheme and provide logical and operational semantics for it along the lines of those given for the original scheme. Then we show how the main soundness and completeness results of Constraint Logic Programming lift to our extension.

This paper presents the formalization of the symbolic simulation and analysis technique for hybrid systems developed in [9, 7, 8]. The main advantage of this technique is the close relation between the hybrid-systems model Hybrid Automata [1, 8] and the execution model CLP( $$\mathcal{R}$$ ) [3]. Our rule-based description is naturally suited for hybrid systems allowing (a) to lift CLP( $$\mathcal{R}$$ ) definitions and results for the theory of hybrid systems, and therefore (b) to apply — in addition to forward/backward fixpoint computation and symbolic model-checking — CLP( $$\mathcal{R}$$ ) intelligent search and backtracking procedures [2] in their analysis, since the depth-first search strategy of CLP( $$\mathcal{R}$$ ) is incomplete on infinite trees. These techniques were implemented in part on top of the CLP( $$\mathcal{R}$$ ) prototype system [4]. We illustrate our method with a variant of the reactor temperature control system from [1]. More realistic examples can be found in [9, 7, 8, 6].

It has been argued that the linear database model, in which semi-linear sets are the only geometric objects, is very suitable for most spatial database applications. For querying linear databases, the language FO + linear has been proposed. We present both negative and positive results regarding the expressiveness of FO+linear. First, we show that the dimension query is definable in FO + linear, which allows us to solve several interesting queries. Next, we show the non-definability of a whole class of queries that are related to sets not definable in FO+linear. This result both sharpens and generalizes earlier results independently found by Afrati et al. and the present authors, and demonstrates the need for more expressive linear query languages if we want to sustain the desirability of the linear database model. In this paper, we show how FO + linear can be strictly extended within FO + poly in a safe way. Whether any of the proposed extensions is complete for the linear queries definable in FO + poly remains open. We do show, however, that it is undecidable whether an expression in FO + poly induces a linear query.

Problems that do not have complete solutions occur in many areas of application of constraint solving. Heuristic repair methods that have been used successfully on complete CSPs can also be used on overconstrained problems. A difficulty in analyzing their performance is the uncertainty about the goodness of solutions returned in relation to the optimal (best possible) solutions. This difficulty can be overcome by testing these procedures on problems that can be solved by complete methods, which return certifiably optimal solutions. With this experimental strategy, comparative analyses of hill-climbing methods were carried out using anytime curves that could be compared with known optima. In addition, extensive analysis of parameter values for key strategies such as random walk and restarting could be done precisely and efficiently by allowing local search to run until a solution was discovered that was known to be optimal, based on earlier tests with complete methods. An important finding is that a version of min-conflicts that incorporates the random walk strategy, with a good value for the walk probability appears to be as efficient in this domain as several of the more elaborate methods for improving local search that have been proposed in recent years.

This paper presents an initial report on an innovative approach for solving satisfiability problems (SAT), i.e., creating a logic circuit that is specialized to solve each problem instance on Field Programmable Gate Arrays (FPGAs). Until quite recently, this approach was unrealistic since creating special-purpose hardware was very expensive and time consuming. However, recent advances in FPGA technologies and automatic logic synthesis technologies have enabled users to rapidly create special-purpose hardware by themselves.This approach brings a new dimension to SAT algorithms, since all constraints (clauses) can be checked simultaneously using a logic circuit. We develop a new algorithm called parallel-checking, which assigns all variable values simultaneously, and checks all constraints concurrently. Simulation results show that the order of the search tree size in this algorithm is approximately the same as that in the Davis-Putnam procedure. Then, we show how the parallel-checking algorithm can be implemented on FPGAs. Currently, actual implementation is under way. We get promising initial results which indicate that we can implement a hard random 3-SAT problem with 300 variables, and run the logic circuit at clock rates of about 1MHz, i.e., it can check one million states per second.

In this paper, a method within the framework of propagation of interval constraints and based on the branch- and-bound optimization scheme for solving the job-shop scheduling problem will be presented. The goal is to provide a constraint program which is clean, flexible and robust. The design of the constraint program is based on an idea of sorting the release and due dates of tasks, which is a successful application of a previous but not yet published work on a distinct integers constraint. Based on the sorting constraint, by assembling redundant constraints and applying an efficient search strategy, the current program for the job-shop problem can solve the ten 10 × 10 instances in the paper of Applegate and Cook (1991) in satisfactory computational time. Moreover, good results have been achieved on some harder instances.

HCLP extend CLP to include constraint hierarchies. We present an algorithm based on our previous work and on the extended notion of comparators for comparisons between the hierarchies that arise from alternate rule choices in the program.

We describe the design and implementation of a finite domain constraint solver embedded in SICStus Prolog system using an extended unification mechanism via attributed variables as a generic constraint interface. The solver is based on indexicals, i.e. reactive functional rules performing incremental constraint solving or entailment checking. Propagation is done using the arc-consistency algorithm AC-3, adapted for non-binary constraints. At the heart of the algorithm is an evaluator for indexicals.The solver provides the usual predefined search strategies (fixed order, failfirst principle, branch and bound for minimization or maximization). Access predicates for the relevant variable attributes (domain value, bounds and size etc.) are also provided, making customized search strategies easily programmable.A design goal has been to keep the solver open-ended and extendible as well as to keep a substantial part written in Prolog, partly contradicting conventional wisdom in implementing constraint solvers.

Many practical problems are overconstrained, i.e., it is impossible to find a solution that would satisfy all constraints. In such situations one may try to find solutions that satisfy as many constraints as possible, see [1]. In a more general approach one can assign some weights (utilities) to constraints and then look for solutions that maximize the sum of weights of satisfied constraints. The problem of finding such solutions, the Maximum Utility Problem, MUP, is the subject of this paper. We present a number of approximate algorithms for solving this problem. Numerous tests have demonstrated high performance of these algorithms: approximated solutions are, on average, about 2% worse than optimal ones. Our algorithms are local search procedures that iteratively improve the current solution by modifying it. As a heuristic that guides the whole process we use the expected utility value of a solution that can be obtained from the current (partial) solution by extending it to a complete one at random. This heuristic has been motivated by an old algorithm for solving the k-MAXGSAT problem, which was proposed by Johnson, [2].

This work presents a general meta CLP architecture which can be built by adding CLP solvers as meta levels reasoning on the constraints of the underlying object system. We propose two specializations on finite domains: the first concerns the possibility of embedding the capability of performing qualitative reasoning in a CLP framework, while the second concerns a multi-level architecture for obtaining different degrees of consistency by using weaker algorithms.

The symbolic simulation and analysis method for hybrid systems presented in [2] is illustrated by means of the benchmark problem ”The Generalized Railroad Crossing” [1].

Many interesting discrete optimization problems, including airline crew scheduling, vehicle routing and cutting stock, have “good” integer programming formulations that require a huge number of variables. Good means that the linear programming relaxations give tight bounds which implies small search trees. We will discuss classes of problems for which this type of formulation is desirable, and special (non-standard) methodology that is needed to solve these integer programs.

Paris Kanellakis's pioneering paper in 1990 provided a framework for constraint databases by combining concepts from constraint logic programming and relational databases. The principal idea is to generalize a tuple (or record) data type to a conjunction of constraints from an appropriate language; for example, order constraints or linear arithmetic constraints. Such a tuple can be seen as representing a large, possibly even infinite, set of points in a compact way (e.g., for spatial databases and GIS). Constraint databases have since become a very active area of database research.After a brief introduction to relational databases, we explain the semantics of constraint database relations and queries, providing complexity results for several specific constraint classes. We consider the various relational querying paradigms (declarative, procedural, and logic programming) and their reinterpretation in the presence of constraints as first-class data. We highlight the basic design principles for constraint databases, such as query closure and safety, efficiency of data representation and data access, and query optimization.We discuss Paris Kanellakis's more recent work, including work on indexing, and constraint query algebras, and survey other developments in the area (aggregation, complex objects, expressive power). The ultimate goal of Paris Kanellakis's research was to enable commercial-quality implementations of constraint databases. We look at some possible applications for constraint databases, and at the implementational efforts currently under way. We conclude by considering the issues and the challenges that lay ahead.

We survey three of Paris Kanellakis's contributions to the complexity-theoretic analysis of constructs in the design of programming languages. These are (1) his result that first-order unification is complete for polynomial time; (2) his contributions to the complexity analysis of type inference for polymorphicallytyped functional programming languages, which was proven to be complete for exponential time; and (3) his work on expressibility of simply typed lambda calculus when used as a functional database programming language. These research investigations are interrelated, emphasizing common themes and difficulties in the design of programming languages, with concrete implications that can be appreciated by language designers. First-order unification is a ubiquitous building block in implementations of sophisticated programming languages. It is, for example, the workhorse of logic programming engines, and the essential component of compile-time type analysis. The research on unification provided a secure foundation for understanding the complexity of automatic polymorphic type inference in functional languages such as ML and Haskell. Modern functional languages are based on the typed lambda calculus, so it is then natural to consider its computational expressiveness. We describe how the degree of higher-order functionality in simply typed terms can be related directly to well known complexity classes.