Principles and Practice of Constraint Programming — CP98

Constraint Programming (CP) has proven useful in several areas, and though the initial impetus came from logic programming frameworks like CLP and CCP, the use of CP and constraint solving is obtaining wider appeal. We suggest that the limiting features of traditional CP are a dependence on a (logic) language, the need for monotonicity in the constraint system, and, to a lesser extent, the lack of an independent mechanism for agents to specify concurrent interaction with constraint solversSome background and examples: the ILOG constraint libraries serve to provide constraint based search using a finite-domain solver for programs written in C++, and not a logic programming language. The Oz language is not rule-based; it uses a finite domain solver for search problems (though instead of backtracking, an encapsulated search mechanism is used). In addition, the concurrent part of Oz borrows from CCP in using entailment of term and feature constraints for synchronization. Further afield, the “glass box” approach to finite-domain constraint solving uses constraints on indexicals which are non-monotonic. Deductive and constraint databases define a store intensionally, but updates are non-monotonic. In shared-memory languages for parallel programming, the model is one of a global at store equipped with various synchronization primitives. Coordination based models like Actors/Blackboards/Linda use a structured global store and more sophisticated synchronization primitives on the store. In summary, the issues covered here include: a global store, logical structure vs local structure, monotonic vs non-monotonic operations, facilities for control and search. The point is, we need them allHere we introduce a model in which agents and constraint solvers interact. Details of agents are of no interest here; they may be written in any (sequential or concurrent) programming language. We employ a more pragmatic definition of constraint system, but more importantly, there is a framework for specifying how agents and solvers interact. What emerges is a general facility which has the traditional advantages of CP, and much more

It is well-known that there is a trade-off between the expressive power of a constraint language and the tractability of the problems it can express. But how can you determine the expressive power of a given constraint language, and how can you tell if problems expressed in that language are tractable? In this paper we discuss some general approaches to these questionsWe show that for languages over a finite domain the concept of an ‘indicator Problem’ gives a universal construction for any constraint within the expressive power of a language. We also discuss the fact that all known tractable languages over finite domains are characterised by the presence of a particular solution to a corresponding indicator problem, and raise the question of whether this is a universal property of tractable languages

It has long been accepted that dynamic variable ordering heuristics outperform static orderings. But just how dynamic are dynamic variable ordering heuristics? This paper examines the behaviour of a number of heuristics, and attempts to measure the entropy of the search process at different depths in the search tree

Constraint Handling Rules (CHR) is a high-level language for writing constraint solvers either from scratch or by modifying existing solvers. An important property of any constraint solver is confluence: The result of a computation should be independent from the order in which constraints arrive and in which rules are applied. In previous work [1], a sufficient and necessary condition for the confluence of terminating CHR programs was given by adapting and extending results about conditional term rewriting systems. In this paper we investigate so-called completion methods that make a non-confluent CHR program confluent by adding new rules. As it turns out, completion can also exhibit inconsistency of a CHR program. Moreover, as shown in this paper, completion can be used to define new constraints in terms of already existing constraints and to derive constraint solvers for them.

We study how constraint-based static analysis can be applied to the automated and systematic debugging of program errorsStrongly moding and constraint-based mode analysis are turning to play fundamental roles in debugging concurrent logic/constraint programs as well as in establishing the consistency of communication protocols and in optimization. Mode analysis of Moded Flat GHC is a constraint satisfaction problem with many simple mode constraints, and can be solved efficiently by unification over feature graphs. We have proposed a simple and efficient technique which, given a non-well-moded program, diagnoses the “reasons” of inconsistency by finding minimal inconsistent subsets of mode constraints. Since each constraint keeps track of the symbol occurrence in the program that imposed the constraint, a minimal subset also tells possible sources of program errors. The technique is quite general and can be used with other constraint-based frameworks such as strong typingBased on the above idea, we study the possibility of automated debugging in the absence of mode/type declarations. The mode constraints are usually imposed redundantly, and the constraints that are considered correct can be used for correcting wrong symbol occurrences found by the diagnosis. As long as bugs are near-misses, the automated debugger can propose a rather small number of alternatives that include the intended program. Search space is kept small because constraints effectively prune many irrelevant alternatives. The paper demonstrates the technique by way of examples

We use Q-matrices to efficiently solve incremental linear systems over IR, using integer computations. An algorithm optimized for the Q-pivot operation of Q-matrices is described, allowing a noticeable improvement in the efficiency of linear constraint solvers with infinite precision. We then present a coding of Q-matrices suitable for this algorithm and give some performance measurements.

