Inria International program |
The associate team TASCMELB gathers researchers from the TASC team (http://www.emn.fr/z-info/ppc/) at LINA, UMR 6241 (http://www.lina.univ-nantes.fr/) in Nantes, and the Optimization Research Group (http://org.nicta.com.au/) at NICTA in Melbourne (http://www.nicta.com.au/about).
On the TASC side the following persons are involved in the proposal:
On the NICTA side the following persons are involved in the proposal:
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.
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.
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.
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.
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.
The objectives of our scientific collaboration for the three years of the Associated Team are described here.
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.
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.
N. Beldiceanu, P. Flener, J. Pearson, P. van Hentenryck
Propagating Regular Counting Constraints,
AAAI 2014, p. 2616-2622, July 27-31, 2014, Quebec, Canada.
This document was translated from LATEX by HEVEA.