Research Interests
I have been working three years on explanation based techniques in constraint programming before moving to Cork in the 4c (Cork Constraint Computation Center) where I am working on modelling issues and applications.
My Phd
Résolution de problèmes combinatoires par des approches fondées sur la notion d’explicationPhdCambazard.pdf
Constraint programming is a search paradigm for solving combinatorial optimization problems, that has been used to design generic solvers. Numerous researches are conducted to deal with over-constrained and dynamic problems. One of those, is based on the concept of explanations. Explanations provide a trace of the behavior of the solver and have been initially introduce to improve backtracking based algorithms. They have been used to design clever but costly ways of exploring the search space since that day. This phd thesis study explanation based algorithms on industrial as well as academical problems. We study the interest of explanation within generic decomposition techniques and implement such an algorithm for a hard real time task allocation problem. This approach outlines the role of explanations within the cooperation of different solving techniques. We also show that the explanation network is a relevant information to analyse the structures of a problem and understand the relationships between its different parts (variables and constraints). This information, used to improve the search heuristic, is another step toward generic search techniques. Finally, explanations have been often used for look-back but are still under-exploited for look-ahead in CP. Nogood recording techniques have never been successful contrary to what happended in the SAT community. We implement in this thesis such a nogood recording in the case of the minimum open stack problem.
Publications
Applications
Domino portrait generation: a fast and scalable approach.
Hadrien Cambazard, John Horan, Eoin O'Mahony and Barry O'Sullivan.
Annals of Operations Research, volume 184, pages 79-95, 2011.
See the domino page and compute your own domino portrait.
[.pdf][french.pdf][talk.pdf][jar file][data set]
Local
Search and Constraint Programming for the
Post-Enrolment-based Course Timetabling Problem
Hadrien
Cambazard, Emmanuel Hebrard, Barry O'Sullivan and Alexandre
Papadopoulos,
Annals of
Operations Research, pages 1–25, 2010.
This paper describes our
algorithm, winner of the track 2 of the 2007 International
Timetabling Competition (Track 2). The algorithm and
the benchmark are available here.
Propagating
the Bin Packing Constraint using Linear
Programming
Hadrien Cambazard and
Barry O'Sullivan,
Proceedings of CP 2010.
Hybrid Models for the Multileaf Collimator Sequencing
Problem
Hadrien Cambazard, Eoin
O'Mahony and Barry O'Sullivan,
Proceedings of CP-AI-OR 2010.
The algorithm is available as a jar file, to run it refer
to readme.txt.
A
Shortest Path-based Approach to the Multileaf Collimator
Sequencing Problem
Hadrien Cambazard, Eoin
O'Mahony and Barry O'Sullivan,
Proceedings of CP-AI-OR 2009.
The algorithm is available as a jar file, to run it refer
to readme.txt.
A Constraint Based Approach to Enigma
1225
Hadrien Cambazard, Barry O'Sullivan and
Barbara M. Smith
Journal of Computers and Mathematics with Applications,
2008
[.pdf]
Learning from the past to dynamically improve search: a
case study on the MOSP problem
Hadrien Cambazard and Narendra Jussien, Learning and
Intelligent OptimizatioN, 2007.
[.pdf]
Solving a Real-Time
Allocation Problem with Constraint Programming
Pierre-Emmanuel Hladik, Hadrien Cambazard, Anne-Marie
Déplanche, Narendra Jussien,
in: "Journal of Systems and Software", Elsevier, 2007.
[.pdf]
Subcontractors
scheduling on residential buildings construction
sites
Thierry Benoist,
Antoine Jeanjean, Guillaume Rochart, Hadrien Cambazard,
Emilie Grellier, Narendra Jussien
ISS'06 International Scheduling Symposium, Technical Report
JSME-06-203, pp. 32-37, Japan Society of Mechanical
Engineers, 2006
[.pdf]
Interactively solving
school timetabling problems using extensions of constraint
programming
Hadrien Cambazard, Fabien Demazeau, Narendra Jussien,
Philippe David,
Practice and Theory of Automated Timetabling V, Lecture
Notes in Computer Science, no. 3616, pp. 190-207,
Springer-Verlag, 2005.
[.pdf]
Decomposition and
learning for a real time task allocation problem
Hadrien Cambazard, Pierre-Emmanuel Hladik, Anne-Marie
Déplanche, Narendra Jussien, Yvon Trinquet,
Principles and Practice of Constraint Programming (CP
2004), Lecture Notes in Computer Science, vol. 3258, pp.
153-167, Springer-Verlag, 2004.
[.pdf]
Functional dependencies in table constraints
Reformulating Positive Table Constraints using Functional Dependencies
Hadrien Cambazard and Barry O'Sullivan, Technical report.
[.pdf]
Reformulating Positive Table Constraints using Functional
Dependencies
Hadrien
Cambazard and Barry O'Sullivan, CP 2008, September
2008.
Reformulating Table Constraints using Functional
Dependencies - An Application to Explanation
Generation
Hadrien Cambazard and
Barry O'Sullivan, Constraints Journal, forthcoming April
2008.
A short version of this paper was awarded the best paper
prize of AICS (sponsored by Google).
[.pdf]
Explanations
Identifying and exploiting problem structures using explanation-based constraint programming
Hadrien Cambazard and Narendra Jussien,
in: "Constraints", vol. 11, no. 4, pp. 295-313, Springer Verlag, 2006.
[.pdf]
Automata for Nogood
recording in Constraint satisfaction Problems
Guillaume Richaud, Hadrien Cambazard, Barry O'Sullivan,
Narendra Jussien,
CP06 Workshop on the Integration of SAT and CP techniques,
2006.
[.pdf]
Integrating Benders
decomposition within Constraint Programming
Hadrien Cambazard, Narendra Jussien,
Principles and Practice of Constraint Programming (CP
2005), Lecture Notes in Computer Science, no. 3709, pp.
752-756, Springer-Verlag, Short paper, 2005.
[.pdf]