The competitors are mainly

Most of the discussion on CLP's Characterization in this document will be related to its comparison with Operations Research. A short description of Simulated Annealing and a comparison with Constraint Solving can be found in the Review by J.-Y. Cras [Cras Review 93]. The main idea is that Simulated Annealing addresses large, weakly constrained problems, while Constraint Solving fits well for tightly constrained problems. See also the experience of Renault on Car sequencing [Renault CarSeq 92; CHIP CarSeq 88].

5.2 First Problem and Context Description

Any attempt to characterize the problem and the methods apt to solve it presupposes at least some informal description. The following framework is based on that given in the first methodology report [Bull CHIC 92]. It consists in

• Problem Context and Environment Description, which should include
  - input / output conditions,
  - description of the process to model (whenever it applies),
  - objective to be fulfilled,
  - classification of the problem, whenever it exists,
  - quantitative hints: size of data, required performance,
  - possibilities of relaxing the problem ( e.g. in scheduling contexts, using third party production or relaxing due-dates).

• Historical data description, which consists of
  - previous attempts to solve the problem,
  - how and why they proved unsatisfactory.

• First Problem Model, which should define
  - entities to be considered,
  - internal relations they obey,
  - objective function and/or `soft' (relaxable) constraints.

5.3 CLP vs. competitors. External qualification criteria

Knowledge about the existence or absence of an OR (or other well-known) approach to solve similar problems is of utmost importance. Renault [Renault CHIC 93] suggests to take as basic criteria:
- whether the problem fits or not an existing OR model - in particular whether it can be linearized - or a simulated annealing model,
- the size of the problem,
with the following conclusions:

• If the problem fits a model without major distortion and is of reasonable size, then use the existing model (OR algorithms are often polynomial, whereas in CLP, though propagation is polynomial, enumeration is in general exponential). This is particularly true if the problem is a linear problem with continuous variables. Then, the algorithms (Simplex or other) implemented in Linear Programming packages will solve the problem even for sizeable data. If the problem is linear but with integer variables, Mixed Integer-Linear packages will allow to reach sizes up to a few hundred integer variables (but this is not completely predictable).
  Bull reported in CHIC on work done to integrate a transportation algorithm inside Charme, to solve a particular problem for which the required performance level had not been reached with Charme alone. The algorithm was already incremental and reasonably extensible. Looking back on it, the conclusion of the Charme Object team is that transportation problems are, actually, very well handled by such algorithms alone, without CLP's intervention.
• If it fits a model but is too large ( e.g. if it is a mixed integer-linear problem with more than a few hundred integer variables), then one should turn to heuristic search (and a global optimum, if ever considered, is not reachable); CLP will be a better framework than OR, for
  - it can much better exploit specific knowledge,
  - heuristics work very well with constraints.
• If one does not know about any available model, which is quite a common case, then one does not even know the relationship between the number of constraints and the problem complexity and one has to prototype; then CLP is the tool, for
  - it is declarative by nature (this is particularly relevant if the constraints change frequently or if new constraints are added often, or if the problem is ill- or under-specified),
  - the user does not have to implement a search technique (backtracking and logic variables are built-in features, as well as standard heuristics),
  - not only linear constraints can be allowed for,
  - it can be checked out whether new constraints actually increase or decrease the size of the search space.

5.4 Relevant problem features

5.4.1 Locality and heterogeneity

According to [Bull CHIC 92], one has to distinguish between:
global vs. local constraints,
homogeneous vs. heterogeneous constraints.

CLP is a likely candidate for heterogeneous problems; it is not a likely candidate for homogeneous problems where a global object can be identified ( e.g. a graph). Often, indeed, in that case, some OR algorithm already exists and will do the job an order of magnitude more efficiently than local constraints propagation, typical of CLP. It is worth noting that the level of globality/homogeneity of the problem is (in a quite informal way) reflected by the size of the description.

See the long description required for the Dassault scheduling problem, a quite heterogeneous problem (it has geometrical and temporal aspects) with constraints depending on the particular work station.

5.4.2 Pruning power of the constraints

In the first methodology report [Bull CHIC 92], a set of concepts is defined in order to establish the notion of solution density. The search space is defined by structural constraints. The solution space is defined by specific constraints. The solution density is the density of the solution space within the search space. It needs to be sufficiently low for CLP to be a candidate. Pure optimization problems, e.g. , are not likely to be handled by CLP.

But these notions appear extremely hard, if not impossible, to quantify. On the other hand, a mere density criterion would not be enough. If a problem, indeed, has got hard constraints, but a huge search space and very few solutions (a large problem with a very low solution density), this may be very bad even for CLP. The situation actually depends on the pruning power of the available constraint implementations (which is often difficult to predict). It has also some relationship with the number of variables - few variables and a lot of constraints seems to be a good case for CLP - and with the hard vs. soft character of these constraints: the harder the constraints, the better for CLP. A problem featuring mostly preferences is bad for CLP: the user would like these `constraints' to be satisfied, but each of them in isolation can be violated and it is accepted that a certain number of them be violated in the solution. Turning these preferences into a linear combination of some criteria is in general not a very good idea, unless the problem can be completely linearized and a linear solver used. Complex cost functions, indeed, usually lead to very poor propagation with the Finite domains. Some possibilities still exist to handle `soft' constraints (see ), but the general idea is that if the problem is dominated by the preference aspect, then CLP is in general not the right technology.