The protein structure prediction problem is one of the most (if not the most) important problem in computational biology. This problem consists of finding the conformation of a protein (i.e., a sequence of amino-acids) with minimal energy. Because of the complexity of this problem, simplified models like Dill’s HP-lattice model [12] have become a major tool for investigating general properties of protein folding. Even for this simplified model, the structure prediction problem has been shown to be NP-complete [3, 5].We describe a constraint formulation of the HP-model structure prediction problem, present the basic constraints and search strategy. We then introduce a novel, general technique for excluding geometrical symmetries in constraint programming. To our knowledge, this is the first general and declarative technique for excluding symmetries in constraint programming that can be added to an existing implementation. Finally, we describe a new lower bound on the energy of an HP-protein. Both techniques yield an efficient pruning of the search tree.

This paper presents the results of a case study, concerning the propagation of a global disjunctive resource constraint, when the resource is over-loaded. The problem can be seen as a partial constraint satisfaction problem, in which either the resource constraint or the due dates of some jobs have to be violated. Global constraint propagation methods are introduced to efficiently deal with this situation. These methods are applied to a well-known operations research problem: minimizing the number of late jobs on a single machine, when jobs are subjected to release dates and due dates. Dominance criteria and a branch and bound procedure are developed for this problem. 960 instances are generated with respect to different characteristics (number of jobs, overload ratio, distribution of release dates, of due dates and of processing times). Instances with 60 jobs are solved in 23 seconds on average and 90% of the instances with 100 jobs are solved in less than 1 hour.

In practice, constraint satisfaction problems are often structured. By exploiting this structure, solving algorithms can make important gains in performance. In this paper, we focus on structured continuous CSPs defined by systems of equations. We use graph decomposition techniques to decompose the constraint graph into a directed acyclic graph of small blocks. We present new algorithms to solve decomposed problems which solve the blocks in partial order and perform intelligent backtracking when a block has no solutionFor under-constrained problems, the solution space can be explored by choosing some variables as input parameters. However, in this case, the decomposition is no longer unique and some choices lead to decompositions with smaller blocks than others. We present an algorithm for selecting the input parameters that lead to good decompositionsFirst experimental results indicate that, even on small problems, significant speedups can be obtained using these algorithms.

Constraint Violation Minimization Problems arise when dealing with over-constrained CSPs. Unfortunately, experiments and practice show that they quickly become too large and too difficult to be optimally solved. In this context, multiple methods (limited tree search, heuristic or stochastic local search) are available to produce non-optimal, but good quality solutions, and thus to provide the user with anytime upper bounds of the problem optimum. On the other hand, few methods are available to produce anytime lower bounds of this optimum. In this paper, we explore some ways of producing such bounds. All of them are algorithmic variants of a Branch and Bound search. More specifically, we show that a new algorithm, resulting from a combination of the Russian Doll Search and Iterative Deepening algorithms, clearly outperforms five known algorithms and allows high lower bounds to be rapidly produced

Constraint databases use constraints to model and query data. In particular, constraints allow a finite representation of infinite sets of relational tuples (also called generalized tuples). The choice of different logical theories to express constraints inside relational languages leads to the definition of constraint languages with different expressive power. Practical constraint database languages typically use linear constraints. This choice allows the use of efficient algorithms but, at the same time, some useful queries, needed by the considered application, may not be represented inside the resulting languages (for example, the convex hull cannot be computed [19]). These additional queries can only be modeled by changing the theory (thus, loosing the advantages of the linear theory), or extending the language, or using external functions. In this paper we consider the last approach and we propose an algebra and a calculus for constraint relational databases extended with external functions, formally proving their equivalence. In doing that, we use an approach similar to the one used by Klug to prove the equivalence between the relational algebra and the relational calculus extended with aggregate functions [14]. As far as we know, this is the first approach to introduce external functions in constraint query languages.

This paper investigates the relations among different partial consistencies which have been proposed for pruning the domains of the variables in constraint systems over the real numbers. We establish several properties of the filtering achieved by the algorithms based upon these partial consistencies. Especially, we prove that: 1)2B—Consistency (or Hull consistency) algorithms actually yield a weaker pruning than Box-consistency;2)3B—Consistency algorithms perform a stronger pruning than Box-consistency.This paper also provides an analysis of both the capabilities and the inherent limits of the filtering algorithms which achieve these partial consistencies.

This paper studies the application of interval analysis and consistency techniques to ordinary differential equations. It presents a unifying framework to extend traditional numerical techniques to intervals. In particular, it shows how to extend explicit methods to intervals. The paper also took a fresh look at the traditional problems encountered by interval techniques and studied how consistency techniques may help. It proposes to generalize interval techniques into a two-step process: a forward process that computes an enclosure and a backward process that reduces this enclosure. In addition, the paper studies how consistency techniques may help in improving the forward process and the wrapping effect.

