Research Interests
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.
Talks
ACP Summer school, June 2016, Cork,
Linear and Dynamic programming for Constraints: summerSchoolTalk1
Tutorial CP, September 2015, Cork,
Lagrangian relaxation for domain filtering: cp2015Talk
ACP Summer school, June 2014, Bologna,
NP-Hard sub-problems involving costs, Lagrangian based filtering: summerSchoolTalk1
Granularity of models, choice of domains: summerSchoolTalk2
Dixièmes Journées Francophones de Progammation par Contraintes, June 2014, Angers
Contraintes NP-Difficiles avec des coûts: exemples d’applications et de filtrage: [invitedTalkJFPC, summary]
Publications
A Branch-And-Price Algorithm for Scheduling Observations on a Telescope.
Nicolas Catusse, Hadrien Cambazard, Nadia Brauner, Pierre Lemaire, Bernard Penz, Anne-Marie Lagrange and Pascal Rubini
IJCAI 2016: 3060-3066
Alternative filtering for the Weighted Circuit Constraint:
Comparing lower bounds for the TSP and solving
TSPTW.
Sylvain
Ducomman, Hadrien Cambazard and Bernard Penz
AAAI 2016: 3390-3396 (2016)
The
algorithm is available as a jar file, to run it refer
to
readme.txt.
[.pdf]
New
Filtering for AtMostNValue and its weighted variant: A
Lagrangian approach.
Hadrien
Cambazard and Jean-Guillaume Fages
Constraints
20(3): 362-380 (2015)
[talk.pdf]
Bin Packing with Linear Usage Costs - An Application to
Energy Management in Data Centres.
Hadrien
Cambazard, Deepak Mehta, Barry O'Sullivan, Helmut Simonis
Proceedings of CP 2013: 47-62
Best
Application paper award
A shortest path-based approach to the multileaf collimator
sequencing problem
Hadrien
Cambazard, Eoin O'Mahony and Barry O'Sullivan
Discrete Applied Mathematics 160 (1-2): 81-99,
2012.
The
algorithm is available as a jar file, to run it refer
to
readme.txt.
[.pdf][jar file][data set1][data set2]
A Constraint Programming Approach for the Traveling
Purchaser Problem
Hadrien
Cambazard and Bernard Penz
Proceedings of CP 2012: 735-749
The
algorithm is available as a jar file, to run it refer
to
readme.txt.
A
Computational Geometry-Based Local Search Algorithm for
Planar Location Problems
Hadrien
Cambazard, Deepak Mehta, Barry O'Sullivan, Luis Quesada
Proceedings of CPAIOR 2012: 97-112
[.pdf]
Domino
portrait generation: a fast and scalable
approach
Hadrien Cambazard, John Horan, Eoin O'Mahony and Barry
O'Sullivan.
Annals of Operations Research 184 (1), 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 194 (1), pages 1–25,
2012.
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.
An Optimal Constraint Programming Approach to the Open-Shop
Problem
Arnaud
Malapert, Hadrien Cambazard, Christelle Guéret, Narendra
Jussien, André Langevin, Louis-Martin Rousseau
INFORMS Journal on Computing 24 (2): 228-244
(2012)
[.pdf]
Propagating
the Bin Packing Constraint using Linear
Programming
Hadrien
Cambazard and Barry O'Sullivan,
Proceedings of CP 2010.
Knowledge Compilation for Itemset Mining
Hadrien
Cambazard, Tarik Hadzic and Barry O'Sullivan,
Proceedings of ECAI 2010: 1109-1110
[.pdf]
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]
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]