To sum up, a `good' CLP problem would be characterized by

• relatively few variables,
• lots of hard constraints, that propagate well (or, more precisely: whose implementations propagate well),
• few soft constraints.

5.4.3 System evolution and interactivity

This is another perspective, also mentioned in [Bull CHIC 92]. CLP is basically adequate for systems

• interactive (see System Specification - Communication Model, ),
• likely to evolve , requiring to be frequently maintained.

5.5 A characterization procedure

The need for a more global expression, together with increased performance, led e.g. to the development of the disjunctive constraint at ECRC, now available in ECLiPSe [ECRC Disjunctive 93], as well as of the disjunctive constraint in Charme Object [Bull Disjunctive 94 ] and the cumulative constraint in CHIP4 [Cosytec JFPL 92]).

In the Car Sequencing problem, as handled in the original CHIP [CHIP CarSeq 88], the sequencing constraints apply to 0/1 variables representing the absence or presence of options on the cars. In the Charme version of this program, this is replaced by global distribute constraints [Bull CharmeObject 94].

The Warehouse Location problem [CHIP Warehouse 89] is an example of using element/3 constraints to express the cost for each customer as a function of the warehouse responsible of delivering goods to this customer. With Integer Programming, 0/1 variables would have to be used. See the original paper for the resulting reduction of the search space size.

See the use of element constraints to express finite mappings in the Braghenti loom scheduling application [ECRC Braghenti 94].

The Dassault Planning Program features a number of 0/1 variables, that are explicitly instantiated in the labelling procedure, viz. one variable per aircraft, representing the decision to change or not the production rate when this aircraft is manufactured, and, if yes, to increase or decrease it. This leads to poor propagation. A constraint model focused on `where to change the rate' rather than `change or not at each a priori possible point' might yield better results.

