The Experts below are selected from a list of 61590 Experts worldwide ranked by ideXlab platform
Pascal Van Hentenryck - One of the best experts on this subject based on the ideXlab platform.
-
Plénière : Constraint Programming : recent progress and applications
2014Co-Authors: Pascal Van HentenryckAbstract:Since its inception, Constraint Programming has featured novel ways of expressing combinatorial optimization problems and new computational models centered around feasibility; It has also been an integration paradigm, exploiting the strength of various technologies. This talk reviews recent progress in these areas and discusses some innovative applications of Constraint Programming. In particular, it reviews the trends in solver-independent modeling, search, and learning, and highlights applications in routing and scheduling.
-
Domain Views for Constraint Programming
arXiv: Artificial Intelligence, 2014Co-Authors: Pascal Van Hentenryck, Laurent MichelAbstract:Views are a standard abstraction in Constraint Programming: They make it possible to implement a single version of each Constraint, while avoiding to create new variables and Constraints that would slow down propagation. Traditional Constraint-Programming systems provide the concept of {\em variable views} which implement a view of the type $y = f(x)$ by delegating all (domain and Constraint) operations on variable $y$ to variable $x$. This paper proposes the alternative concept of {\em domain views} which only delegate domain operations. Domain views preserve the benefits of variable views but simplify the implementation of value-based propagation. Domain views also support non-injective views compositionally, expanding the scope of views significantly. Experimental results demonstrate the practical benefits of domain views.
-
Constraint Programming
Lecture Notes in Computer Science, 2009Co-Authors: Pascal Van HentenryckAbstract:Constraint Programming is a remarkable success story. It quickly moved from research laboratories to industrial applications in the late 1980s and is in daily use to solve complex optimization throughout the world. At the same time, Constraint Programming has continued to evolve, addressing new needs and opportunities. This talk reviews some recent progress in Constraint Programming. The first part of the talk starts with its fundamental contribution, the ability to express and exploit combinatorial substructures to prune infeasible solutions and find feasible solutions. It also reviews some of the benefits of its architecture on a variety of applications in scheduling, rostering, and combinatorial matching, emphasizing the underlying modeling and computation techniques. The second part of the talk argues that Constraint Programming is an integration technology and reviews some hybridizations of Constraint Programming, including local search, mathematical Programming, and global optimization. The final part of the talk gives a brief overview of some promising, novel applications of Constraint Programming.
-
Transparent Parallelization of Constraint Programming
INFORMS Journal on Computing, 2009Co-Authors: Laurent Michel, Andrew See, Pascal Van HentenryckAbstract:The availability of commodity multicore and multiprocessor machines and the inherent parallelism in Constraint Programming search offer significant opportunities for Constraint Programming. These opportunities also present a fundamental challenge: how to exploit parallelism transparently to speed up Constraint programs. This paper shows how to parallelize Constraint programs transparently without changes to the sequential code. The main technical idea consists of automatically lifting a sequential exploration strategy into its parallel counterpart, allowing workers to share and steal subproblems. Experimental results show that the parallel implementation may produce significant speedups on multicore machines.
-
ECAI - The Impact of Constraint Programming
2008Co-Authors: Pascal Van HentenryckAbstract:Constraint Programming is a success story for artificial intelligence. It quickly moved from research laboratories to industrial applications and is in daily use to solve complex optimization throughout the world. At the same time, Constraint Programming continued to evolve, addressing new needs and opportunities. This talk reviews some recent progress in Constraint Programming, including its hybridization with other optimization approaches, the quest for more autonomous search, and its applications in a variety of nontraditional areas.
Toby Walsh - One of the best experts on this subject based on the ideXlab platform.
-
Stochastic Constraint Programming
arXiv: Artificial Intelligence, 2009Co-Authors: Toby WalshAbstract:To model combinatorial decision problems involving uncertainty and probability, we introduce stochastic Constraint Programming. Stochastic Constraint programs contain both decision variables (which we can set) and stochastic variables (which follow a probability distribution). They combine together the best features of traditional Constraint satisfaction, stochastic integer Programming, and stochastic satisfiability. We give a semantics for stochastic Constraint programs, and propose a number of complete algorithms and approximation procedures. Finally, we discuss a number of extensions of stochastic Constraint Programming to relax various assumptions like the independence between stochastic variables, and compare with other approaches for decision making under uncertainty.
-
Handbook of Constraint Programming
2006Co-Authors: Francesca Rossi, Peter Van Beek, Toby WalshAbstract: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. 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. The intended audience of the handbook is researchers, graduate students, higher-year undergraduates and practitioners who wish to learn about the state-of-the-art in Constraint Programming. No prior knowledge about the field is necessary to be able to read the chapters and gather useful knowledge. Researchers from other fields should find in this handbook an effective way to learn about Constraint Programming and to possibly use some of the Constraint Programming concepts and techniques in their work, thus providing a means for a fruitful cross-fertilization among different research areas. The handbook is organized in two parts. The first part 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. The second part 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. - Covers the whole field of Constraint Programming - Survey-style chapters - Five chapters on applications Table of Contents Foreword (Ugo Montanari) Part I : Foundations Chapter 1. Introduction (Francesca Rossi, Peter van Beek, Toby Walsh) Chapter 2. Constraint Satisfaction: An Emerging Paradigm (Eugene C. Freuder, Alan K. Mackworth) Chapter 3. Constraint Propagation (Christian Bessiere) Chapter 4. Backtracking Search Algorithms (Peter van Beek) Chapter 5. Local Search Methods (Holger H. Hoos, Edward Tsang) Chapter 6. Global Constraints (Willem-Jan van Hoeve, Irit Katriel) Chapter 7. Tractable Structures for CSPs (Rina Dechter) Chapter 8. The Complexity of Constraint Languages (David Cohen, Peter Jeavons) Chapter 9. Soft Constraints (Pedro Meseguer, Francesca Rossi, Thomas Schiex) Chapter 10. Symmetry in Constraint Programming (Ian P. Gent, Karen E. Petrie, Jean-Francois Puget) Chapter 11. Modelling (Barbara M. Smith) Part II : Extensions, Languages, and Applications Chapter 12. Constraint Logic Programming (Kim Marriott, Peter J. Stuckey, Mark Wallace) Chapter 13. Constraints in Procedural and Concurrent Languages (Thom Fruehwirth, Laurent Michel, Christian Schulte) Chapter 14. Finite Domain Constraint Programming Systems (Christian Schulte, Mats Carlsson) Chapter 15. Operations Research Methods in Constraint Programming (John Hooker) Chapter 16. Continuous and Interval Constraints(Frederic Benhamou, Laurent Granvilliers) Chapter 17. Constraints over Structured Domains (Carmen Gervet) Chapter 18. Randomness and Structure (Carla Gomes, Toby Walsh) Chapter 19. Temporal CSPs (Manolis Koubarakis) Chapter 20. Distributed Constraint Programming (Boi Faltings) Chapter 21. Uncertainty and Change (Kenneth N. Brown, Ian Miguel) Chapter 22. Constraint-Based Scheduling and Planning (Philippe Baptiste, Philippe Laborie, Claude Le Pape, Wim Nuijten) Chapter 23. Vehicle Routing (Philip Kilby, Paul Shaw) Chapter 24. Configuration (Ulrich Junker) Chapter 25. Constraint Applications in Networks (Helmut Simonis) Chapter 26. Bioinformatics and Constraints (Rolf Backofen, David Gilbert)
-
ECAI - Stochastic Constraint Programming
2002Co-Authors: Toby WalshAbstract:To model combinatorial decision problems involving uncertainty and probability, we introduce stochastic Constraint Programming. Stochastic Constraint programs contain both decision variables (which we can set) and stochastic variables (which follow a probability distribution). They combine together the best features of traditional Constraint satisfaction, stochastic integer Programming, and stochastic satisfiability. We give a semantics for stochastic Constraint programs, and propose a number of complete algorithms and approximation procedures. Finally, we discuss a number of extensions of stochastic Constraint Programming to relax various assumptions like the independence between stochastic variables, and compare with other approaches for decision making under uncertainty.
Narendra Jussien - One of the best experts on this subject based on the ideXlab platform.
-
solving a real time allocation problem with Constraint Programming
Journal of Systems and Software, 2008Co-Authors: Pierreemmanuel Hladik, Hadrien Cambazard, A M Deplanche, Narendra JussienAbstract:In this paper, we present an original approach (CPRTA for ''Constraint Programming for solving Real-Time Allocation'') based on Constraint Programming to solve a static allocation problem of hard real-time tasks. This problem consists in assigning periodic tasks to distributed processors in the context of fixed priority preemptive scheduling. CPRTA is built on dynamic Constraint Programming together with a learning method to find a feasible processor allocation under Constraints. Two efficient new approaches are proposed and validated with experimental results. Moreover, CPRTA exhibits very interesting properties. It is complete (if a problem has no solution, the algorithm is able to prove it); it is non-parametric (it does not require specific tuning) thus allowing a large diversity of models to be easily considered. Finally, thanks to its capacity to explain failures, it offers attractive perspectives for guiding the architectural design process.
-
Trends in Constraint Programming
2007Co-Authors: Frédéric Benhamou, Narendra Jussien, Barry O'sullivanAbstract:Constraint Programming is a constantly evolving field, something which is explored at the annual International Conference on Principles and Practice of Constraint Programming. This conference provides papers and workshops which produce new insights, concepts and results which those involved in this area can then use to develop their own work. This title provides an accessible overview of this by bringing together the best papers on a range of topics within this subject area, thus allowing those involved in Constraint Programming to benefit from the new innovations and results created as a result of the conference.
-
Trends in Constraint Programming - Trends in Constraint Programming
2007Co-Authors: Frédéric Benhamou, Narendra Jussien, Barry O'sullivanAbstract:Introduction. Part I. The Past, Present and Future of Constraint Programming. Chapter 1. Constraint Programming as Declarative Algorithmics. Chapter 2. Constraint Programming Tools. Chapter 3. The Next 10 Years of Constraint Programming. Chapter 4. Constraint Propagation and Implementation. Chapter 5. On the First SAT/CP Integration Workshop. Chapter 6. Constraint-based Methods for Bioinformatics. Part II. Constraint Modeling and Reformulation. Chapter 7. Improved Models and Reformulation. Chapter 8. The Automatic Generation of Redundant Representations and Channeling Constraints. Part III. Symmetry in Constraint Satisfaction Problems. Chapter 9. GAPLex: Generalized Static Symmetry Breaking. Chapter 10. Symmetry Breaking in Subgraph Pattern Matching. Part IV. Interval Analysis, Constraint Propagation and Applications. Chapter 11. Modeling and Solving of a Radio Antenna Deployment Support Application. Chapter 12. Guaranteed Numerical Injectivity Test via Interval Analysis. Chapter 13. An Interval-based Approximation Method for Discrete Changes in Hybrid cc. Part V. Local Search Techniques in Constraint Satisfaction. Chapter 14. Combining Adaptive Noise and Look-Ahead in Local Search for SAT. Chapter 15. Finding Large Cliques using SAT Local Search. Chapter 16. Multi-Point Constructive Search for Constraint Satisfaction: An Overview. Chapter 17. Boosting SLS Using Resolution. Chapter 18. Growing COMET. Part VI. Preferences and Soft Constraints. Chapter 19. The Logic Behind Weighted CSP. Chapter 20. Dynamic Heuristics for Branch and Bound on Tree-Decomposition of Weighted CSPs. Part VII. Constraints in Software Testing, Verification and Analysis. Chapter 21. Extending a CP Solver with Congruences as Domains for Program Verification. Chapter 22. Generating Random Values Using Binary Decision Diagrams and Convex Polyhedra. Chapter 23. A Symbolic Model for Hash-Collision Attacks. Chapter 24. Strategy for Flaw Detection Based on a Service-driven Model for Group Protocols. Part VIII. Constraint Programming for Graphical Applications. Chapter 25. Trends and Issues in using Constraint Programming for Graphical Applications. Chapter 26. A Constraint Satisfaction Framework for Visual Problem Solving. Chapter 27. Computer Graphics and Constraint Solving: An Application to Virtual Camera Control. Index.
-
allocating hard real time tasks with Constraint Programming
2006Co-Authors: Pierreemmanuel Hladik, Hadrien Cambazard, Narendra JussienAbstract:In this paper, we present an original approach (CPRTA for ”Constraint Programming for solving Real-Time Allocation”) based on Constraint Programming to solve an allocation problem of hard real-time tasks. This problem consists in assigning periodic tasks to distributed processors in the context of fixed priority preemptive scheduling. CPRTA is built on dynamic Constraint Programming together with a learning method to find a feasible processor allocation under Constraints. Two new approaches are proposed for solving these kinds of problems which produce in their current version as acceptable performances as classical algorithms do. Some experimental results are given to show it. Moreover, CPRTA exhibits very interesting properties. It is complete — i.e., if a problem has no solution — the algorithm is able to prove it ; it is non-parametric — i.e., it does not require specific initializations — thus allowing a large diversity of models to be easily considered. Finally, thanks to its capacity to explain failures, it oers attractive perspectives for guiding the architectural design process.
-
The versatility of using explanations within Constraint Programming
2003Co-Authors: Narendra JussienAbstract:Constraint Programming is a research topic benefiting from many other areas: discrete mathematics, numerical analysis, artificial intelligence, operations research, and formal calculus. It has proven its interest and its efficiency in various domains: combinatorial optimization, scheduling, finance, simulation and synthesis, diagnosis, molecular biology, or geometrical problems. However, some limitations and difficulties remain: designing stable and generic algorithms, handling dynamic problems, opening Constraint Programming to non-specialists, etc. In this document, we advocate the use of explanations within Constraint Programming. Our aim is two-fold: drawing the big picture about explanations (definition, generation, management and use) and showing that they can help address several issues in Constraint Programming. We also introduce a new general explanation-based search technique that has been successfully used to design new efficient algorithms. Finally, current open issues and research topics in this field are presented.
Luc De Raedt - One of the best experts on this subject based on the ideXlab platform.
-
The Inductive Constraint Programming Loop
IEEE Intelligent Systems, 2017Co-Authors: Christian Bessiere, Barry O'sullivan, Luc De Raedt, Tias Guns, Lars Kotthoff, Mirco Nanni, Siegfried Nijssen, Anastasia Paparrizou, Dino Pedreschi, Helmut SimonisAbstract:Constraint Programming is used for a variety of real-world optimization problems, such as planning, scheduling, and resource allocation problems, all while we continuously gather vast amounts of data about these problems. Current Constraint Programming software doesn’t exploit such data to update schedules, resources, and plans. The authors propose a new framework that they call the inductive Constraint Programming loop. In this approach, data is gathered and analyzed systematically to dynamically revise and adapt Constraints and optimization criteria. Inductive Constraint Programming aims to bridge the gap between the areas of data mining and machine learning on one hand and Constraint Programming on the other.
-
The Inductive Constraint Programming Loop
arXiv: Artificial Intelligence, 2015Co-Authors: Christian Bessiere, Barry O'sullivan, Luc De Raedt, Tias Guns, Lars Kotthoff, Mirco Nanni, Siegfried Nijssen, Anastasia Paparrizou, Dino Pedreschi, Helmut SimonisAbstract:Constraint Programming is used for a variety of real-world optimisation problems, such as planning, scheduling and resource allocation problems. At the same time, one continuously gathers vast amounts of data about these problems. Current Constraint Programming software does not exploit such data to update schedules, resources and plans. We propose a new framework, that we call the Inductive Constraint Programming loop. In this approach data is gathered and analyzed systematically, in order to dynamically revise and adapt Constraints and optimization criteria. Inductive Constraint Programming aims at bridging the gap between the areas of data mining and machine learning on the one hand, and Constraint Programming on the other hand.
-
Itemset mining: A Constraint Programming perspective
Artificial Intelligence, 2011Co-Authors: Tias Guns, Siegfried Nijssen, Luc De RaedtAbstract:The field of data mining has become accustomed to specifying Constraints on patterns of interest. A large number of systems and techniques has been developed for solving such Constraint-based mining problems, especially for mining itemsets. The approach taken in the field of data mining contrasts with the Constraint Programming principles developed within the artificial intelligence community. While most data mining research focuses on algorithmic issues and aims at developing highly optimized and scalable implementations that are tailored towards specific tasks, Constraint Programming employs a more declarative approach. The emphasis lies on developing high-level modeling languages and general solvers that specify what the problem is, rather than outlining how a solution should be computed, yet are powerful enough to be used across a wide variety of applications and application domains. This paper contributes a declarative Constraint Programming approach to data mining. More specifically, we show that it is possible to employ off-the-shelf Constraint Programming techniques for modeling and solving a wide variety of Constraint-based itemset mining tasks, such as frequent, closed, discriminative, and cost-based itemset mining. In particular, we develop a basic Constraint Programming model for specifying frequent itemsets and show that this model can easily be extended to realize the other settings. This contrasts with typical procedural data mining systems where the underlying procedures need to be modified in order to accommodate new types of Constraint, or novel combinations thereof. Even though the performance of state-of-the-art data mining systems outperforms that of the Constraint Programming approach on some standard tasks, we also show that there exist problems where the Constraint Programming approach leads to significant performance improvements over state-of-the-art methods in data mining and as well as to new insights into the underlying data mining problems. Many such insights can be obtained by relating the underlying search algorithms of data mining and Constraint Programming systems to one another. We discuss a number of interesting new research questions and challenges raised by the declarative Constraint Programming approach to data mining.
-
Constraint Programming for data mining and machine learning
National Conference on Artificial Intelligence, 2010Co-Authors: Luc De Raedt, Tias Guns, Siegfried NijssenAbstract:Machine learning and data mining have become aware that using Constraints when learning patterns and rules can be very useful. To this end, a large number of special purpose systems and techniques have been developed for solving such Constraint-based mining and learning problems. These techniques have, so far, been developed independently of the general purpose tools and principles of Constraint Programming known within the field of artificial intelligence. This paper shows that off-the-shelf Constraint Programming techniques can be applied to various pattern mining and rule learning problems (cf. also (De Raedt, Guns, and Nijssen 2008; Nijssen, Guns, and De Raedt 2009)). This does not only lead to methodologies that are more general and flexible, but also provides new insights into the underlying mining problems that allow us to improve the state-of-the-art in data mining. Such a combination of Constraint Programming and data mining raises a number of interesting new questions and challenges.
-
EGC - Constraint Programming for data mining
2009Co-Authors: Luc De RaedtAbstract:In this talk I shall explore the relationship between Constraint-based mining and Constraint Programming. In particular, I shall show how the typical Constraints used in pattern mining can be formulated for use in Constraint Programming environments. The resulting framework is surprisingly flexible and allows one to combine a wide range of mining Constraints in different ways. The approach is implemented in off-the-shelf Constraint Programming systems and evaluated empirically. The results show that the approach is not only very expressive, but also works well on complex benchmark problems. In addition to providing a detailed account of our actual initial results for item-set mining, I shall also argue that the use of Constraint Programming techniques and methodologies provides a new and interesting paradigm for data mining. The work I will report on is joint work with Tias Guns and Siegfried Nijssen
Barry O'sullivan - One of the best experts on this subject based on the ideXlab platform.
-
The Inductive Constraint Programming Loop
IEEE Intelligent Systems, 2017Co-Authors: Christian Bessiere, Barry O'sullivan, Luc De Raedt, Tias Guns, Lars Kotthoff, Mirco Nanni, Siegfried Nijssen, Anastasia Paparrizou, Dino Pedreschi, Helmut SimonisAbstract:Constraint Programming is used for a variety of real-world optimization problems, such as planning, scheduling, and resource allocation problems, all while we continuously gather vast amounts of data about these problems. Current Constraint Programming software doesn’t exploit such data to update schedules, resources, and plans. The authors propose a new framework that they call the inductive Constraint Programming loop. In this approach, data is gathered and analyzed systematically to dynamically revise and adapt Constraints and optimization criteria. Inductive Constraint Programming aims to bridge the gap between the areas of data mining and machine learning on one hand and Constraint Programming on the other.
-
The Inductive Constraint Programming Loop
arXiv: Artificial Intelligence, 2015Co-Authors: Christian Bessiere, Barry O'sullivan, Luc De Raedt, Tias Guns, Lars Kotthoff, Mirco Nanni, Siegfried Nijssen, Anastasia Paparrizou, Dino Pedreschi, Helmut SimonisAbstract:Constraint Programming is used for a variety of real-world optimisation problems, such as planning, scheduling and resource allocation problems. At the same time, one continuously gathers vast amounts of data about these problems. Current Constraint Programming software does not exploit such data to update schedules, resources and plans. We propose a new framework, that we call the Inductive Constraint Programming loop. In this approach data is gathered and analyzed systematically, in order to dynamically revise and adapt Constraints and optimization criteria. Inductive Constraint Programming aims at bridging the gap between the areas of data mining and machine learning on the one hand, and Constraint Programming on the other hand.
-
AAAI - Opportunities and challenges for Constraint Programming
2012Co-Authors: Barry O'sullivanAbstract:Constraint Programming has become an important technology for solving hard combinatorial problems in a diverse range of application domains. It has its roots in artificial intelligence, mathematical Programming, operations research, and Programming languages. This paper gives a perspective on where Constraint Programming is today, and discusses a number of opportunities and challenges that could provide focus for the research community into the future.
-
AAAI - Automated modelling and solving in Constraint Programming
2010Co-Authors: Barry O'sullivanAbstract:Constraint Programming can be divided very crudely into modeling and solving. Modeling defines the problem, in terms of variables that can take on different values, subject to restrictions (Constraints) on which combinations of variables are allowed. Solving finds values for all the variables that simultaneously satisfy all the Constraints. However, the impact of Constraint Programming has been constrained by a lack of "user-friendliness". Constraint Programming has a major "declarative" aspect, in that a problem model can be handed off for solution to a variety of standard solving methods. These methods are embedded in algorithms, libraries, or specialized Constraint Programming languages. To fully exploit this declarative opportunity however, we must provide more assistance and automation in the modeling process, as well as in the design of application-specific problem solvers. Automated modelling and solving in Constraint Programming presents a major challenge for the artificial intelligence community. Artificial intelligence, and in particular machine learning, is a natural field in which to explore opportunities for moving more of the burden of Constraint Programming from the user to the machine. This paper presents technical challenges in the areas of Constraint model acquisition, formulation and reformulation, synthesis of filtering algorithms for global Constraints, and automated solving. We also present the metrics by which success and progress can be measured.
-
Trends in Constraint Programming
2007Co-Authors: Frédéric Benhamou, Narendra Jussien, Barry O'sullivanAbstract:Constraint Programming is a constantly evolving field, something which is explored at the annual International Conference on Principles and Practice of Constraint Programming. This conference provides papers and workshops which produce new insights, concepts and results which those involved in this area can then use to develop their own work. This title provides an accessible overview of this by bringing together the best papers on a range of topics within this subject area, thus allowing those involved in Constraint Programming to benefit from the new innovations and results created as a result of the conference.