Constraint Programming (CP)[1] has been successfully appl ied to both constraint satisfaction and constraint optimization prob lems. A wide variety of specialized global constraints provide critical assistan ce in achieving a good model that can take advantage of the structure of the problem in the search for a solution. However, a key outstanding issue is the representation of'a d-hoc' constraints that do not have an inherent combinatorial nature, and hence are n ot modelled well using narrowly specialized global constraints. We attempt to address this issue by considering a hybrid of search and compilation. Specificall y we suggest the use of Reduced Ordered Multi-V alued Decision Diagrams (ROMDDs) as the supporting data structure for a generic global constraint. We g ive an algorithm for maintaining generalized arc consistency (GAC) on this cons traint that amortizes the cost of the GAC computation over a root-to-leaf path in th e search tree without requiring asymptotically more space than used for the MD D. Furthermore we present an approach for incrementally maintaining the redu ced property of the MDD during the search, and show how this can be used for provid ing domain entailment detection. Finally we discuss how to apply our ap proach to other similar data structures such as AOMDDs and Case DAGs. The techni que used can be seen as an extension of the GAC algorithm for the regular la nguage constraint on finite length input [2].

Arithmetic constraints on integer intervals are supported in many constraint programming systems. We study here a number of approaches to implement constraint propagation for these constraints. To describe them we introduce integer interval arithmetic. Each approach is explained using appropriate proof rules that reduce the variable domains. We compare these approaches using a set of benchmarks. For the most promising approach we provide results that characterize the effect of constraint propagation. This is a full version of our earlier paper, cs.PL/0403016.

We study the connection between the order of phase transitions in combinatorial problems and the complexity of decision algorithms for such problems. We rigorously show that, for a class of random constraint satisfaction problems, a limited connection between the two phenomena indeed exists. Specifically, we extend the definition of the spine order parameter of Bollobas et al. to random constraint satisfaction problems, rigorously showing that for such problems a discontinuity of the spine is associated with a $2^{Ω(n)}$ resolution complexity (and thus a $2^{Ω(n)}$ complexity of DPLL algorithms) on random instances. The two phenomena have a common underlying cause: the emergence of ``large'' (linear size) minimally unsatisfiable subformulas of a random formula at the satisfiability phase transition. We present several further results that add weight to the intuition that random constraint satisfaction problems with a sharp threshold and a continuous spine are ``qualitatively similar to random 2-SAT''. Finally, we argue that it is the spine rather than the backbone parameter whose continuity has implications for the decision complexity of combinatorial problems, and we provide experimental evidence that the two parameters can behave in a different manner.

This paper advocates the use of a portfolio of representations for problem solving in complex domains. It describes an approach that decouples efficient storage mechanisms called descriptives from the decision-making procedures that employ them. An architecture that takes this approach can learn which representations are appropriate for a given problem class. Examples of search with a portfolio of representations are drawn from a broad set of domains.

LODE is a web tool for children that are novice readers, and is primarily meant for deaf children. It proposes written stories and interactive games for reasoning, globally, on the stories. In this paper, first, we motivate the rationale of LODE, and explain its reasoning games. Then we briefly describe the design of the web client-server architecture of LODE; the server employs a constraint programming system for creating and solving the LODE games in real time. Finally, we concentrate on two evaluations of the latest prototype of LODE: one with hearing novice readers; another one with deaf readers. We conclude by discussing the results of the evaluations, and their implications for LODE.

When configuring customizable software, it is useful to provide interactive tool-support that ensures that the configuration does not breach given constraints. But, when is a configuration complete and how can the tool help the user to complete it? We formalize this problem and relate it to concepts from non-monotonic reasoning well researched in Artificial Intelligence. The results are interesting for both practitioners and theoreticians. Practitioners will find a technique facilitating an interactive configuration process and experiments supporting feasibility of the approach. Theoreticians will find links between well-known formal concepts and a concrete practical application.

LSCS is a satellite workshop of the international conference on principles and practice of Constraint Programming (CP), since 2004. It is devoted to local search techniques in constraint satisfaction, and focuses on all aspects of local search techniques, including: design and implementation of new algorithms, hybrid stochastic-systematic search, reactive search optimization, adaptive search, modeling for local-search, global constraints, flexibility and robustness, learning methods, and specific applications.

When a high-level constraint programming (CP) language lacks a (possibly global) constraint that would allow the formulation of a particular model of a combinatorial problem, then the modeller traditionally has the choice of (1) switching to another CP language that has all the required constraints, (2) formulating a different model that does not require the lacking constraints, or (3) implementing the lacking constraint in the low-level implementation language of the chosen CP language. This paper addresses the core question of facilitating the third option, and as a side effect often makes the first two options unnecessary. The user-level extensibility of CP languages has been an important goal for over a decade. In the traditional global search approach to CP (namely heuristic-based tree search interleaved with propagation), higher-level abstractions for describing new constraints include indexicals [17]; (possibly enriched) deterministic finite automata (DFAs) via the automaton [2] and regular [11] generic constraints; and multivalued decision diagrams (MDDs) via the mdd [5] generic constraint. Usually, a generic but efficient propagation algorithm achieves a suitable level of local consistency by processing the higher-level description of the new constraint.

We explore the use of the Cell Broadband Engine (Cell/BE for short) for combinatorial optimization applications: we present a parallel version of a constraint-based local search algorithm that has been implemented on a multiprocessor BladeCenter machine with twin Cell/BE processors (total of 16 SPUs per blade). This algorithm was chosen because it fits very well the Cell/BE architecture and requires neither shared memory nor communication between processors, while retaining a compact memory footprint. We study the performance on several large optimization benchmarks and show that this achieves mostly linear time speedups, even sometimes super-linear. This is possible because the parallel implementation might explore simultaneously different parts of the search space and therefore converge faster towards the best sub-space and thus towards a solution. Besides getting speedups, the resulting times exhibit a much smaller variance, which benefits applications where a timely reply is critical.

In this paper, we investigate the hybridization of constraint programming and local search techniques within a large neighbourhood search scheme for solving highly constrained nurse rostering problems. As identified by the research, a crucial part of the large neighbourhood search is the selection of the fragment (neighbourhood, i.e. the set of variables), to be relaxed and re-optimized iteratively. The success of the large neighbourhood search depends on the adequacy of this identified neighbourhood with regard to the problematic part of the solution assignment and the choice of the neighbourhood size. We investigate three strategies to choose the fragment of different sizes within the large neighbourhood search scheme. The first two strategies are tailored concerning the problem properties. The third strategy is more general, using the information of the cost from the soft constraint violations and their propagation as the indicator to choose the variables added into the fragment. The three strategies are analyzed and compared upon a benchmark nurse rostering problem. Promising results demonstrate the possibility of future work in the hybrid approach.