During the evaluation of a constraint logic program, many local variables become inaccessible, or dead. In Prolog and other programming languages, the data bound to local variables can be removed automatically by garbage collection. The case of CLP is more complex, as the variables may be involved in several constraints. We can consider dead variables to be existentially quantified. Removing an existential variable from a set of constraints is then a problem of quantifier elimination, or projection. Eliminating variables not only allows recovery of space but also can decrease the cost of further consistency tests. Surprisingly, the existing systems do not exploit these advantages. Instead, the primary use of projection is as a mechanism for obtaining answer constraints. In this paper, we will give a general system architecture for automatic early projection and specify the heuristics for CLP(R) together with an in-situ removal method. We then show the effectiveness of early projection by applying it to some practical planning problems.

In this paper we describe a paradigm for content-focused matchmaking, based on a recently proposed model for constraint acquisition and satisfaction. Matchmaking agents are conceived as constraint-based solvers that interact with other, possibly human, agents (Customers). The Matchmaker provides potential solutions (“suggestions”) based on partial knowledge, while gaining further information about the problem itself from the other agent through the latter’s evaluation of these suggestions. The dialog between Matchmaker and Customer results in iterative improvement of solution quality, as demonstrated in simple simulations. We also show empirically that this paradigm supports “suggestion strategies” for finding acceptable solutions more efficiently or for increasing the amount of information obtained from the Customer. This work also indicates some ways in which the tradeoff between these two metrics for evaluating performance can be handled

In some recent works, a general framework for finite domains constraint satisfaction has been defined, where classical CSPs, fuzzy CSPs, weighted CSPs, partial CSPs and others can be easily cast. This framework, based on a semiring structure, allows, under certain conditions, to compute arc-consistency. Restricting to that case and integrating semiring-based constraint solving in the Constraint Logic Programming paradigm, we have implemented a generic language, clp(FD,S), for semiring-based constraint satisfaction. In this paper, we describe the kernel of the language: the SFD system and our implementation of clp(FD,S). We also give some performance results on various examples.

Information about the relative size of spatial regions is often easily accessible and, when combined with other types of spatial information, it can be practically very useful. In this paper we combine a simple framework for reasoning about qualitative size relations with the Region Connection Calculus RCC-8, a widely studied approach for qualitative spatial reasoning with topological relations. Reasoning about RCC-8 relations is NP-hard, but a large maximal tractable subclass of RCC-8 called H₈ was identified. Interestingly, any constraint in RCC-8 - H₈ can be consistently reduced to a constraint in Ĥ₈, when an appropriate size constraint between the spatial regions is supplied. We propose an O(n3) time path-consistency algorithm based on a novel technique for combining RCC-8 constraints and relative size constraints, where n is the number of spatial regions. We prove its correctness and completeness for deciding consistency when the input contains topological constraints in Ĥ₈. We also provide results on finding a consistent scenario in O(n3) time both for combined topological and relative size constraints, and for topological constraints alone. This is an O(n ₂ ) improvement over the known methods

Propagation based finite domain solvers provide a general mechanism for solving combinatorial problems. Different propagation methods can be used in conjunction by communicating through the domains of shared variables. The flexibility that this entails has been an important factor in the success of propagation based solving for solving hard combinatorial problems. In this paper we investigate how linear integer constraints should be represented in order that propagation can determine strong domain information. We identify two kinds of substitution which can improve propagation solvers, and can never weaken the domain information. This leads us to an alternate approach to propagation based solving where the form of constraints is modified by substitution as computation progresses. We compare and contrast a solver using substitution against an indexical based solver, the current method of choice for implementing propagation based constraint solvers, identifying the the relative advantages and disadvantages of the two approaches.

We are concerned with interval constraints: solving constraints among real unknowns in such a way that soundness is not affected by rounding errorsThe contraction operator for the constraint x +y = z can simply be expressed in terms of interval arithmetic. An attempt to use the analogous definition for x * y = z fails if the usual definitions of interval arithmetic are used. We propose an alternative to the interval arithmetic definition of interval division so that the two constraints can be handled in an analogous way. This leads to a unified treatment of both interval constraints and interval arithmetic that makes it easy to derive formulas for other constraint contraction operatorsWe present a theorem that justifies simulating interval arithmetic evaluation of complex expressions by means of constraint propagation. A naive implementation of this simulation is inefficient. We present a theorem that justifies what we call the totality optimization. It makes simulation of expression evaluation by means of constraint propagation as efficient as in interval arithmetic. It also speeds up the contraction operators for primitive constraints.

