那伽邪無 Tech notes of DeerRIDER

Constaint-based Reasoning and Programming


Progress

TODO: parallel ONGOING: COMPLETE: CTMCP, Constaint-based Scheduling

Resources

Constraint programming is a powerful paradigm for solving combinatorial search problems that draws on a wide range of techniques from artificial intelligence, computer science, databases, programming languages, and operations research. Constraint programming is currently applied with success to many domains, such as scheduling, planning, vehicle routing, configuration, networks, and bioinformatics.

Concepts, Techniques and Models of Computer Programming (CTMCP), 1st Edition, 2004, Peter Van Roy, Seif Haridi

Essentials of Constraint Programming, 1st Edition, Thom Frühwirth, Slim Abdennadher

  • Readership: graduates, researchers
  • The book is a short, concise and complete presentation of constraint programming and reasoning. The use of constraints had its scientific and commercial breakthrough in the 1990s. Programming with constraints makes it possible to model and solve problems with uncertain, incomplete information and combinatorial problems, as they are abundant in industry and commerce, such as scheduling, planning, transportation, resource allocation, layout, design and analysis. The theoretically well-founded presentation includes application examples from real life. It introduces the common classes of constraint programming languages and constraint systems in a uniform way. Constraint solving algorithms are specified and implemented in the constraint handling rules language (CHR).

Handbook of Constraint Programming, 1st Edition, 2006, Francesca Rossi, Peter van Beek, Toby Walsh

  • Readership: advanced undergraduates, graduates, researchers, software pactitioners
  • The aim of this handbook is to capture the full breadth and depth of the constraint programming field and to be encyclopedic in its scope and coverage. While there are several excellent books on constraint programming, such books necessarily focus on the main notions and techniques and cannot cover also extensions, applications, and languages. The handbook gives a reasonably complete coverage of all these lines of work, based on constraint programming, so that a reader can have a rather precise idea of the whole field and its potential. Of course each line of work is dealt with in a survey-like style, where some details may be neglected in favor of coverage. However, the extensive bibliography of each chapter will help the interested readers to find suitable sources for the missing details. Each chapter of the handbook is intended to be a self-contained survey of a topic, and is written by one or more authors who are leading researchers in the area.
  • Structure:
    • Part I covers the basic foundations of constraint programming, including the history, the notion of constraint propagation, basic search methods, global constraints, tractability and computational complexity, and important issues in modeling a problem as a constraint problem.
    • Part II covers constraint languages and solver, several useful extensions to the basic framework (such as interval constraints, structured domains, and distributed CSPs), and successful application areas for constraint programming.

Handbook of Parallel Constraint Reasoning, 2018 Edition, Youssef Hamadi, Lakhdar Sais

  • Readership: advanced undergraduates and graduates, researchers
  • This is the first book presenting a broad overview of parallelism in constraint-based reasoning formalisms. In recent years, an increasing number of contributions have been made on scaling constraint reasoning thanks to parallel architectures. The goal in this book is to overview these achievements in a concise way, assuming the reader is familiar with the classical, sequential background. It presents work demonstrating the use of multiple resources from single machine multi-core and GPU-based computations to very large scale distributed execution platforms up to 80,000 processing units.
  • The contributions in the book cover the most important and recent contributions in parallel propositional satisfiability (SAT), maximum satisfiability (MaxSAT), quantified Boolean formulas (QBF), satisfiability modulo theory (SMT), theorem proving (TP), answer set programming (ASP), mixed integer linear programming (MILP), constraint programming (CP), stochastic local search (SLS), optimal path finding with A*, model checking for linear-time temporal logic (MC/LTL), binary decision diagrams (BDD), and model-based diagnosis (MBD).

Comments

Content