My Constraint Programming Blog

Today's cable and satellite systems provide a multitude of TV viewing choices for a user, making it difficult to select the best program to watch at any one time. Digital video recording and IPTV add even more options, allowing to time- and sometimes place-shift TV watching. CPTV is a system which generates a personalized viewing schedule for a user, integrated with his current calendar tools. The system is based on three main elements: a rule based system to express viewing preferences, a content-based recommender system to suggest films based on past viewing selections and information extracted from Wikipedia, and a constraint-based scheduler which plans and schedules recording and viewing schedules around existing events and availability time periods of a user. The application thus combines different AI methods in one Web-based application, and is implemented using the constraint logic programming system ECLiPSe.

Visualization is one of the best techniques to understand the behaviour of a constraint program, allowing to directly observe the impact of changes by visual inspection instead of tedious debugging. So far, most constraint visualization tools have been closely linked to specific solvers, making it difficult to compare alternative solvers and to reuse development effort spent on other systems. The new, light-weight VIZ system provides a simple XML based interface for solvers, and can be easily extended by writing basic Java code. In this talk we describe the overall system architecture, give examples of the visualization possible and show how the tool has been used to improve a number of constraint models in different domains.

This talk will review our experience in building automatic test data generation tools with SICStus Prolog in various contexts. Using Logic Programming in this area is not new but putting theory into practice requires to take care of some non-trivial aspects of this real-world implementation of Prolog. We will also discuss of the use of global constraints to handle structure and control of classical programming language features in order to benefit from powerful deduction rules available in SICStus Prolog.

We explore the idea of using automata to implement new constraints for local search. This is already a successful approach in constraint-based global search. We show how to maintain the violations of a constraint and its decision variables via a (deterministic or nondeterministic) finite automaton that describes a ground checker for that constraint. We extend the approach to counter automata, which are often much more convenient than finite automata, if not more independent of the constraint instance, and can even recognise non-regular languages. We establish the practicality of our approach on several real-life combinatorial problems. This is joint work with Pierre Flener and Justin Pearson.

Context-free grammar constraints enforce that an ordered set of variables must form a word in a language defined by a context-free grammar. For this constraint, we devise an efficient, complete filtering algorithm that has the same asymptotic complexity as the Cocke-Younger-Kasami algorithm for parsing context-free languages. Particularly, we show how to filter a sequence of monotonically tightening problems in cubic time and quadratic space. We present experiments on a shift scheduling problem that shows orders of magnitude improvements in time and space consumption.

Recently many new IPTV providers have appeared, typically telephone and broadband companies, that now distribute scheduled TV channels, sometimes high-definition TV and video-on-demand (VoD) over IP in their own network. From a network management perspective, distribution of IPTV can be seen as a scheduling problem with the network links and storage facilities as resources and the objective to balance the overall load in the network. We show that scheduling and optimisation techniques can be used to make the distribution of IPTV more efficient by pushing content out to caches in the network to the right place at the right time.

Solving constraint satisfaction and optimisation problems is increasingly crucial in industry, in order to cope effectively with hard problems of practical relevance. However, the approach of exploiting, in production scenarios, current constraint or mathematical programming solvers has severe limitations, which clearly demand new methods: data is usually stored in potentially very large databases, and building a problem model in central memory suitable for current solvers could be very challenging or impossible. We present a declarative language based on SQL for modelling combinatorial problems, and novel techniques for local search algorithms explicitly designed to work directly on relational databases. We also discuss and experiment with a solver implementation that, working on top of any DBMS, exploits such algorithms in a way transparent to the user, allowing a smooth integration of combinatorial problem solving into industry environments.

I will describe the work our optimisation group has done in the domain of Nurse rostering. Rostering is the process of creating a working plan that shows employees working hours over a given planning horizon. Our approach is a hybrid one that uses Constraint Programming techniques to find an initial solution that becomes the starting point for an Iterated Local Search algorithm. We have tested and verified our approach on real world instances and it's currently implemented at several hospitals in Norway.

Automatic parallelization in constraint programming (CP) becomes increasingly important when new multi-core architectures provide ways to improve performance. Previous research on parallelism in CP has mostly focused on parallel search. However, the consistency part of the solving process is often magnitudes more time-consuming. Before, we have looked at parallel consistency. In this paper we investigate how to combine parallel search with parallel consistency. We evaluate which problems are suitable and which are not. Our results show that parallelizing the entire solving process in CP is a major challenge as parallel search and parallel consistency typically suit different problems.