Finding good problem decompositions is crucial for solving large-scale key/lock configuration problems. We present a novel approach to problem decomposition where the detection of a subproblem hierarchy is formulated as a constraint satisfaction problem (CSP) on set variables. Primitive constraints on set variables such as an inverse and a union-over-set-constraint are used to formalize properties of trees and to ensure that solutions of these CSPs represent a tree. An objective for optimizing properties of the tree is presented as well. Experimental results from an industrial prototype are reported

The Constraint Hierarchy (CH) framework is used to tackle multiple criteria selection (MCS), consisting of a set of candidates and a set of, possibly competing, criteria for selecting the ”best“ candidate(s). In this paper, we identify aspects of the CH framework for further enancement so as to model and solve MCS problems more accurately. We propose the Fuzzy Constraint Hierarchies framework, which allows constraints to belong to, possibly, more than one level in a constraint hierarchy to a varying degree. We also propose to replace the standard equality relation = used in valuation comparators of the CH framework by the α-approximate equality relation =a(α) for providing more flexible control over the handling of valuations with close error values. These proposals result in three new classes of valuation comparators. Formal properties of the new comparators are given, wherever possible.

In this paper we will show how constraint solving methods can be applied for the recognition of buildings in aerial images. Object models are transformed to constraint representations which are matched against extracted image features. To cope with disturbances caused by occlusions and noise, we distinguish between the unobservability of a) relations between object parts and b) object parts themselves. Whereas other approaches for solving over-constrained problems suggest to reduce the relaxation of a variable to the relaxation of its incident constraints, we argue that both cases have to be treated separately. Information theory is applied to derive constraint weights on a probabilistic basis. We extend constraints and variables in a way which provides for an adequate integration of constraint violation and variable elimination on the one hand, and allows the determination of the maximum likelihood estimation for the matching between model and image on the other hand.

Constraint Programming is a technique of choice for solving hard combinatorial optimization problems. However, it is best used in conjunction with other optimization paradigms such as local search, yielding hybrid algorithms with constraints. Such combinations lack a language supporting an elegant description and retaining the original declarativity of Constraint Logic Programming. We propose a language, SALSA, dedicated to specifying (local, global or hybrid) search algorithms. We illustrate its use on a few examples from combinatorial optimization for which we specify complex optimization procedures with a few simple lines of code of high abstraction level. We report preliminary experiments showing that such a language can be implemented on top of CP systems, yielding a powerful environment for combinatorial optimization.

We study the experimental consequences of a recent theoretical result by Achlioptas et al. that shows that conventional models of random problems are trivially insoluble in the limit. We survey the literature to identify experimental studies that lie within the scope of this result. We then estimate theoretically and measure experimentally the size at which problems start to become trivially insoluble. Our results demonstrate that most (but not all) of these experimental studies are luckily unaffected by this result. We also study an alternative model of random problems that does not suffer from this asymptotic weakness. We show that, at a typical problem size used in experimental studies, this model looks similar to conventional models. Finally, we generalize this model so that we can independently adjust the constraint tightness and density

We describe an object-oriented constraint solving toolkit, QOCA, designed for interactive graphical applications. It has a simple yet powerful interface based on the metric space model for constraint manipulation. Currently QOCA supports linear arithmetic constraints and two different metrics: the square of the Euclidean distance and the Manhattan distance. It provides three solvers, all of which rely on keeping the constraints in solved form and relies on novel algorithms for efficient resolving of constraints during direct manipulation. We provide a thorough empirical evaluation of QOCA, both of the interface design and the speed of constraint solving.

In this paper we consider Datalog queries with linear constraints. We identify several syntactical subcases of Datalog queries with linear constraints, called safe queries, and show that the least model of safe Datalog queries with linear constraints can be evaluated bottomup in closed-form. These subcases include Datalog with only positive and upper-bound or only negative and lower bound constraints or only half-addition, upper and lower bound constraints. We also study other subcases where the recognition problem is decidable

This paper explores the performance of a new complete nonsystematic search algorithm learn-SAT on two types of 3-SAT problems, (i) an extended range of AIM problems [1] and (ii) structured unsolvable problems [2]. These are thought to present a difficult challenge for non-systematic search algorithms. They have been extensively used to study powerful special purpose SAT algorithms. We consider two of these, viz. the tableau-based algorithm of Bayardo & Schrag [2] and relsat. We compare their performance with that of learn-SAT, which is based on restart-repair and learning no-goods. Surprisingly, learn-SAT does very well. Sometimes it does much better than the other two algorithms; at other times they are broadly equivalent; and then there are some “anomalies”. One thing at least is clear, learn-SAT solves problems which many would predict are beyond its scope. The relative performance of the three algorithms generates several interesting questions. We point to some of them with a view to future research. The empirical paradigm in this paper reflect some of the views outlined by Mammen & Hogg [10].

