De l’influence de Jacques Pitrat sur mes recherches en programmation par contraintes
Nicolas Beldiceanu1
1 IMT Atlantique, LS2N DAPI 4 rue Alfred Kastler 44307 Nantes, France
Revue Ouverte d'Intelligence Artificielle, Hommage à Jacques Pitrat, Volume 3 (2022) no. 1-2, pp. 141-153.

Dans cet article, je montre comment les enseignements et les travaux de Jacques Pitrat ont orienté ma carrière et ont nourri mes réflexions et mes interrogations dans le domaine de la programmation par contraintes. Après un bref rappel des idées clefs que j’ai retenues, je montre comment j’ai utilisé ces idées tout au long de mon parcours, et j’indique pourquoi ces idées sont toujours d’actualité.

In this article, I show how Jacques Pitrat’s teachings and work have influenced my career and have fed my thoughts and questions in the field of constraint programming. After a brief reminder of the key ideas I adopted, I show how I used these ideas throughout my career and indicate why these ideas are still relevant today.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/roia.24
Mot clés : Contraintes, Métaconnaissances, Programmation par contraintes
Keywords: Constraints, Metaknowledge, Constraint programming

Nicolas Beldiceanu 1

1 IMT Atlantique, LS2N DAPI 4 rue Alfred Kastler 44307 Nantes, France
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{ROIA_2022__3_1-2_141_0,
     author = {Nicolas Beldiceanu},
     title = {De l{\textquoteright}influence de {Jacques} {Pitrat} sur mes recherches en programmation par contraintes},
     journal = {Revue Ouverte d'Intelligence Artificielle},
     pages = {141--153},
     publisher = {Association pour la diffusion de la recherche francophone en intelligence artificielle},
     volume = {3},
     number = {1-2},
     year = {2022},
     doi = {10.5802/roia.24},
     language = {fr},
     url = {https://roia.centre-mersenne.org/articles/10.5802/roia.24/}
}
TY  - JOUR
AU  - Nicolas Beldiceanu
TI  - De l’influence de Jacques Pitrat sur mes recherches en programmation par contraintes
JO  - Revue Ouverte d'Intelligence Artificielle
PY  - 2022
SP  - 141
EP  - 153
VL  - 3
IS  - 1-2
PB  - Association pour la diffusion de la recherche francophone en intelligence artificielle
UR  - https://roia.centre-mersenne.org/articles/10.5802/roia.24/
DO  - 10.5802/roia.24
LA  - fr
ID  - ROIA_2022__3_1-2_141_0
ER  - 
%0 Journal Article
%A Nicolas Beldiceanu
%T De l’influence de Jacques Pitrat sur mes recherches en programmation par contraintes
%J Revue Ouverte d'Intelligence Artificielle
%D 2022
%P 141-153
%V 3
%N 1-2
%I Association pour la diffusion de la recherche francophone en intelligence artificielle
%U https://roia.centre-mersenne.org/articles/10.5802/roia.24/
%R 10.5802/roia.24
%G fr
%F ROIA_2022__3_1-2_141_0
Nicolas Beldiceanu. De l’influence de Jacques Pitrat sur mes recherches en programmation par contraintes. Revue Ouverte d'Intelligence Artificielle, Hommage à Jacques Pitrat, Volume 3 (2022) no. 1-2, pp. 141-153. doi : 10.5802/roia.24. https://roia.centre-mersenne.org/articles/10.5802/roia.24/

[1] A. Aggoun; N. Beldiceanu Extending CHIP in order to Solve Complex Scheduling and Placement Problems, Mathl. Comput. Modelling, Volume 17 (1993) no. 7, pp. 57-73 | DOI

[2] E. Arafailova; N. Beldiceanu; M. Carlsson; P. Flener; M. A. F. Rodríguez; J. Pearson; H. Simonis Systematic Derivation of Bounds and Glue Constraints for Time-Series Constraints, Principles and Practice of Constraint Programming (CP’2016) (LNCS), Volume 9892 (2016), pp. 13-29 | DOI

[3] E. Arafailova; N. Beldiceanu; R. Douence; M. Carlsson; P. Flener; M. A. F. Rodríguez; J. Pearson; H. Simonis Global Constraint Catalog, Volume II, Time-Series Constraints (2018) (https://arxiv.org/abs/1609.08925)

[4] E. Arafailova; N. Beldiceanu; R. Douence; P. Flener; M. A. Francisco Rodríguez; J. Pearson; H. Simonis Time-Series Constraints : Improvements and Application in CP and MIP Contexts, International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR’16) (LNCS), Volume 9676 (2016), pp. 18-34 | DOI

[5] E. Arafailova; N. Beldiceanu; H. Simonis Generating Linear Invariants for a Conjunction of Automata Constraints, Principles and Practice of Constraint Programming (CP’2017) (LNCS), Volume 10416 (2017), pp. 21-37 | DOI

[6] E. Arafailova; N. Beldiceanu; H. Simonis Deriving Generic Bounds for Time-Series Constraints Based on Regular Expressions Characteristics, Constraints An Int. J., Volume 23 (2018) no. 1, pp. 44-86 | DOI

[7] E. Arafailova; N. Beldiceanu; H. Simonis Invariants for time-series constraints, Constraints An Int. J., Volume 25 (2020) no. 3-4, pp. 71-120 | DOI

[8] N. Beldiceanu An example of introduction of global constraints in CHIP : Application to block theory problems (1990) no. TR-LP-49 (Technical report)

[9] N. Beldiceanu Global Constraints as Graph Properties on a Structured Network of Elementary Constraints of the Same Type, Principles and Practice of Constraint Programming (CP’2000) (LNCS), Volume 1894 (2000), pp. 52-66 (Preprint available as SICS Tech Report T2000-01, soda.swedish-ict.se/2284/2/SICS-T--2000-01--SE.pdf)

[10] N. Beldiceanu; M. Carlsson Revisiting the Lexicographic Ordering Constraint (2002) no. T2002-17 (Available at http://www.diva-portal.org/smash/get/diva2:1041533/FULLTEXT01.pdf) (Technical report)

[11] N. Beldiceanu; M. Carlsson; R. Debruyne; T. Petit Reformulation of Global Constraints Based on Constraint Checkers, Constraints An Int. J., Volume 10 (2005) no. 4, pp. 339-362 | DOI

[12] N. Beldiceanu; M. Carlsson; R. Douence; H. Simonis Using finite transducers for describing and synthesising structural time-series constraints, Constraints An Int. J., Volume 21 (2016) no. 1, pp. 22-40 | DOI

[13] N. Beldiceanu; M. Carlsson; J.-X. Rampon Global Constraint Catalog, 2nd Edition (revision a) (2012) no. T2012-03 (Available at http://soda.swedish-ict.se/5195/1/T2012-03.pdf) (Technical report)

[14] N. Beldiceanu; T. Petit Cost Evaluation of Soft Global Constraints, International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR’2004) (LNCS), Volume 3011 (2004), pp. 80-95 | DOI

[15] N. Beldiceanu; H. Simonis A Constraint Seeker : Finding and Ranking Global Constraints from Examples, Principles and Practice of Constraint Programming (CP’2011) (LNCS), Volume 6876 (2011), pp. 12-25 | DOI

[16] N. Beldiceanu; H. Simonis A Model Seeker : Extracting Global Constraint Models from Positive Examples, Principles and Practice of Constraint Programming (CP’2012) (LNCS), Volume 7514 (2012), pp. 141-157 | DOI

[17] C. Bessière; G. Katsirelos; N. Narodytska; C.-G. Quimper; T. Walsh Decompositions of all different, global cardinality and related constraints, IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009 (2009), pp. 419-424

[18] N. Bleuzen-Guernalec; A. Colmerauer Optimal Narrowing of a Block of Sortings in Optimal Time, Constraints An Int. J., Volume 5 (2000) no. 1/2, pp. 85-118 | DOI

[19] M. Carlsson; N. Beldiceanu From Constraints to Finite Automata to Filtering Algorithms, Programming Languages and Systems, 13th European Symposium on Programming, ESOP 2004, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004, Barcelona, Spain, March 29 - April 2, 2004, Proceedings (2004), pp. 94-108 | DOI

[20] M. Carlsson; N. Beldiceanu; J. Martin A Geometric Constraint over k-Dimensional Objects and Shapes Subject to Business Rules, Principles and Practice of Constraint Programming (CP’2008) (LNCS), Volume 5202 (2008), pp. 220-234 | DOI

[21] P. Codognet; D. Diaz A Simple and Efficient Boolean Solver for Constraint Logic Programming, J. Autom. Reason., Volume 17 (1996) no. 1, pp. 97-129 | DOI

[22] M.-C. Costa Persistency in maximum cardinality bipartite matchings, Operation Research Letters, Volume 15 (1994), pp. 143-149 | DOI

[23] M.-C. Coté; B. Gendron; L.-M. Rousseau Modeling the Regular Constraint with Integer Programming, International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR’2007) (LNCS), Volume 4150 (2007), pp. 29-43 | DOI

[24] M. Fischetti; L. Liberti; D. Salvagnin; T. Walsh Orbital shrinking : Theory and applications, Discret. Appl. Math., Volume 222 (2017), pp. 109-123 | DOI

[25] M. A. Francisco Rodríguez; P. Flener; J. Pearson Implied constraints for automaton constraints, GCAI 2015 (2015) (Available at http://www.easychair.org/publications/paper/Implied_Constraints_for_Automaton_Constraints)

[26] M. A. Francisco Rodríguez; P. Flener; J. Pearson Automatic Generation of Descriptions of Time-Series Constraints, 29th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2017, Boston, MA, USA, November 6-8, 2017 (2017), pp. 102-109

[27] A. M. Frisch; B. Hnich; Z. Kızıltan; I. Miguel; T. Walsh Global Constraints for Lexicographic Orderings, Principles and Practice of Constraint Programming (CP’2002) (LNCS), Volume 2470 (2002), pp. 93-108

[28] W.-J. van Hoeve; I. Katriel Global Constraints, Handbook of Constraint Programming (F. Rossi; P. van Beek; T. Walsh, eds.), Elsevier, 2006, pp. 169-208 | DOI

[29] D. Hofstadter; E. Sander L’Analogie, coeur de la pensée, Odile Jacob, 2013

[30] A. Lahrichi Ordonnancements : la notion de partie obligatoire et son application aux problèmes cumulatifs, Ph. D. Thesis, Paris 6 University, France, Mai (1979)

[31] C. E. Larson; N. Van Cleemput Automated conjecturing I : Fajtlowicz’s Dalmatian heuristic revisited, Artif. Intell., Volume 231 (2016), pp. 17-38 | DOI

[32] J.-L. Laurière A Language and a Program for Stating and Solving Combinatorial Problems, Artificial Intelligence, Volume 10 (1978) no. 1, pp. 29-127 | DOI

[33] J.-L. Laurière Toward Efficiency Through Generality, Proceedings of the Sixth International Joint Conference on Artificial Intelligence, IJCAI 79, Tokyo, Japan, August 20-23, 1979, 2 Volumes (1979), pp. 519-521

[34] M. J. Maher Open Contractible Global Constraints, IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009 (2009), pp. 578-583

[35] N. Nethercote; P. J. Stuckey; R. Becket; S. Brand; G. J. Duck; G. Tack MiniZinc : Towards a Standard CP Modelling Language, Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007, Proceedings (Lecture Notes in Computer Science), Volume 4741 (2007), pp. 529-543

[36] W. J. Older; G. M. Swinkels; M. H. van Emden Getting to the Real Problem : Experience with BNR Prolog in OR, 3rd Int. Conf. on the Practical Application of Prolog (PAP’95) (1995), pp. 465-478

[37] G. Pesant A Regular Language Membership Constraint for Finite Sequences of Variables, Principles and Practice of Constraint Programming (CP’2004) (LNCS), Volume 3258 (2004), pp. 482-495

[38] J. Pitrat Métaconnaissance, Futur de l’Intelligence Artificielle, Hermès, 1993

[39] J. Pitrat AI Systems Are Dumb Because AI Researchers Are Too Clever, ACM Comput. Surv., Volume 27 (1995) no. 3, pp. 349-350 | DOI

[40] J. Pitrat Penser autrement l’informatique, Hermès, 2000

[41] J. Pitrat MALICE, notre collègue, Colloque Métaconnaissance de Berder (2001), pp. 4-19

[42] J. Pitrat A Step toward an Artificial Artificial Intelligence Scientist (2008) (Technical report)

[43] J. Pitrat Artificial Beings, Wiley InterScience, 2009 | DOI

[44] G. Raayoni; G. Pisha; Y. Manor; U. Mendlovic; D. Haviv; Y. Hadad; I. Kaminer The Ramanujan Machine : Automatically Generated Conjectures on Fundamental Constants, Nature, Volume 590 (2021), pp. 67-73 | DOI

[45] J.-C. Régin A Filtering Algorithm for Constraints of Difference in CSP, 12th National Conference on Artificial Intelligence (AAAI-94) (1994), pp. 362-367

[46] A. Schutt; T. Feydy; P. J. Stuckey; M. G. Wallace Explaining the cumulative propagator, Constraints An Int. J., Volume 16 (2011) no. 3, pp. 250-282 | DOI

[47] G. J. Stein Machine Learning & Robotics : My (biased) 2019 State of the Field, http://cachestocaches.com/2019/12/my-state-of-the-field/ (Accessed : 2021-07-28)

[48] R. Sutton The Bitter Lesson, http://incompleteideas.net/IncIdeas/BitterLesson.html (Accessed : 2021-07-28)

[49] L. G. Valiant The complexity of computing the permanent, Theoretical Computer Science, Volume 8 (1979), pp. 189-201 | DOI

[50] P. Van Hentenryck Scheduling and Packing in the Constraint Language cc(FD), Intelligent Scheduling (1994)

[51] A. Zanarini; G. Pesant Solution Counting Algorithms for Constraint-Centered Search Heuristics, Principles and Practice of Constraint Programming (CP’2007) (LNCS), Volume 4741 (2007), pp. 743-757

Cité par Sources :