1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128@article{pesant_support_2019, title = {From {Support} {Propagation} to {Belief} {Propagation} in {Constraint} {Programming}}, volume = {66}, issn = {1076-9757, 1943-5037}, url = {https://www.webofscience.com/wos/woscc/full-record/WOS:000489021500005}, abstract = {The distinctive driving force of constraint programming to solve combinatorial problems has been a privileged access to problem structure through the high-level models it uses. From that exposed structure in the form of so-called global constraints, powerful inference algorithms have shared information between constraints by propagating it through shared variables' domains, traditionally by removing unsupported values. This paper investigates a richer propagation medium made possible by recent work on counting solutions inside constraints. Beliefs about individual variable-value assignments are exchanged between contraints and iteratively adjusted. It generalizes standard support propagation and aims to converge to the true marginal distributions of the solutions over individual variables. Its advantage over standard belief propagation is that the higher-level models featuring large-arity (global) constraints do not tend to create as many cycles, which are known to be problematic for convergence. The necessary architectural changes to a constraint programming solver are described and an empirical study of the proposal is conducted on its implementation. We find that it provides close approximations to the true marginals and that it significantly improves search guidance.}, language = {English}, urldate = {2024-05-24}, journal = {JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH}, author = {Pesant, Gilles}, year = {2019}, note = {Num Pages: 28 Place: Marina Del Rey Publisher: Ai Access Foundation Web of Science ID: WOS:000489021500005}, keywords = {CONSISTENCY, COUNTING SOLUTIONS, PROBABILISTIC INFERENCE, SEARCH HEURISTICS}, pages = {123--150}, file = {Pesant - 2019 - From Support Propagation to Belief Propagation in .pdf:/home/axel/Zotero/storage/GYRBR5YF/Pesant - 2019 - From Support Propagation to Belief Propagation in .pdf:application/pdf}, } @article{dechter_power_nodate, title = {On the {Power} of {Belief} {Propagation}: {A} {Constraint} {Propagation} {Perspective}}, language = {en}, author = {Dechter, R and Bidyuk, B and Mateescu, R and Rollon, E}, file = {Dechter et al. - On the Power of Belief Propagation A Constraint P.pdf:/home/axel/Zotero/storage/IKEWEARF/Dechter et al. - On the Power of Belief Propagation A Constraint P.pdf:application/pdf}, } @incollection{pesant_babaki_search_2020, address = {Cham}, title = {Combinatorial {Search} in {CP}-{Based} {Iterated} {Belief} {Propagation}}, volume = {12333}, isbn = {978-3-030-58474-0 978-3-030-58475-7}, url = {https://link.springer.com/10.1007/978-3-030-58475-7_2}, abstract = {Compared to most other computational approaches to solving combinatorial problems, Constraint Programming’s distinctive feature has been its very high-level modeling primitives which expose much of the combinatorial substructures of a problem. Weighted counting on these substructures (i.e. constraints) can be used to compute beliefs about certain variable-value assignments occurring in a solution to the given constraint. A recent proposal generalizes the propagation mechanism of constraint programming to one sharing such beliefs between constraints. These beliefs, even if not computed exactly, can be very revealing for search. In this paper we investigate how best to guide combinatorial search in this cp-based belief propagation framework. We empirically evaluate branching heuristics on a wide set of benchmark constraint satisfaction problems.}, language = {en}, urldate = {2024-06-27}, booktitle = {Principles and {Practice} of {Constraint} {Programming}}, publisher = {Springer International Publishing}, author = {Babaki, Behrouz and Omrani, Bilel and Pesant, Gilles}, editor = {Simonis, Helmut}, year = {2020}, doi = {10.1007/978-3-030-58475-7_2}, note = {Series Title: Lecture Notes in Computer Science}, pages = {21--36}, file = {Babaki et al. - 2020 - Combinatorial Search in CP-Based Iterated Belief P.pdf:/home/axel/Zotero/storage/HKKSLFVF/Babaki et al. - 2020 - Combinatorial Search in CP-Based Iterated Belief P.pdf:application/pdf}, } @article{pesant_counting-based_2016, title = {Counting-{Based} {Search} for {Constraint} {Optimization} {Problems}}, volume = {30}, issn = {2374-3468, 2159-5399}, url = {https://ojs.aaai.org/index.php/AAAI/article/view/10433}, doi = {10.1609/aaai.v30i1.10433}, abstract = {Branching heuristics based on counting solutions in constraints have been quite good at guiding search to solve constraint satisfaction problems. But do they perform as well for constraint optimization problems? We propose an adaptation of counting-based search for optimization, show how to modify solution density computation for some of the most frequently-occurring constraints, and empirically evaluate its performance on several benchmark problems.}, language = {en}, number = {1}, urldate = {2024-06-27}, journal = {Proceedings of the AAAI Conference on Artificial Intelligence}, author = {Pesant, Gilles}, month = mar, year = {2016}, file = {Pesant - 2016 - Counting-Based Search for Constraint Optimization .pdf:/home/axel/Zotero/storage/G68W2QPG/Pesant - 2016 - Counting-Based Search for Constraint Optimization .pdf:application/pdf}, } @misc{regin_filtering_nodate, title = {A {Filtering} {Algorithm} for {Constraints} of {Difference} in {CSPs}}, url = {https://aaai.org/papers/00362-aaai94-055-a-filtering-algorithm-for-constraints-of-difference-in-csps/}, language = {en-US}, urldate = {2025-01-15}, journal = {AAAI}, author = {Régin, Jean-Charles}, file = {PDF:/home/axel/Zotero/storage/ZJ36H64F/Régin - A Filtering Algorithm for Constraints of Difference in CSPs.pdf:application/pdf;Snapshot:/home/axel/Zotero/storage/27LVNAIR/00362-AAAI94-055-a-filtering-algorithm-for-constraints-of-difference-in-csps.html:text/html}, } @article{trick_dynamic_2003, title = {A {Dynamic} {Programming} {Approach} for {Consistency} and {Propagation} for {Knapsack} {Constraints}}, volume = {118}, issn = {1572-9338}, url = {https://doi.org/10.1023/A:1021801522545}, doi = {10.1023/A:1021801522545}, abstract = {Knapsack constraints are a key modeling structure in constraint programming. These constraints are normally handled with simple bounding arguments. We propose a dynamic programming structure to represent these constraints. With this structure, we are able to achieve hyper-arc consistency, to determine infeasibility before all variables are set, to generate all solutions quickly, and to provide incrementality by updating the structure after domain reduction. Testing on a difficult set of multiple knapsack instances shows significant reduction in branching.}, language = {en}, number = {1}, urldate = {2025-01-15}, journal = {Annals of Operations Research}, author = {Trick, Michael A.}, month = feb, year = {2003}, keywords = {dynamic programming, global constraints, knapsack constraints}, pages = {73--84}, file = {Full Text PDF:/home/axel/Zotero/storage/479IRPRL/Trick - 2003 - A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints.pdf:application/pdf}, } @inproceedings{hutchison_regular_2004, address = {Berlin, Heidelberg}, title = {A {Regular} {Language} {Membership} {Constraint} for {Finite} {Sequences} of {Variables}}, volume = {3258}, isbn = {978-3-540-23241-4 978-3-540-30201-8}, url = {http://link.springer.com/10.1007/978-3-540-30201-8_36}, doi = {10.1007/978-3-540-30201-8_36}, abstract = {This paper describes a global constraint on a fixed-length sequence of finite-domain variables requiring that the corresponding sequence of values taken by these variables belong to a given regular language, thereby generalizing some other known global constraints. We describe and analyze a filtering algorithm achieving generalized arc consistency for this constraint. Some comparative empirical results are also given.}, urldate = {2025-01-15}, publisher = {Springer Berlin Heidelberg}, author = {Pesant, Gilles}, editor = {Hutchison, David and Kanade, Takeo and Kittler, Josef and Kleinberg, Jon M. and Mattern, Friedemann and Mitchell, John C. and Naor, Moni and Nierstrasz, Oscar and Pandu Rangan, C. and Steffen, Bernhard and Sudan, Madhu and Terzopoulos, Demetri and Tygar, Dough and Vardi, Moshe Y. and Weikum, Gerhard and Wallace, Mark}, year = {2004}, doi = {10.1007/978-3-540-30201-8_36}, note = {Book Title: Principles and Practice of Constraint Programming – CP 2004 Series Title: Lecture Notes in Computer Science}, pages = {482--495}, annote = {[TLDR] A filtering algorithm is described and analyzed achieving generalized arc consistency for this constraint requiring that the corresponding sequence of values taken by these variables belong to a given regular language, thereby generalizing some other known global constraints.}, file = {PDF:/home/axel/Zotero/storage/VQ8DKCB7/Pesant - 2004 - A Regular Language Membership Constraint for Finite Sequences of Variables.pdf:application/pdf}, } @book{dechter_constraint_2003, title = {Constraint {Processing}}, isbn = {978-1-55860-890-0}, abstract = {This book provides a comprehensive and much needed introduction to the field by one of its foremost experts. It is beautifully written and presents a unifying framework capturing a wide range of techniques for processing symbolic, numerical, and probabilistic information.--Bart Selman, Cornell UniversityI've been waiting a long time for a good theoretical introduction to constraint programming. Rina Dechter's book is just this. If you want to understand why this technology works, and how to make it work for you, then I recommend you read this book.--Toby Walsh, Cork Constraint Computation CentreThe book is rigorous but it is not difficult to read. An abundance of examples illustrate concepts and algorithms. The reader is well guided through technical issues, so intuition is never hidden by technicalities.--Pedro Meseguer, Institut d'Investigació en Intel.lingència Artificial - Consejo Superior de Investigaciones Científicas (IIIA-CSIC)An indispensable resource for researchers and practitioners in AI and optimization. --Henry Kautz, University of WashingtonConstraint satisfaction is a simple but powerful tool. Constraints identify the impossible and reduce the realm of possibilities to effectively focus on the possible, allowing for a natural declarative formulation of what must be satisfied, without expressing how. The field of constraint reasoning has matured over the last three decades with contributions from a diverse community of researchers in artificial intelligence, databases and programming languages, operations research, management science, and applied mathematics. Today, constraint problems are used to model cognitive tasks in vision, language comprehension, default reasoning, diagnosis, scheduling, temporal and spatial reasoning. In Constraint Processing, Rina Dechter, synthesizes these contributions, along with her own significant work, to provide the first comprehensive examination of the theory that underlies constraint processing algorithms. Throughout, she focuses on fundamental tools and principles, emphasizing the representation and analysis of algorithms. ·Examines the basic practical aspects of each topic and then tackles more advanced issues, including current research challenges·Builds the reader's understanding with definitions, examples, theory, algorithms and complexity analysis·Synthesizes three decades of researchers work on constraint processing in AI, databases and programming languages, operations research, management science, and applied mathematics}, language = {en}, publisher = {Morgan Kaufmann}, author = {Dechter, Rina}, month = may, year = {2003}, note = {Google-Books-ID: w4LG4EUOBCwC}, keywords = {Computers / Artificial Intelligence / Expert Systems, Computers / Artificial Intelligence / General, Computers / Computer Science, Computers / Programming / General, Computers / Programming / Object Oriented, COMPUTERS / Programming / Open Source, COMPUTERS / Software Development \& Engineering / General, COMPUTERS / Software Development \& Engineering / Tools}, }