This paper presents a robust approach to solve Hoist Scheduling Problems (HSPs) based on an integration of Constraint Logic Programming (CLP) and Mixed Integer Programming (MIP). By contrast with previous dedicated models and algorithms for solving classes of HSPs, we define only one model and run different solversThe robust approach is achieved by using a CLP formalism. We show that our models for different classes of industrial HSPs are all based on the same generic model. In our hybrid algorithm search is separated from the handling of constraints. Constraint handling is performed by constraint propagation and linear constraint solving. Search is applied by labelling of boolean and integer variablesComputational experience shows that the hybrid algorithm, combining CLP and MIP solvers, solves classes of HSPs which cannot be handled by previous dedicated algorithms. For example, the hybrid algorithm derives an optimal solution, and proves its optimality, for multiple-hoists scheduling problems.

We introduce a constraint system LC that handles arithmetic constraints over reals within the linear concurrent constraint programming (lcc) framework. This approach provides us with a general, extensible foundation for linear programming algorithm design that comes with a (linear) logical semantics. In particular, it allows us to build a ’glass-box’ version of the (constraint solver) simplex algorithm by defining (monotone) cc ask and tell agents over a higher-level constraint system as lcc(LC) programs. We illustrate at the same time the use of the lccframework as a non-trivial concurrent algorithm specification tool.

We use a local search method we term Large Neighbourhood Search (LNS) to solve vehicle routing problems. LNS is analogous to the shuffing technique of job-shop scheduling, and so meshes well with constraint programming technology. LNS explores a large neighbourhood of the current solution by selecting a number of “related” customer visits to remove from the set of planned routes, and re-inserting these visits using a constraint-based tree search. Unlike similar methods, we use Limited Discrepancy Search during the tree search to re-insert visits. We analyse the performance of our method on benchmark problems. We demonstrate that results produced are competitive with Operations Research meta-heuristic methods, indicating that constraint-based technology is directly applicable to vehicle routing problems

The multi-way dataflow constraint model allows a user to describe interactive applications whose consistency is maintained by a local propagation algorithm. Local propagation applies a sequence of methods that solve the constraints individually. The local aspect of this solving process makes this model sensitive to cycles in the constraint graph. We use a formalism which overcomes this major limitation by allowing the definition of general methods that can solve several constraints simultaneously. This paper presents an algorithm called General-PDOF to deal with these methods which has a polynomial worst case time complexity. This algorithm therefore has the potential to tackle numerous real-life applications where cycles make local propagation unfeasible. Especially, general methods can implement “ruler and compass” rules to solve geometric constraints.

An important extension of constraint technology involves problems that undergo changes that may invalidate the current solution. Previous work on dynamic problems sought methods for efficiently finding new solutions. We take a more proactive approach, exploring methods for finding solutions more likely to remain valid after changes that temporarily alter the set of valid assignments (stable solutions). To this end, we examine strategies for tracking changes in a problem and incorporating this information to guide search to solutions that are more likely to be stable. In this work search is carried out with a min-conflicts hill climbing procedure, and information about change is used to bias value selection, either by distorting the objective function or by imposing further criteria on selection. We study methods that track either value losses or constraint additions, and incorporate information about relative frequency of change into search. Our experiments show that these methods are generally effective in finding stable solutions, and in some cases handle the tradeof between solution stability and search efficiency quite well. In addition, we identify one condition in which these methods markedly reduce the effort to find a stable solution

Objective. In a faulty digital circuit, many (single) faulty gates may explain the observed findings. It may be not practical (e.g. in VLSI chips) to test points in the circuit other than their input and output bits, so constraint technology was used to obtain input patterns that identify single faulty gates. However, two alternative faulty gates often have a large number of test patterns, but only a few, if any, differentiate them. We focus on obtaining test patterns that discriminate alternative faulty gates. Technique. The technique of [2] to generate a test pattern for a faulty gate introduces new values, d and notd, and assigns d to the gate output. New truth tables cope with the new values, and the patterns generated force a d (or notd) to reach an output bitWe adapted the technique to differentiate two faulty gates, not both faulty. The output of a gate is either independent of the faulty state of both gates, or depends on the faulty state of one of the gates alone or depends on either faulty states. We denote this latter case as m-X, meaning that the gate output takes value X if both gates are normal and not X if any of the gates is faulty. Similarly, d1-X (d2-X) denotes the output of a gate that depends solely on the faulty state of gate g₁ (g₂) and takes value X if g₁ (g₂) is normal and not X if it is faulty. We developed truth tables to cope with these new values, which depend on whether the gate is one of the potentially faulty.

