The Experts below are selected from a list of 6549 Experts worldwide ranked by ideXlab platform
Christopher J Beck - One of the best experts on this subject based on the ideXlab platform.
-
a Global Constraint for total weighted completion time for unary resources
Constraints - An International Journal, 2011Co-Authors: András Kovács, Christopher J BeckAbstract:We introduce a novel Global Constraint for the total weighted completion time of activities on a single unary capacity resource. For propagating the Constraint, we propose an O(n 4) algorithm which makes use of the preemptive mean busy time relaxation of the scheduling problem. The solution to this problem is used to test if an activity can start at each start time in its domain in solutions that respect the upper bound on the cost of the schedule. Empirical results show that the proposed Global Constraint significantly improves the performance of Constraint-based approaches to single-machine scheduling for minimizing the total weighted completion time. We then apply the Constraint to the multi-machine job shop scheduling problem with total weighted completion time. Our experiments show an order of magnitude reduction in search effort over the standard weighted-sum Constraint and demonstrate that the way in which the job weights are associated with activities is important for performance.
-
a Global Constraint for total weighted completion time for cumulative resources
Engineering Applications of Artificial Intelligence, 2008Co-Authors: András Kovács, Christopher J BeckAbstract:The criterion of total weighted completion time occurs as a sub-problem of combinatorial optimization problems in such diverse areas as scheduling, container loading and storage assignment in warehouses. These applications often necessitate considering a rich set of requirements and preferences, which makes Constraint programming (CP) an effective modeling and solving approach. On the other hand, basic CP techniques can be inefficient in solving models that require inference over sum type expressions. In this paper, we address increasing the solution efficiency of Constraint-based approaches to cumulative resource scheduling with the above criterion. Extending previous results for unary capacity resources, we define the COMPLETION"m Global Constraint for propagating the total weighted completion time of activities that require the same cumulative resource. We present empirical results in two different problem domains: scheduling a single cumulative resource, and container loading with Constraints on the location of the center of gravity. In both domains, the proposed Constraint propagation algorithm out-performs existing propagation techniques.
András Kovács - One of the best experts on this subject based on the ideXlab platform.
-
a Global Constraint for total weighted completion time for unary resources
Constraints - An International Journal, 2011Co-Authors: András Kovács, Christopher J BeckAbstract:We introduce a novel Global Constraint for the total weighted completion time of activities on a single unary capacity resource. For propagating the Constraint, we propose an O(n 4) algorithm which makes use of the preemptive mean busy time relaxation of the scheduling problem. The solution to this problem is used to test if an activity can start at each start time in its domain in solutions that respect the upper bound on the cost of the schedule. Empirical results show that the proposed Global Constraint significantly improves the performance of Constraint-based approaches to single-machine scheduling for minimizing the total weighted completion time. We then apply the Constraint to the multi-machine job shop scheduling problem with total weighted completion time. Our experiments show an order of magnitude reduction in search effort over the standard weighted-sum Constraint and demonstrate that the way in which the job weights are associated with activities is important for performance.
-
a Global Constraint for total weighted completion time for cumulative resources
Engineering Applications of Artificial Intelligence, 2008Co-Authors: András Kovács, Christopher J BeckAbstract:The criterion of total weighted completion time occurs as a sub-problem of combinatorial optimization problems in such diverse areas as scheduling, container loading and storage assignment in warehouses. These applications often necessitate considering a rich set of requirements and preferences, which makes Constraint programming (CP) an effective modeling and solving approach. On the other hand, basic CP techniques can be inefficient in solving models that require inference over sum type expressions. In this paper, we address increasing the solution efficiency of Constraint-based approaches to cumulative resource scheduling with the above criterion. Extending previous results for unary capacity resources, we define the COMPLETION"m Global Constraint for propagating the total weighted completion time of activities that require the same cumulative resource. We present empirical results in two different problem domains: scheduling a single cumulative resource, and container loading with Constraints on the location of the center of gravity. In both domains, the proposed Constraint propagation algorithm out-performs existing propagation techniques.
-
CPAIOR - A Global Constraint for Total Weighted Completion Time
Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2007Co-Authors: András Kovács, J. Christopher BeckAbstract:We introduce a novel Global Constraint for the total weighted completion time of activities on a single unary capacity resource. For propagating the Constraint, an O(n4) algorithm is proposed, which makes use of the preemptive mean busy time relaxation of the scheduling problem. The solution to this problem is used to test if an activity can start at each start time in its domain in solutions that respect the upper bound on the cost of the schedule. Empirical results show that the proposed Global Constraint significantly improves the performance of Constraint-based approaches to single-machine scheduling for minimizing the total weighted completion time. Since our eventual goal is to use the Global Constraint as part of a larger optimization problem, we view this performance as very promising. We also sketch the application of the Global Constraint to cumulative resources and to problems with multiple machines.
Helmut Simonis - One of the best experts on this subject based on the ideXlab platform.
-
Global Constraint catalog volume ii time series Constraints
arXiv: Artificial Intelligence, 2016Co-Authors: Ekaterina Arafailova, Nicolas Beldiceanu, Mats Carlsson, Remi Douence, Pierre Flener, Maria Andreina Francisco Rodriguez, Justin Pearson, Helmut SimonisAbstract:First this report presents a restricted set of finite transducers used to synthesise structural time-series Constraints described by means of a multi-layered function composition scheme. Second it provides the corresponding synthesised catalogue of structural time-series Constraints where each Constraint is explicitly described in terms of automata with registers.
-
Analysis and Visualization Tools for Constraint Programming - Complex Constraint Abstraction: Global Constraint Visualisation
Analysis and Visualization Tools for Constraint Programming, 2016Co-Authors: Helmut Simonis, Nicolas Beldiceanu, Abderrahmane Aggoun, Eric BourreauAbstract:In this chapter we describe visualisation tools for Global Constraints in the CHIP system. These tools help to understand the behaviour of different Global Constraints, the core feature of the CHIP Constraint language. The tools follow a general classification scheme for the use of Global Constraints in Global Constraint concepts. Each concept captures the use of a Constraint for a particular type of problem, which can be visualised in a specific way. The different visualisers form a class structure of CHIP++ objects, and can be extended or modified by rewriting some callback predicates.
-
a model seeker extracting Global Constraint models from positive examples
Principles and Practice of Constraint Programming, 2012Co-Authors: Nicolas Beldiceanu, Helmut SimonisAbstract:We describe a system which generates finite domain Constraint models from positive example solutions, for highly structured problems. The system is based on the Global Constraint catalog, providing the library of Constraints that can be used in modeling, and the Constraint Seeker tool, which finds a ranked list of matching Constraints given one or more sample call patterns. We have tested the modeler with 230 examples, ranging from 4 to 6,500 variables, using between 1 and 7,000 samples. These examples come from a variety of domains, including puzzles, sports-scheduling, packing & placement, and design theory. When comparing against manually specified "canonical" models for the examples, we achieve a hit rate of 50%, processing the complete benchmark set in less than one hour on a laptop. Surprisingly, in many cases the system finds usable candidate lists even when working with a single, positive example.
-
Building Global Constraint models from positive examples
2012Co-Authors: Helmut Simonis, Nicolas BeldiceanuAbstract:We present a system which generates Global Constraint models from few positive examples of problem solutions. In contrast to previous Constraint acquisition work, we present a novel approach based on the Global Constraint catalog and the Constraint Seeker tool which generates models for problems which can be expressed as regular conjunctions of similar Constraints. Our system first generates regular groupings of variables in the given samples. The Constraint Seeker is then used to find ranked, typical Constraints which match all given positive examples. A dominance check, which removes implied Constraints based on meta-data in the Constraint catalog, leads to a final ranked set of candidate Constraints for each problem. The system is implemented in SICStus Prolog, and heavily relies on the Constraint description and evaluators in the Global Constraint catalog. We show results for more than 200 example problems, ranging from puzzles to sports scheduling, placement and layout problems. The problems range from 4 to over 6000 variables, and use between one and 7000 samples, utilizing over 50 Global Constraints of the catalog. We achieve an overall hit-rate of about 50%.
-
a Constraint seeker finding and ranking Global Constraints from examples
Principles and Practice of Constraint Programming, 2011Co-Authors: Nicolas Beldiceanu, Helmut SimonisAbstract:In this paper we describe a Constraint Seeker application which provides a web interface to search for Global Constraints in the Global Constraint catalog, given positive and negative, fully instantiated (ground) examples. Based on the given instances the tool returns a ranked list of matching Constraints, the rank indicating whether the Constraint is likely to be the intended Constraint of the user. We give some examples of use cases and generated output, describe the different elements of the search and ranking process, discuss the role of Constraint programming in the different tools used, and provide evaluation results over the complete Global Constraint catalog. The Constraint Seeker is an example for the use of generic meta-data provided in the catalog to solve a specific problem.
Thierry Charnois - One of the best experts on this subject based on the ideXlab platform.
-
Prefix-projection Global Constraint and top-k approach for sequential pattern mining
Constraints, 2017Co-Authors: Amina Kemmar, Samir Loudni, Yahia Lebbah, Patrice Boizumault, Thierry CharnoisAbstract:Sequential pattern mining (SPM) is an important data mining problem with broad applications. SPM is a hard problem due to the huge number of intermediate subsequences to be considered. State of the art approaches for SPM (e.g., PrefixSpan Pei et al. 2001 ) are largely based on the pattern-growth approach, where for each frequent prefix subsequence, only its related suffix subsequences need to be considered, and the database is recursively projected into smaller ones. Many authors have promoted the use of Constraints to focus on the most promising patterns according to the interests of the end user. The top- k SPM problem is also used to cope with the difficulty of thresholding and to control the number of solutions. State of the art methods developed for SPM and top- k SPM, though efficient, are locked into a rather rigid search strategy, and suffer from the lack of declarativity and flexibility. Indeed, adding new Constraints usually amounts to changing the data-structures used in the core of the algorithm, and combining these new Constraints often require new developments. Recent works (e.g. Kemmar et al. 2014 ; Négrevergne and Guns 2015 ) have investigated the use of Constraint Programming (CP) for SPM. However, despite their nice declarative aspects, all these modelings have scaling problems, due to the huge size of their Constraint networks. To address this issue, we propose the Prefix-Projection Global Constraint, which encapsulates both the subsequence relation as well as the frequency Constraint. Its filtering algorithm relies on the principle of projected databases which allows to keep in the variables domain, only values leading to a frequent pattern in the database. Prefix-Projection filtering algorithm enforces domain consistency on the variable succeeding the current frequent prefix in polynomial time. This Global Constraint also allows for a straightforward implementation of additional Constraints such as size, item membership, regular expressions and any combination of them. Experimental results show that our approach clearly outperforms existing CP approaches and competes well with the state-of-the-art methods on large datasets for mining frequent sequential patterns, sequential patterns under various Constraints, and top- k sequential patterns. Unlike existing CP methods, our approach achieves a better scalability.
-
prefix projection Global Constraint and top k approach for sequential pattern mining
Constraints - An International Journal, 2017Co-Authors: Amina Kemmar, Samir Loudni, Yahia Lebbah, Patrice Boizumault, Thierry CharnoisAbstract:Sequential pattern mining (SPM) is an important data mining problem with broad applications. SPM is a hard problem due to the huge number of intermediate subsequences to be considered. State of the art approaches for SPM (e.g., PrefixSpan Pei et al. 2001) are largely based on the pattern-growth approach, where for each frequent prefix subsequence, only its related suffix subsequences need to be considered, and the database is recursively projected into smaller ones. Many authors have promoted the use of Constraints to focus on the most promising patterns according to the interests of the end user. The top-k SPM problem is also used to cope with the difficulty of thresholding and to control the number of solutions. State of the art methods developed for SPM and top-k SPM, though efficient, are locked into a rather rigid search strategy, and suffer from the lack of declarativity and flexibility. Indeed, adding new Constraints usually amounts to changing the data-structures used in the core of the algorithm, and combining these new Constraints often require new developments. Recent works (e.g. Kemmar et al. 2014; Negrevergne and Guns 2015) have investigated the use of Constraint Programming (CP) for SPM. However, despite their nice declarative aspects, all these modelings have scaling problems, due to the huge size of their Constraint networks. To address this issue, we propose the Prefix-Projection Global Constraint, which encapsulates both the subsequence relation as well as the frequency Constraint. Its filtering algorithm relies on the principle of projected databases which allows to keep in the variables domain, only values leading to a frequent pattern in the database. Prefix-Projection filtering algorithm enforces domain consistency on the variable succeeding the current frequent prefix in polynomial time. This Global Constraint also allows for a straightforward implementation of additional Constraints such as size, item membership, regular expressions and any combination of them. Experimental results show that our approach clearly outperforms existing CP approaches and competes well with the state-of-the-art methods on large datasets for mining frequent sequential patterns, sequential patterns under various Constraints, and top-k sequential patterns. Unlike existing CP methods, our approach achieves a better scalability.
-
CPAIOR - A Global Constraint for Mining Sequential Patterns with GAP Constraint
Integration of AI and OR Techniques in Constraint Programming, 2016Co-Authors: Amina Kemmar, Samir Loudni, Yahia Lebbah, Patrice Boizumault, Thierry CharnoisAbstract:Sequential pattern mining (SPM) under gap Constraint is a challenging task. Many efficient specialized methods have been developed but they are all suffering from a lack of genericity. The Constraint Programming (CP) approaches are not so effective because of the size of their encodings. In [7], we have proposed the Global Constraint Prefix-Projection for SPM which remedies to this drawback. However, this Global Constraint cannot be directly extended to support gap Constraint. In this paper, we propose the Global Constraint GAP-SEQ enabling to handle SPM with or without gap Constraint. GAP-SEQ relies on the principle of right pattern extensions. Experiments show that our approach clearly outperforms both CP approaches and the state-of-the-art cSpade method on large datasets.
-
a Global Constraint for mining sequential patterns with gap Constraint
arXiv: Artificial Intelligence, 2015Co-Authors: Amina Kemmar, Samir Loudni, Yahia Lebbah, Patrice Boizumault, Thierry CharnoisAbstract:Sequential pattern mining (SPM) under gap Constraint is a challenging task. Many efficient specialized methods have been developed but they are all suffering from a lack of genericity. The Constraint Programming (CP) approaches are not so effective because of the size of their encodings. In[7], we have proposed the Global Constraint Prefix-Projection for SPM which remedies to this drawback. However, this Global Constraint cannot be directly extended to support gap Constraint. In this paper, we propose the Global Constraint GAP-SEQ enabling to handle SPM with or without gap Constraint. GAP-SEQ relies on the principle of right pattern extensions. Experiments show that our approach clearly outperforms both CP approaches and the state-of-the-art cSpade method on large datasets.
-
prefix projection Global Constraint for sequential pattern mining
arXiv: Artificial Intelligence, 2015Co-Authors: Amina Kemmar, Samir Loudni, Yahia Lebbah, Patrice Boizumault, Thierry CharnoisAbstract:Sequential pattern mining under Constraints is a challenging data mining task. Many efficient ad hoc methods have been developed for mining sequential patterns, but they are all suffering from a lack of genericity. Recent works have investigated Constraint Programming (CP) methods, but they are not still effective because of their encoding. In this paper, we propose a Global Constraint based on the projected databases principle which remedies to this drawback. Experiments show that our approach clearly outperforms CP approaches and competes well with ad hoc methods on large datasets.
J. Christopher Beck - One of the best experts on this subject based on the ideXlab platform.
-
SARA - Modeling, Global Constraints, and Decomposition
2013Co-Authors: J. Christopher BeckAbstract:Unlike mathematical programming and SAT solving, ConstraintProgramming (CP) is based on the idea that both modeling and solving of combinatorial optimization problems can be based on conjunctions of loosely coupled, recurring, combinatorial sub-problems (aka "Global Constraints"). This rich representational approach means that, for better or for worse, pretty much anything can be expressed as a Global Constraint. Much of CP's success, however, has come from exploiting only one aspect of the rich Constraint definition: Global Constraint propagation. In this talk, I will investigate how work in CP, SAT, AI planning, and mathematical programming can be understood as more seriously pursuing the implications of a rich Constraint definition and how the interplay between local and Global information can lead to dynamic problem reformulations and a flexible hybrid solver architecture.
-
CPAIOR - A Global Constraint for Total Weighted Completion Time
Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2007Co-Authors: András Kovács, J. Christopher BeckAbstract:We introduce a novel Global Constraint for the total weighted completion time of activities on a single unary capacity resource. For propagating the Constraint, an O(n4) algorithm is proposed, which makes use of the preemptive mean busy time relaxation of the scheduling problem. The solution to this problem is used to test if an activity can start at each start time in its domain in solutions that respect the upper bound on the cost of the schedule. Empirical results show that the proposed Global Constraint significantly improves the performance of Constraint-based approaches to single-machine scheduling for minimizing the total weighted completion time. Since our eventual goal is to use the Global Constraint as part of a larger optimization problem, we view this performance as very promising. We also sketch the application of the Global Constraint to cumulative resources and to problems with multiple machines.