Inria International program
Associate Team 2014-2016

The associate team TASCMELB gathers researchers from the TASC team ( at LINA, UMR 6241 ( in Nantes, and the Optimization Research Group ( at NICTA in Melbourne (

Synergy between Filtering and Explanations for Scheduling and Placement Constraints
Associate Team acronym:
Principal investigator (Inria):
Nicolas Beldiceanu, TASC
Principal investigator (Main team):
Pascal van Hentenryck, NICTA, Australia

1  Partnership

1.1  Detailed list of participants

On the TASC side the following persons are involved in the proposal:

On the NICTA side the following persons are involved in the proposal:

1.2  Nature and history of the collaboration

1.2.1  History

The two principal investigators were working in the same team at ECRC in 1988/1989 in Munich on the CHIP (Constraint Handling in Prolog) project. The last three years they have shortly meet in Uppsala and Nantes for working on constraints and automata with some common Swedish colleagues. Pascal is doctor honoris causa degrees from Nantes University in 2011. A former PhD student of Mines de Nantes, Victor Pillac, and an engineer from Mines de Nantes, Caroline Even, are both currently working at NICTA in the optimisation group of Pascal.

1.2.2  Context

Constraint programming emerges in the eighties and develops at the intersection of Artificial Intelligence and Operations Research, of Computer Science and Mathematics. The current proposal proposes to extend constraint solvers to handle in a better an integrated ways scheduling and packing problems by simultaneously combining knowledge and techniques from SAT, geometry and library designs.

1.2.3  Nature and complementarity of the proposed collaboration

We address the synergy between filtering and explanations for scheduling and placement constraints. On the one hand the TASC team has been a forerunner both in the context of scheduling and placement constraints,1 and in the context of explanations.2 On the other hand the Melbourne team has been pioneer in the use of SAT-style explanations in the context of constraint programming.3

By using the combination of light filtering and SAT-style explanations the Melbourne team has currently the best approach for solving small (up to 200 activities) hard instances of resource constrained project scheduling (RCPSP),4 compared to all existing approaches and in particular OR methods. By using greedy (respectively light) algorithms based fast convergence to the fix point, the TASC team could recently handle with Choco up to 1 millions activities in 15 minutes (respectively 16000 activities in 4 minutes) in the context of scheduling.5 By putting their complementary expertise it is expected to advance state of the art wrt both solving hard scheduling and placement problems and scalability.

1.2.4  Existing activities in 2013 between TASC and NICTA

2  Scientific program

2.1  Context

2.1.1  Scheduling

On the one hand scheduling and packing problems have a long tradition in the context of Operations Research. This stems from the fact that we both have hard academic pure problems on which generation of researchers have tried out different ideas in order to push the limit of the problems that can be solved, and concrete problems that combines various operational constraints linking various aspects such as how to simultaneously optimise the packing of items, while considering the order in which places are visited.

With the integration of scheduling libraries in early constraint programming systems such as Ilog Solver, scheduling has been a success in the context of industrial applications. It was also shown that constraint programming was competitive in the context of academic benchmarks.

On the one hand, by recently coupling the filtering associated with scheduling constraints together with SAT-style explanation (i.e., filtering algorithms are also used for generating explanation of why a value was removed in term of a set of clauses) recent work has lead to significative improvement on academic benchmarks which currently beats any other methods.

Finally, new challenges [d] arise from the concrete need to handle large scale strongly correlated scheduling and packing problems where each subproblem cannot be solved independently without sacrificed efficiency. This stems from the fact that too many assumptions have to be made when solving one subproblem about the way the other subproblem will be handled.

2.1.2  Interactive CP

CP solvers usually provide either one solution, or all the solutions, to a problem expressed with logical relations between some variables. This is unsufficient when the problem cannot be fully formalized, as it is the case in arts or humanities, or when there is a need for expert, non formalizable knowledge, like in medicine or engineering. We want to develop solving tools where the user could investigate the solution set interactively, possibly modifying the solution or the constraints. The solver needs to keep the quality of the proposed solutions, by resolving the problem on the fly. We will rely on the expertise of both teams who have worked in interactive solving on two applications: urban planning in Nantes, medicine in Melbourne.

2.2  Objectives

The objectives of our scientific collaboration for the three years of the Associated Team are described here.

2.2.1  Scheduling

The objective of the collaboration is twofold:

The approach used will be:

Finally careful investigation will be done between the interaction of filtering, the search and the generation of explanations. This will be done to control the size of the generated explanations, and the set of explanations which can still be active.

2.2.2  Interactive CP

The goal is now to compare our two frameworks, generalize the ideas and define a generic interactive solver. This may be done in interaction with other teams from Nantes and Melbourne, in particular the Marvl group at Monash University, with a strong expertise both in visualisation and in CP.

3  Record of activitites

3.1  Visits

3.2  Publications

N. Beldiceanu, P. Flener, J. Pearson, P. van Hentenryck
Propagating Regular Counting Constraints,
AAAI 2014, p. 2616-2622, July 27-31, 2014, Quebec, Canada.

A. Aggoun, N. Beldiceanu. Extending CHIP in order to solve complex scheduling and placement problems. Mathematical and Computer Modelling 17 (7), pp. 57–73, 1993.
N. Jussien, V. Barichard. The PaLM system: explanation-based constraint programming. Proceedings of TRICS pp. 118–133, 2000.
O. Ohrimenko, P. Stuckey, and M. Codish. Propagation via lazy clause generation. Constraints, 14(3), pp. 357–391, 2009.
A. Schutt, T. Feydy, P. Stuckey and M. Wallace. Solving RCPSP/max by lazy clause generation. Journal of Scheduling, 16(3), pp. 1–17, 2012.
A. Letort, M. Carlsson, N. Beldiceanu. A Synchronized Sweep Algorithm for the k-dimensional cumulative Constraint. CPAIOR 2013, LNCS 7874, pp. 144–159.
N. Narodytska, T. Petit, M. Siala, and T. Walsh. Three Generalizations of the FOCUS Constraint. IJCAI, 23rd International Joint Conference on A.I., 2013. see also
N. Beldiceanu, P. Flener, J. Pearson, P. van Hentenryck. Propagating Regular Counting Constraints, CoRR report, 2013.

This document was translated from LATEX by HEVEA.