We introduce a new optimization method based on a Genetic Algorithm (GA) combined with Constraint Satisfaction Problem (CSP) techniques. The approach is designed for combinatorial problems whose search spaces are too large and/or objective functions too complex for usual CSP techniques and whose constraints are too complex for conventional genetic algorithm. The main idea is the handling of sub-domains of the CSP variables by the genetic algorithm. The population of the genetic algorithm is made up of strings of sub-domains whose adaptation are computed through the resolution of the corresponding ¤b-CSPs’ which are somehow much easier than the original problem. We provide basic and dedicated recombination and mutation operators with various degrees of robustness. The first set of experimentations adresses a naÏve formulation of a Vehicle Routing Problem (VRP). The results are quite encouraging as we outperform CSP techniques and genetic algorithm alone on these formulationsGenetic algorithms are well suited to the quick and global exploration of a large search space to optimize any objective function (even a “black box” one, i.e. no hypothesis is required on the function) and are able to provide several solutions of “good quality”.Constraints satisfaction techniques are fitted to highly constrained problems for which the exhaustive exploration of their search spaces are conceivable. Such a method provides naturally feasible solutionsWe suggest to take advantage of the two approaches by combining hybridizing them: use of constraint satisfaction to compute feasible solutions on a subspace of the search spaceuse of a genetic algorithm to explore the space formed by the set of these subspaces and perform the optimizationThe ratio ρ of the size of a subspace to the size of the whole search space is the essential parameter of the hybridization: one can continuously pass from a pure CSP search (ρ = 1) to a pure stochastic search (ρ = 0, i.e a subspace is reduced to a single value).

Classical constraint problems (CSPs) are a very expressive and natural formalism to specify many kinds of real-life problems. However, sometimes they are not very exible when trying to represent real-life scenarios where the knowledge is not completely available nor crisp. For this reason, many extensions of the classical CSP framework have been proposed in the literature: fuzzy, partial, probabilistic, hierarchical. More recently, all these extensions have been unified in a general framework [1], called SCSP, which uses a semiring to associate with each tuple of values for the variables of each constraint an appropriate “degree of preference”, which can also be interpreted as a cost, or an award, or othersSometimes, however, even SCSPs are not expressive enough, since one may know his/her preferences over some of the solutions but have no idea on how to code this knowledge into the SCSP. That is, one has a global idea about the goodness of a solution, but does not know the contribution of each single constraint to such a measure. In [2] this situation is addressed by using learning techniques based on gradient descent: it is assumed that the level of preference for some solutions (the examples) is known, and it is proposed to learn, from these examples, values to be associated with each constraint tuple, in a way that is compatible with the examplesHere we make the technique proposed in [2] concrete: we identify its features, and we show the results of several experiments run by choosing various values of these features.

Extended Abstract. In this paper we develop and analyse CSP-based procedures for solving scheduling problems with metric temporal constraints (e.g. jobs’ deadlines or separation constraints between couple of consecutive activities in a job) and multiple capacitated resources, referred to formally as the Multiple Capacitated Metric Scheduling Problem (MCM-SP). This work follows two different solution approaches used to identify resource capacity conflicts. (1) Proffle-based approaches (e.g. [1]) - They consist of characterizing a resource demand as a function of time, identifying periods of overallocation in this demand proffle, and incrementally performing “eveling actions” to (hopefully) ensure that resource usage peaks fall below the total capacity of the resource. (2) Clique-based approaches [3, 2] - Given a current schedule, this approach builds up a conflicts graph whose nodes are activities and whose edges represent overlapping resource capacity requests of the connected activities. Fully connected subgraphs (cliques) are identiffed and if the number of nodes in the clique is greater than resource capacity a conflict is detectedClique-based approaches perform more global analysis and offer greater accuracy in conflict detection in comparison with local pairwise proffle-based analysis, but at a potentially much higher computational cost. In a previous paper [1], several proffle-based solution procedures were developed and evaluated (in particular the ESTA algorithm), some of them descending from an approach proposed in the planning literature.