In [Bull Sets&Graphs 94: 4.3] an example is given of how an array of 0/1 variables can be efficiently replaced by set constraints to solve a bin-packing problem (`packing' songs into records). Note that set partitioning constraints are global constraints.

In the car sequencing problem [CHIP CarSeq 88], classes of cars are considered instead of individual cars, in order to remove symmetries.

8.2.2 Generation strategies

8.2.2.1 Non-completeness of the search

If the search space is too large, one has to accept the non-completeness of the search. According to the Charme Object team, it is probably better to leave only a few (significant) possibilities at each node of the search tree down to a certain depth, cut the rest, but leave the system run through the whole reduced tree, than e.g. leav e all possibilities but impose a time-out. In other words, it might be better completely running through a less `dense' search tree than having an exhaustive search on an very local part of the initial search tree.

Thus, for many disjunctive problems, it is probably a good approach to

• forget about global optima (which, anyway, often lack robustness),
• put important choices at the beginning,
• avoid backtracking on the rest.

A first step taken in the ECRC handling of the Braghenti problem was to give up with finding a global optimum and to move to heuristic search [ECRC Braghenti 94].

In MADE, the Dassault team has adopted a strategy which consists in a non deterministic task assignment in the bottleneck resource, but a deterministic assignment in the other work stations. This, in general, suppresses potential solution, but the search space is so large that backtracking on secondary aspects should at any rate be avoided.

8.2.2.2 Significant choices

In scheduling problems, significant choices are e.g.

• ordering pairs of disjunctive tasks,
• selecting the next task to place,
  

For scheduling problems, e.g. , this may mean to have as basic choice either `what order to impose on heuristically chosen pairs of tasks', or `what task to consider to put next', rather than `what value to try next for the currently considered task' (which most of the time leads to absolutely irrelevant backtracking).

With dichotomic labelling, any failure occurring when a domain is split discards a whole half of the domain and the system directly backtracks to the other half. This usually gives good results for problems like cutting stock [CHIP CuttingStock 88] or placement problems (see, e.g. , the part geometrical arrangement module of the Dassault scheduling application [Dassault PAP 94; CHIC 95]).

8.2.3 Soft constraints

8.2.3.1 Soft constraints as objective functions

The issue of soft constraints was already mentioned in Problem Characterization . Preferences can in principle be turned into linear combinations of the criteria and the initial problem recast into the problem of optimizing this cost function. Assuming this is meaningful (which is often questionable), either the problem is completely linear and, then, the Linear Solver or an OR linear package will be appropriate provided the problem is not too large, or the problem features a number of discontinuous aspects, like disjunctions. In this latter case, the Finite Domains are in principle appropriate, but a complex cost constraint leads to very poor propagation and this method is not to be recommended.

Here lies a possible explanation to difficulties encountered by Dassault on their planning application. The problem, indeed features a very high solution density and was initially specified as an optimization one. Though solutions get scarcer when stringer cost bounds are set in the course of the B&B optimization, this, unfortunately, cannot be efficiently exploited by the solver due to the additive structure of the cost function and the weakness of the underlying constraint model.

8.2.3.2 Use of meta-constraints

In Charme Object, to each constraint is associated a Boolean variable representing its truth value and, thus, meta-constraints can be expressed [Bull CharmeObject 94]. Therefore, it is theoretically possible to optimize, e.g. , a linear combination of constraint truth values, as a means of achieving a maximum preference. This process may not be very efficient, but experience is so far too limited to allow definitive conclusions.

8.2.3.3 Heuristics

Soft constraints can sometimes be allowed for by adequate heuristic methods in the enumeration procedure. The idea is to use domain-dependent knowledge to design strategies apt to ensure `good' first solution, with respect to user preferences.

In the MADE system, strategies based on a classical Bin-Packing heuristic methods, First Fit Decreasing, are used to produce compact schedule, satisfactory with respect to resource utilization (soft) constraints expressed by the end-user.

8.2.3.4 Hard constraint derivation

Hard constraints can be derived from the soft ones to help to prune the search tree. Often, simple and strong cost constraints can be designed, which do not exactly match the user's criteria, but will lead to `good' results and allow efficient pruning of the search space. This issue will be discussed in more detail below (8.2.4 ).

8.2.3.5 Semi-automatic systems

Finally, it is always possible to design a semi-automatic system, with which the user will be able to express his preferences during the construction of the solution. This may mean reconsidering the Communication Model in the System Specification.

The Renault constraint spreadsheet paradigm implemented in their Short-Term Production application [Renault IJCAI 94; Renault STP 92] is an example of that.

According to the Dassault team, when designing an interactive system, one should clearly distinguish between cases when

• the end-user is an expert in the process of constructing solutions, e.g. a planning expert: then, low level interactions can be allowed, up to a full graphical construction of the solutions;
• the end-user is an expert of the domain, not of the process of building solutions, e.g. a workshop foreman: then, only high level interactions can be safely allowed.

The Dassault assembly line application is an instance of highly interactive system aimed at users who are experts in the tasks to be performed on the assembly line, not in the process of building schedules. Only high level and global actions are allowed, like incrementally setting subsets of the constraints (see above , Handling Constraint Failure) and modifying the related parameters to express desired tendencies ( e.g. , given a solution, locally modify the maximum manpower available in order to get a smoother solution at the next run).

8.2.4 Costs

Problem modelling often exhibits several kinds of cost factors. It is important to see which costs can efficiently be exploited during the search and which ones are merely results to be reported to the user as indicators.

A maximum acceptable delay may not exist as a hard limit (increasing the delay may just have increasing `costs' as a consequence), but fixing an upper bound helps the search.

The sum of delays in job shop scheduling is both non-linear (one cannot use the linear solver) and a complex additive cost (a sum of a great number of elementary costs). This is disastrous when used as a constraint or an objective function with the FD solver. It may be worth trying to replace such a criterion by the maximum delay criterion.

The maximum end date in job shop scheduling has no particular meaning for the user (new orders will be issued anyway, unlike in the case of project planning), but, in a B & B optimization with finite domains, it is a powerful constraint for the search of compact solution (which are, as such, satisfactory for the user though the end-date indicator is not relevant for him).

8.3 Prototyping in CLP

8.3.1 CLP as a Prototyping Tool

Whenever

• the problem is complex,
• the specifications are vague,
• the technology to be applied is not clear,

• the problem properties,
• the user requirements.

• declarativity, which allows modifiability,
• efficiency, which allows representativity of the prototypes in terms of size,
• in languages like ECLiPSe or CHIP in particular, close integration of high level graphical languages, which allows representativity of the prototypes in terms of user functionalities.

8.3.2 Features of the first prototypes

The following features of the first prototypes are important for the quality of further development:

• full declarativity,
• maximal degree of generality,
• no `tricky' use of powerful constructs,
• demonstration of a significant part of both problem resolution and the man-machine interface,
• handling of real data.

8.3.3 Discovering the real complexity. Caveat

• the problem is theoretically less hard, e.g. polynomial,
• but, still, practically very complex, e.g. if the degree and/or coefficients of the polynomial are large numbers.

8.3.4 Subproblems

One should prototype first the most constrained subproblems [Bull CHIC 92]. If they are feasible, the whole problem should be feasible. Strongly coupled subproblems should be handled as a whole and one should not impose too early a decomposition to the problem in the Problem Modelling phase. That, indeed, might jeopardize `transversal' propagations that could help to solve locally `stuck' situations. One should rather try and keep a global approach to the problem. There are, of course, quantitative limits (like the number of constraints that can be set up).

The Dassault scheduling application features both part-grouping and temporal constraints. Due to quantitative limits and the predominance of disjunctive constraints, it was impossible to solve the problem as a whole. The choice that was initially made was to first solve the part-grouping subproblem, then the temporal one. This proved computationall y feasible, but appeared to be too restrictive. In the MADE system, the successor of the first prototype, the part-grouping constraints are partly pre-solved (partial part aggregation), then a tentative schedule is produced, then the part-grouping constraints are completely taken into account and, finally, a definitive schedule is produced for the definitive batches.

It may happen on the contrary that a problem is initially stated as global, but can eventually be split into independent subproblems.

Bull had a manpower assignment application where the problem was presented as global by the client. But this problem eventually proved to be composed of two totally decoupled subproblems, concerning two distinct subsets of the personnel, with distinct activities, performing unrelated tasks, the only link between them being that they belong to the same company.

8.3.5 Real data

It is extremely important to handle real data very early in the prototyping process, in order

• to handle from the beginning the right data formats,
• to detect in an early stage of the project possibly crucial features or peculiarities of the data; this, in particular, may have an impact on the complexity of the problem (make it harder or simpler than had been expected).

Temporal granularity in scheduling problems is an example: only real data can show what the required level of temporal precision really is.

8.3.6 Assessing the practical complexity

Some recommendations for practical measure of complexity:

• Frequently compute the exponential complexity factor. An exponential complexity has, indeed, to be assumed (propagation is polynomial, but enumeration is exponential). If T(N) is the execution time for a problem of size N , and DN any variation in the problem size, the exponential complexity factor is the quantity T(N+DN) / T(N) , which should be a function of DN only.
• Extrapolate to larger size data.
• Match them with the initial expectations.
• Check the sensitivity to particular data sets for a given size.

8.3.7 Debugging

Debugging is greatly eased when the kind of modular and incremental methods of setting up constraints, mentioned in , are implemented. The need of explaining a failure during development bears, indeed, a lot of similarity with the need of having the end-user understand the reason why the system does not find any solution. Even for the developer, implementation of such method may be necessary for the understanding of the system's results.

`Over-using' powerful built-ins may make things harder to debug: refrain from using constraints or predefined heuristics, e.g. , when simple computations or sorting procedures can do the job.

A mistake done by the Dassault team in one of their applications consisted of dynamically choosing the smallest of a set of instantiated values using the variable choice heuristic method `smallest' of CHIPv4, instead of a static sort! Not only was this definitely inefficient, but it was also simply wrong, for the heuristic method picks up integers randomly !

Inconsistency in the data is a common source of trouble. When possible, it may be interesting to have simple ad-hoc procedures to detect major inconsistencies, before running the main system.

In their Time-tabling application, the Charme Object team perform some pre-processing to detect `standard' causes of inconsistency in the data.

Another interesting approach consists in focusing on key variables and monitoring their changes (in the FD). This can be achieved by daemons set on the relevant domain changes. A dynamic graphical interface , allowing to visually achieve this kind of monitoring, is usually of great help in the development process. Tools for that purpose have been developed in CHIC [ICL Tools 94], based on ECLiPSe suspension mechanisms [ECRC ECLiPSe 94] .

8.3.8 End-user strategies

If the system end-user has got a strategy for solving the problem, it may be useful to have the system provide his solution as reference solution, at least in the prototyping phase, instead of ignoring it. In certain cases, this strategy, or parts of it, may prove adequate for the constraint system. In addition, it has to be shown that the solutions provided by the system are at least as good as those the user would find using his own methods. This is a discipline for the developer and a condition of acceptance of the system by the user.

8.3.9 Interfaces and integration

CLP languages like ECLiPSe or CHIP are complete languages, in the sense that

• they are are based on a logical language in which (almost) everything can be expressed,
• they have got closely integrated high level graphical languages.

The COCA system at Dassault is fully implemented in CHIP. This appears to be a right choice, since the system is relatively autonomous and its users are not accustomed to a particular interaction style with computer systems.

In contrast, the tools developed at Renault are integrated in a wider environment and mix constraint-based programs with other resolution techniques. Therefore, the philosophy adopted for these development is that of libraries of tools and a C/C++ `glue'.

Contents

9 Constraint Optimization and Definitive Implementation

9.1 Improving performance

This section about Constraint Optimization and Definitive Implementation deals with Performance improvement, either at an advanced prototyping stage, or for the definitive implementation. It is completely specific to CLP. The following issues and recommendations basically come from the first methodology report [Bull CHIC 92]. The discussions concerning structural constraints, application-dependent knowledge and practical complexity are general to CLP, but the rest of the section is specific to the Finite Domains.

9.2 Structural constraints

Implementation of structural constraints can be performed

• in CLP for small search spaces,
• by pre-processing for medium-sized cases (by a priori filtering the set of potential solution tuples),
• using an incremental specialized solver for large-scaled cases.

For a manpower assignment problem, Bull has used a priori filtering of the candidate tuples through rules. According to the Charme Object team, this may be simply a sign that the constraints are not powerful enough. Anyway, with CLP systems provided in the form of C++ libraries, like Charme Object, the very notion of preprocessing tends to disappear, for all treatments are performed using the same language.

See Bull's experience of integrating a transportation algorithm with Charme.

9.3 Operational behaviour of constraints

The operational behaviour of constraints should be studied in terms of

• information grain, bearing in mind that the finer the information deduced by the constraints, the slower they are likely to be, and `the slowest horse determines the speed';
• directionality of deduction: identify mainstreams or gaps.

An early discussion in CHIC was about the usefulness of an extended element constraint, in particular for scheduling problems. Having such a constraint in the CHIC platform was then a requirement of Dassault. Charme already featured an implementation of this constraint. The problem is the following: when used for scheduling problems, extended element may deduce information about holes in the domains, but this will not be used by arithmetic constraints; one should then decide whether a restricted version of extended element should be designed, either as a built-in or a user-constraint (see below), or whether local saturation e.g. should be applied to arithmetic constraints, so that they really take hole information into consideration. The practical answer in the Charme implementation was to `simulate' the holes by daemons: the holes are not propagated when they are created, but only when one of their bounds is reached by a domain bound. Dassault eventually applied user-defined conditional constraints to achieve a similar behaviour on pairwise disjunctive constraints and dropped their requirement of a powerful extended element .

In general, at this implementation level (not at the modelling/prototyping level), one should use powerful constraints only when their expressive power and inference capacity are actually required, and simpler constraints should always be preferred to complex ones when they allow the same deductions.

For instance, X + Y + Z #<= 1 is better than atmost(1, [X, Y, Z], 1) .

In Charme (using an ECLiPSe-like syntax)
[X, Y, Z] :: 1..3,
alldifferent([X, Y, Z])
is better than distribute(3, [X, Y, Z], [1, 2, 3], [1, 1, 1]) ( i. e. `distribute 3 of the variables X, Y, Z, onto values 1, 2, 3, each value being taken once').

Issues concerning the directionality of deduction are also interesting. While in principle constraints are completely adirectional, in most cases a mainstream of information propagation may be detected in a running program. If, for instance, in a constraint relating A and B, one observes that 90% of the information comes from changes in the domain of A and results in modifications in the domain of B, it is a natural idea to favour the mainstream by writing a restricted version of the constraint that works in one direction only. Once again, powerful constraints should be used only when necessary.

An arg(N, T, V) delayed on N is better than element(N, L, V) if the main propagation is from N , when it gets instantiated, to V.

On the other hand, when gaps are detected in the propagation mainstreams, redundant (surrogate) constraints can be introduced (only) as a means of filling these gaps. (Note that this applies to finite domains only . When using the Linear Solver, on the contrary, redundant constraints are a burden for the system and should be avoided. Note also that `redundant' refers to the logical aspect - the constraint being logically implied by the others is, in that sense, unnecessary -, whereas `surrogate' refers to the procedural aspect - the constraint performs actions that other cannot.)

An extremely simple example is the following, in the Finite Domains
[A, B, C] :: 0..100,
A + B #= 10,
A + B + C #= 11.
is not enough for C = 1 to be deduced. One should write, e.g.
[A, B, AB, C] :: 0..100,
AB #= A + B,
AB #= 10,
AB + C #= 11.
which, of course, in this example, is trivial.

Assume that non_overlap(StartA, DurA, StartB, DurB) , is a FD constraint, defined by conditional propagation (daemon) mechanisms, expressing that two tasks A and B may not overlap in time. Then, merely stating
non_overlap(StartA, DurA, StartB, DurB),
StartA + DurA #<= StartC, % task C follows A ...
StartB + DurB #<= StartC, % ... and B
is not enough for the system to deduce that
StartC #>= minimum([StartA, StartB]) + DurA + DurB
and it is worth adding this explicitly.

In general, it is worth playing with the prototypes, and even designing small application-specific trace tools to detect this kind of optimization possibilities.

9.4 User-defined constraints

As mentioned above, a (careful) use of user-defined constrained can be recommended, in order to

• enforce more homogeneous grains of information,
• favour the mainstreams of propagation.

Approximate Generalized Propagation [ECRC GP 93] is a promising approach to make this work easier, since it allows both a declarative statement of the constraints and the tuning of the amount of information deduced at each step.

With Constraint Handling Rules [ECRC CHR 93] , a high-level language (Prolog) is used to define the propagations.

Contents

10 Application Description Framework

We call `CLP team' the people who faced the problem of applying CLP to the application, within the lifetime of the CHIC project. `Previous(ly)' refers to a situation prior to the moment when the CLP team started or took over the job.

10.1 Short Problem/Context Description

• Try and describe the application informally in terms of
  - input / output conditions,
  - process to model (whenever it applies),
  - objective to be fulfilled,
  - quantitative hints: size of data, required performance,
  - possibilities of relaxing the problem ( e.g. in scheduling contexts, using subcontracting or relaxing due-dates).

10.2 Problem Characterization

• Were there previous attempts to solve the problem? If yes, using which techniques? Operations Research? With which results?
• What was initial intuition of the CLP team on how the problem would be solved?
• Which techniques were considered and/or tried by the CLP team? Operations Research, Simulated Annealing? With which results? Why was CLP chosen? Which solver was chosen: FD or LS? If LS, why not a linear programming package?
• What were the characteristics of the problem with respect to the criteria elaborated in this document:
  - existing problem classification,
  - global vs. local constraints, homogeneous vs. heterogeneous,
  - sparse vs. dense solution space,
  - predominance of hard vs. soft constraints,
  - one solution vs. optimization,
  - order of magnitude of the number of variables,
  - foreseeable evolution of the system, level of interactivity?
• Were there further attempts to use other techniques, once the CLP development had started? Operations Research, Simulated Annealing? Why? With which results?
• Looking back on it, did CLP prove, eventually, adequate ?

10.3 Problem Modelling

• Were there previous formal models of the problem? If yes, using which formalisms:
  - Operations Research,
  - Objects,
  - other?
• Did the CLP team write formal models ? If yes, attach the models. Which formalisms were used:
  - Operations Research,
  - Objects,
  - CLP-oriented formalism,
  - other?
• If such models were written, did they prove useful ? Describe the transition to Constraint Expression and Prototyping? How hard was it?

10.4 System Specification. Communication Model

• What were the initial views on what the system should do, i.e. the client's initial specification and the CLP team's conception, with respect to
  - optimum sought vs. one solution,
  - level of user intervention:
  • automatic vs. interactive system,
  • handling of failure?
• Was a formal document written, following well established procedures?
• Did the functional definition of the system evolve ? If yes, how and why? Was it because of non-feasibility of the initial specification? At which step did it occur? Did it lead to reconsider Constraint Expression, or even Problem Modelling or Problem Characterization ( loops )?
• What is the current functional definition of the system?

10.5 Constraint Expression and Prototyping

• Were subproblems identified? If yes, what was the initial assessment of their coupling? Were they solved independently? Was this reconsidered later on? Why?
• Describe the successive prototypes , the successive models and resolution strategies, and the reasons for modifying them?
• How were soft constraints handled?
• How was failure (no result produced) handled?
• How did the prototypes scale up ? Were extrapolations made, `exponential factors' computed? Did the scaling up conform to the predictions?
• Were real data used early in the prototyping process?
• Assess the adequacy (expressive power, performance) of the constraints provided in the particular CLP languages (CHIP, Charme, ECLiPSe)? What new features or changes would be required?
• Did prototyping lead to reconsider Characterization issues ( loops )?

10.6 Constraint Optimization

• Is there a clear distinction between the prototype(s) and the final implementation? Or is it basically the same system, that continuously evolved? How far is the final implementation of the constraints from the prototype?
• Describe the optimizations. Is there
  - constraint pre-processing,
  - sophisticated search strategies,
  - user-defined constrained
  to replace general and complex built-in constraints on particular, directional propagations,
  to achieve propagations not allowed by the built-in constraints,
  - addition of redundant constraints?
• If user-defined constraints were implemented, how was this done:
  - using demons or conditional propagation,
  - using ECLiPSe constraint definition languages (GP, CHRs)?
• How much performance did constraint optimization help to gain with respect to the prototypes in terms of size and/or speed? Was that an order of magnitude or a limited improvement?
• How were soft constraints eventually handled?
• How was failure eventually handled?

10.7 Debugging

• What debugging strategies and tools were used?

10.8 Design of Interfaces and Integration

• Does the system have a graphical man-machine interface ? Was this designed and implemented early in the development process? Is this implemented in the CLP language?
• How are data acquired ? Does the system communicate with existing systems ? If yes, how? Is it autonomous system or a module of a larger system? Is the CLP language the integration language?

10.9 General Remarks on the Application as a Project. Conclusion

• How did the project start? As a research project? Did it follow the normal company procedures or was it an `exotic' project?
• Was there some cooperation with mainstream computer developers? Did the project lead to a technology transfer?
• What is the proportion of the constraint core? Try and fill the following table:

  

• How could the most prominent lessons learnt be summarized?
• How could you characterize the specificity of CLP in the light of the project?
• Any other general remarks and conclusions.

Contents

11 Acknowledgments

Contents

12 Selected References

[Bull CharmeObject 94] Charme Object documentation, Bull-Cediag, 1994.

[Bull CHIC 91] Jean-Yves Cras, Benoît Guinaudeau, Outline of CHIC User Requirements and First Methodologic Notes , CHIC deliverable report D 2.1.2.1, Bull-Cediag, June 1991.

[Bull CHIC 92] Jean-Yves Cras, Michel Leconte, Benoît Guinaudeau, Towards a Constraint Programming Methodology , CHIC deliverable report D 2.1.2.2, Bull-Cediag, January 1992.

[Bull CHIC 92'] Michel Leconte, Positioning CLP Methodology in CHIC , CHIC report, Bull-Cediag, June 1992.

[Bull CHIC 93] Michel Leconte, Francis Leyter, Update Specification of Logic Constraint Programming Methodology , CHIC report, Bull-Cediag, June 1993.

[Bull CSP 94] Massimo Paltrinieri, Some Remarks on the Design of Constraint Satisfaction Problems, Bull, 1994.

[Bull Disjunctive 94] André Guillaud, Michel Leconte, Disjunctive Constraints, a Global Approach , CHIC deliverable report D 4.2, Bull, June 1994.

[Bull Formalism 90] Jean-Yves Cras, Conventions for Constraint Expression , CHIC non-deliverable report, Bull-Cediag, September 1990.

[Bull Sets&Graphs 94] Michel Leconte, Implementation of Sets and Graphs Constraints , CHIC deliverable report 5.1.1, Bull, January 1994.

[Bull Tutorial 92] Peter Chan, Tutorial on Constraint Programming, Bull-Cediag, 1992.

[CERT IBT 93] Eric Bensana, Intelligent Backtracking , CHIC deliverable report D 5.3.2.2, CERT, June 1993.

[CHIP CarSeq 88] Mehmet Dincbas & al. , Solving the Car Sequencing Problem in Constraint Logic Programming , ECAI-88, Munich, 1988.

[CHIP CuttingStock 88] Mehmet Dincbas & al. , Solving a Cutting Stock Problem in Constraint Logic Programming , Fifth International Conference on Logic Programming, Seattle, 1992.

[CHIP Warehouse 89] Pascal van Hentenrick, A Logic Language for Combinatorial Optimization , Annals of Operations Research: Special Issue on Links with Artificial Intelligence, 1989. (Warehouse location problem pp. 20-26.)

[Cosytec JFPL 92] Nicolas Beldiceanu, Abderrahmane Aggoun, Extending CHIP in order to solve Complex Scheduling and Placement Problems , JFPL, Lille, France, 1992.

[Cras Review 93] Jean-Yves Cras, A Review of Industrial Constraint Satisfaction Tools , AI Perspectives Report, AI Intelligence (PO Box 95, Oxford, OX2 7XL, UK), 1993.

[Dassault CHIC 95] André Chamard, Annie Fischler, Applying CLP to a Complex Scheduling Problem - The MADE System , CHIC deliverable report D6.5.3, Dassault Aviation, January 1995.

[Dassault PAP 92] Jacques Bellone, André Chamard, Claudine Pradelles, PLANE, An Evolutive Planning System for Aircraft Production written in CHIP , The First International Conference on the Practical Application of Prolog, London, April 1992.

[Dassault PAP 94] André Chamard, Annie Fischler, MADE, A Workshop Scheduler System written in CHIP , The Second International Conference on the Practical Application of Prolog, London, April 1994. (Work partially funded by CHIC.)

[Dassault PAP 95] André Chamard, Decision-support Systems for Planning and Scheduling Aircraft Manufacturing , The Third Conference on the Practical Application of Prolog, Paris, April 1995. (Work partially funded by CHIC.)

[De Backer & Beringer IJCAI 93] Henri Beringer, Bruno De Backer, Satisfiability of Boolean Formulas over Linear Constraints , IJCAI-93, Chambéry, France, 1993.

[ECRC Braghenti 94] Pierre Lim, The Braghenti scheduling application, CTAI Workshop, 1994.

[ECRC CHR 93] Thom Fruhwirth, Temporal Reasoning with Constraint Handling Rules , CHIC deliverable report D 5.3.1.2, ECRC, January 1993.

[ECRC Disjunctive 93] André Veron, Disjunctive Scheduling in Elipsys , APPLAUSE report ECRC.02, May 1993.

[ECRC ECLiPSe 94] ECLiPSe Extensions User Manual, ECRC, January 1994. HTML

[ECRC GP 93] Thierry Le Provost, Mark Wallace, Approximate Generalized Propagation , CHIC deliverable report D 5.2.3.3, ECRC, January 1993.

[ECRC NovelSearch 92] Volker Kuchenhoff, Novel Search and Constraints - an Integration , CHIC deliverable report D 5.3.3.2, ECRC, December 1992.

[ECRC Scheduling 94] Mark Wallace, Constraints for Scheduling , Constraint Programming", Mayoh, Penjaam and Tyugu eds., Nato Advanced Study Institute Series, Springer Verlag, 1994.

[ECRC Tutorial 92] Thom Fruhwirth & al., Constraint Logic Programming - An Informal Introduction , Tutorial, Logic Programming Summer School, Zurich, September 1992.

[ECRC-Cosytec Debugger 92] Abderrahmane Aggoun, Emmanuel van Rossum, Mark Wallace, Specification of a CHIP debugger , CHIC deliverable report D 2.3.1, ECRC, January 1992.

[ICL Tools 94] Owen V.D. Evans, Tools to Visualise Domain Variables , CHIC deliverable report D5.3.4.2, June 1994.

[Renault 2GES 95] Jean-Marc David, Les systêmes Experts de Seconde Génération , Techniques et Sciences Informatiques, to appear.

[Renault CarSeq 92] Chew Tat Leong, Jean-Marc David, Yves Tourbier, Solving Constraint Satisfaction Problems with Simulated Annealing: The Car Sequencing Problem revisited , Avignon 1992. (Work partially funded by CHIC.)

[Renault CHIC 93] Chew Tat Leong, Evaluation of Scheduling Using CHIP , CHIC deliverable report D 3.1.2, Renault, January 1993 .

[Renault CONSTRUCT 92] Alain Nguyen & Jean-Marc David, Relationship s between Problem Features and Problem Solving Methods , Contribution to Deliverable D/WP5/1, ESPRIT II Project EP5477 CONSTRUCT, May 1992.

[Renault IJCAI 93] Jean-Marc David, Chew Tat Leong, Pushing Innovative Techniques into Production Planning; some lessons learned so far , IJCAI Workshop on Knowledge-based Production Planning, Scheduling and Control, Chambéry, 1993. (Work partially funded by CHIC.)

[Renault STP 92] Chew Tat Leong, Jean-Marc David, A Constraint-based Spreadsheet for Cooperative Production Planning , AAAI SIGMAN Workshop on Knowledge-based Production Planning, Scheduling and Control, San Jose, California, 1992. (Work partially funded by CHIC.)

[Siemens CHIC 94] Erik Tidén & al. , Verifying Sequential Circuits with CVE: Technological Considerations and Assessments, CHIC deliverable report D 3.2.4, Siemens, 1994.