In order to improve the deductive power of ffinite domain constraint solvers usually redundant and global constraints are added to the constraint system. The objective of this work [2] is to develop a new constraint solving scheme designed as an extension of a classical arc-consistency algorithm. Associated to a declarative language, it allows the user to implement his own global relations without the need of manipulating internal structures of the solver or modifying in depth the original model of the studied problem. This system relies on two new structures: index-sets and constraint templates. The former consist in sets of integers used as indices over tables. They collect variables sharing some properties (for instance tasks in a scheduling problem assigned to the same machine). The latter are descriptions of constraints that must be applied (possibly) over selected sets of variables (for instance the fact that a set of tasks must be scheduled before another set). Both, set-index and constraint template deffnitions are evaluated dynamically and depend on the variables’ domains. Indeed, the new constraints are automatically generated by the constraint solver based on the set contents and variable domain values. The index-set and constraint deffinition language uses a mathematic style notation. The deffnitions are compiled to the solver representation which can be directly handled by the propagation mechanism. This organisation guarantees a high level of efficiency.

In this research, we study a transportation problem which is concerned with vehicle routing and driver scheduling for a bus station. The problem requires drivers to provide pick-up and delivery services to customers, subject to vehicle capacity limitation and time constraints. The objective is to efficiently schedule the fleet of vehicles for customer demand so as to reduce costs.

CLP systems diffr signicantly in the efficiency of their execution so that a wrong choice for an application may be disastrous relative to the necessary performance. Thus, efficiency should be taken into account when choosing the best system for a particular application. In spite of this, there appeared to be no impartial efficiency information concerning CLP systems. In the research described here1, we have compared, as fairly as possible, eight systems and provided detailed results concerning their speed and robustness

A well-studied problem in the electric power industry is that of optimally scheduling preventative maintenance of power generating units within a power plant [1, 3]. The general purpose of determining a maintenance schedule is to determine the duration and sequence of outages of power generating units over a given time period, while minimizing operating and maintenance costs over the planning period, subject to various constraints. We show how maintenance scheduling can be cast as a constraint satisfaction problem and used to define the structure of randomly generated non-binary CSPs. These random problem instances are then used to evaluate several previously studied backtracking-based algorithms, including backjumping and dynamic variable ordering augmented with constraint learning and look-ahead value ordering [2].We also define and report on a new ⩼erative learning’ algorithm which solves maintenance scheduling problems in the following manner. In order to find an optimal schedule, the algorithm solves a series of CSPs with successively tighter cost-bound constraints. For the solution of each problem in the series constraint learning is applied, which involves recording additional constraints that are uncovered during search. However, instead of solving each problem in the series independently, after a problem is solved successfully with a certain cost-bound, the new constraints recorded by learning are used in subsequent attempts to find a schedule with a lower cost-bound. We show empirically that on a class of randomly generated maintenance scheduling problems iterative learning reduces the time required to find a good schedule.

This abstract gives a brief overview of our work presented in [3]. Our approach for characterising the run-time behaviour of stochastic local search (SLS) algorithms is based on a novel and adequate empirical methodology for evaluating SLS algorithms first used in [1] and presented in more detail in [2]: Instead of collecting simple statistics averaged over a large number of runs and large sets of instances, we are estimating and functionally characterising run-time distributions on single instances. The data thus obtained provides the basis for formulating hypotheses on the behaviour of SLS algorithms on problem distributions and across several domains. These hypotheses are then tested using standard statistical methodology like parameter estimation methods and goodness-of-fit testsUsing this methodology, we obtain some novel and surprisingly general empirical results concerning the run-time behaviour of the most popular SLS algorithms for SAT and CSP. Our main result establishes that on hard instances from a variety of randomised problem classes (Random-3-SAT at the phase transition) as well as encoded problems from other domains (like blocks world planning or graph colouring), the run-time behaviour of some of the most powerful SLS algorithms for both SAT and CSP can be characterised by exponential distributions. This result has a number of significant implications, the most interesting of which might be the fact that SLS algorithms displaying this type of behaviour can be easily parallelised with optimal speedup, or, equivalently, their performance cannot be improved by using restart.

The constraint paradigm provides powerful concepts to represent and solve different kinds of planning problems. Typically a large and conflicting set of restrictions, objectives and preferences has to be considered for real planning problems. We introduce a unified formalism - called Petri decision nets - for representation and implementation of complex CSP solution algorithms. The formalism enables the consideration of the problem structure as well as given objectives and the usage of problem specific heuristics or expert knowledge. It is based on the fundamental assumption that designing CSP solution algorithms means designing decision networks.

As constraint logic programming matures and larger applications are built, an increased need arises for advanced development and debugging environments. Assertions are linguistic constructions which allow expressing properties of programs. Classical examples of assertions are type declarations. However, herein we are interested in supporting a more general setting [3, 1] in which, on one hand assertions can be of a more general nature, including properties which are statically undecidable, and, on the other, only a small number of assertions may be present in the program, i.e., the assertions are optional. In particular, we do not wish to limit the programming language or the language of assertions unnecessarily in order to make the assertions statically decidable. Consequently, the proposed framework needs to deal throughout with approximations [2].The framework we propose (see [4]) is aimed at detecting deviations of the program behavior (symptoms) w.r.t. the given assertions, either statically (at compile-time) or dynamically (at run-time). Our approach is strongly motivated by the availability of analyzers for constraint logic programs which can statically infer a wide range of properties, from types to determinacy or terminationWe provide techniques for using information from global analysis both to detect at compile-time assertions which do not hold (i.e., static symptoms) and assertions which hold for all possible executions (i.e., statically proved assertions).

Constraint propagation algorithms present inherent parallelism. Each constraint behaves as a concurrent process triggered by changes in the store of variables, updating the store in its turn. There is an inherent sequentiality, as well, since a constraint must be executed only as the consequence of a previous execution of another constraint. We have developed different parallel execution models of constraint propagation for MIMD distributed memory machines. We have adopted the indexical scheme, an adequate approach to achieve consistency for n-ary constraints. The proposed models arise from two techniques, dynamic and static, for scheduling constraint executions (assignment of constraint executions to processing elements). In the static scheduling models the constraint graph is divided into N partitions, which are executed in parallel on N processors. We have investigated an important issue affecting performance, the criterion to establish the graph partition in order to balance the run-time workload. In the dynamic scheduling models, any processor can execute any constraint, improving the workload balance. However, a coordination mechanism is required to ensure a sound order in the execution of constraints. We have designed coordination mechanisms for both centralised and distributed control schemes. Several parallel processing methods for solving Constraint Satisfaction Problems have been proposed. [1] and [3] must be remarked in relation with our work.

The assembly problem is the spatial joining of separate rigid bodies within a CAD/CAM-system. The solution to the assembly does not only need to contain one consistent instantiation, but also qualitative information. In particular, this covers the localization of redundancy and remaining degrees of freedom in the mechanism. Although it is natural to model the assembly as a constraint satisfaction problem (CSP), solving remains a difficult taskIn general, a CSP can be attacked by two strategies: consistency enforcement and search. Algorithms work best if they combine these strategies in a clever way. When modeling the assembly problem as a CSP, one is confronted with two special conditions. First, the variable domains are continuous. Second, constraints are not arbitrary, but are conjunctions of instantiated predefined constraint types. Thus, search is not possible because of the continuous domains and numeric iterative or interval approaches deliver no information on degrees of freedom and redundancy. Therefore, pure consistency enforcement, which has many drawbacks in general CSPs, is the best choiceIn this poster, we discuss how consistency can be enforced in assembly problems while preserving redundancy information. For this purpose, we introduce k-block-consistency (k-BC), which only requires support for tuples of the same biconnected component (block).

The solution of Dynamic Constraint Satisfaction Problems (DCSPs) in Constraint Logic Programming (CLP) basically requires a solution of dynamically changing systems of syntactical equations over the rational treesFor instance, let U; V;X; Y;Z be variables, c be a constant, f; g be function symbols and fX: = f(X; Y ); f(Z; c): = X;U: = V; V: = U; g(c): = Zg be a set of syntactical equations. Suppose that all but the last equations are considered and the rational solved form X: = f(X; Y ); Z: = f(X; Y ); Y: = c; U: = V: is calculated. Given the last equation, inconsistency is detected, because the two equations g(c): = Z and Z: = f(X; Y ) are unsolvable. For an adaptation of the rational solved form and the decision about the consistency after the deletion of the equation f(Z; c): = X in CLP we have the opportunity to backtrack to the first equation X: = f(X; Y ) and then recalculate the solution. A closer examination shows that backtracking is not really necessary. Only the bindings Z: = f(X; Y ) and Y: = c depend on the deleted equation. The binding U: = V and the equation V: = U are completely independent. Thus, for an adaptation it is sufficient to keep the bindings X = f(X; Y ); U: = V and reconsider the equation g(c): = ZBased on this deeper understanding we developed an unification algorithm, which uses truth maintenance techniques to maintain a solved form of a set of equations over the rational trees.

Planning of local wireless communication networks is about installing base stations (small radio transmitters) to provide wireless devices with strong enough signals. POPULAR is an advanced industrial prototype that allows to compute the minimal number of base stations and their location given a blue-print of the installation site and information about the materials used for walls and ceilings. It does so by simulating the propagation of radio-waves using ray tracing and by subsequent optimization of the number of base stations needed to cover the whole building. Taking advantage of state-of-the-art techniques for programmable application-oriented constraint solving, POPULAR is among thefirst practical tools that can optimally plan wireless communication networks