constraint programming (CP) allows to solve constraint satisfaction and optimization problems by building and then exploring a search tree of potential solutions. Potential solutions are generated by firstly selecting...
详细信息
ISBN:
(纸本)9781467398176
constraint programming (CP) allows to solve constraint satisfaction and optimization problems by building and then exploring a search tree of potential solutions. Potential solutions are generated by firstly selecting a variable and then a value from the given problem, phase known as enumeration. In this context, Autonomous Search (AS) that is a particular case of adaptive systems, enables the problem solver to control and adapt its internal configuration during solving time, based on performance metrics in order to be more efficient. The goal is to provide a mechanism for CP solvers, integrating a component able to evaluate the solving performance process. In particular, we employ a classic decision making method called Choice Function (CF). In this paper, we present an evaluation of different choice functions, based on performance exhibited in a indicators set. The results are promising and show that it is feasible to solve constraint satisfaction problems with this new technique.
constraint programming allows to solve constraint satisfaction and optimization problems by building and then exploring a search tree of potential solutions. Potential solutions are generated by firstly selecting a va...
详细信息
ISBN:
(纸本)9783319184760;9783319184753
constraint programming allows to solve constraint satisfaction and optimization problems by building and then exploring a search tree of potential solutions. Potential solutions are generated by firstly selecting a variable and then a value from the given problem. The enumeration strategy is responsible for selecting the order in which those variables and values are selected to produce a potential solution. There exist different ways to perform this selection, and depending on the quality of this decision, the efficiency of the solving process may dramatically vary. A main concern in this context is that the behavior of the strategy is notably hard to predict. In this paper, we present a performance evaluation of 24 enumeration strategies for solving constraint satisfaction problems. Our goal is to provide new and interesting knowledge about the behavior of such strategies. To this end, we employ a set of wellknown benchmarks that collect general features that may be present on most constraint satisfaction and optimization problems. We believe this information will be useful to help users making better solving decisions when facing new problems.
Distributed real-time systems such as automotive applications are becoming larger and more complex, thus, requiring the use of more powerful hardware and software architectures. Furthermore, those distributed applicat...
详细信息
ISBN:
(纸本)9783319160863;9783319160856
Distributed real-time systems such as automotive applications are becoming larger and more complex, thus, requiring the use of more powerful hardware and software architectures. Furthermore, those distributed applications commonly have stringent real-time constraints. This implies that such applications would gain in flexibility if they were parallelized and distributed over the system. In this paper, we consider the problem of allocating fixed-priority fork-join Parallel/Distributed real-time tasks onto distributed multi-core nodes connected through a Flexible Time Triggered Switched Ethernet network. We analyze the system requirements and present a set of formulations based on a constraint programming approach. constraint programming allows us to express the relations between variables in the form of constraints. Our approach is guaranteed to find a feasible solution, if one exists, in contrast to other approaches based on heuristics. Furthermore, approaches based on constraint programming have shown to obtain solutions for these type of formulations in reasonable time.
We report our solution to the problem of designing test-site chips. This is a specific variation of the VLSI floorplanning problem where rectangular macros must be placed without overlap in a given area, but no wiring...
详细信息
ISBN:
(数字)9783319180083
ISBN:
(纸本)9783319180083;9783319180076
We report our solution to the problem of designing test-site chips. This is a specific variation of the VLSI floorplanning problem where rectangular macros must be placed without overlap in a given area, but no wiring between the macros exists. Typically, industrial problems of this type require placing hundreds of macros of different sizes and shapes and include additional constraints such as fixing or grouping some of the macros. Many tools and techniques developed to solve similar problems proved unsuitable for this specific variation. We used constraint programming (CP) with additional heuristics, including sophisticated variable and value orderings, to produce floorplans for real test-sites. Our CP solution is successfully used in production by test-site designers.
In robot localization problems, uncertainty arises from many factors and must be considered together with the model constraints. Probabilistic robotics is the classical approach for dealing with hard robotic problems ...
详细信息
ISBN:
(纸本)9783319234854;9783319234847
In robot localization problems, uncertainty arises from many factors and must be considered together with the model constraints. Probabilistic robotics is the classical approach for dealing with hard robotic problems that relies on probability theory. This work describes the application of probabilistic constraint techniques in the context of probabilistic robotics to solve robot localization problems. Instead of providing the most probable position of the robot, the approach characterizes all positions consistent with the model and their probabilities (in accordance with the underlying uncertainty). It relies on constraint programming to get a tight covering of the consistent regions combined with Monte Carlo integration techniques that benefit from such reduction of the sampling space.
Feature modeling is of paramount importance to capture variabilities and commonalities within a software product line. Nevertheless, current feature modeling notations are limited, representing only propositional form...
详细信息
ISBN:
(纸本)9789897581397
Feature modeling is of paramount importance to capture variabilities and commonalities within a software product line. Nevertheless, current feature modeling notations are limited, representing only propositional formulae over attributed variables. This position paper advocates the extension of feature modeling formalisms with richer computational domains and relational operations. In particular, it proposes to extend feature modeling with finite and continuous domain variables, with first-order logic quantifiers (for all,there exists), and with N-ary relations between features attributes, and with so-called global constraints. In order to extend the expressiveness while preserving automated analysis facilities, feature models could be semantically interpreted as first-order logic formulae (instead of propositional logic formulae), including global and continuous dependency between features. In simpler words, this paper emphasizes the importance of having more relational feature models and presents next-generation applications.
The search of frequent patterns in a transaction database is a well-known problem in the field of data mining. Several specific methods for solving this problem and its variants have been developed in the data mining ...
详细信息
ISBN:
(纸本)9783319258409;9783319258393
The search of frequent patterns in a transaction database is a well-known problem in the field of data mining. Several specific methods for solving this problem and its variants have been developed in the data mining community. A generic and declarative alternative approach to these targeted and specific methods was recently introduced. It consists in representing the data mining problems as constraint networks, then use an appropriate solver as a black box to solve the encoded problem. For instance, several works expressed the frequent itemset mining problem and its variants as constraint networks or Boolean satisfiability, and thus offer the possibility of using the associated efficient solvers to solve the problem. On the other hand, the symmetry notion was very invested and shown to be efficient in the fields of constraint programming and propositional satisfiability. The principle of symmetry could be exported to other areas where some structures can be exploited effectively. Especially, in the field of data mining where several tasks can be expressed as constraint networks. In this work, we propose a generic and declarative method to eliminate symmetries in data mining problems expressed as Boolean constraints. We show how the symmetries between items of a transaction database can be detected and eliminated by adding symmetries breaking predicates (SBP) to the Boolean encoding of the considered data mining problem.
constraint satisfaction problems can be expressed very elegantly in state-based formal methods such as B. However, can such specifications be directly used for solving real-life problems? We will try and answer this q...
详细信息
ISBN:
(纸本)9783319192499;9783319192482
constraint satisfaction problems can be expressed very elegantly in state-based formal methods such as B. However, can such specifications be directly used for solving real-life problems? We will try and answer this question in the present paper with regard to the university timetabling problem. We report on an ongoing project to build a formal model-based curriculum timetable validation tool where we use a formal specification as the basis to validate timetables from a student's perspective and to support incremental modification of timetables. In this article we focus on expressing the problem domain, the formalization in B and our approach to execute the formal model in a production system using ProB.
This paper highlights the current usability issues when solving Sudoku problems. This problem is a well-known puzzle game which consists in assigning numbers in a game board, commonly of 9 x 9 size. The board of the g...
详细信息
ISBN:
(纸本)9783319213804;9783319213798
This paper highlights the current usability issues when solving Sudoku problems. This problem is a well-known puzzle game which consists in assigning numbers in a game board, commonly of 9 x 9 size. The board of the game is composed of 9 columns, 9 rows and 9 3 x 3 sub-grids;each one containing 9 cells with distinct integers from 1 to 9. A game is completed when all cells have a value assigned, and the previous constraints are satisfied. Some instances are very difficult to solve, to tackle this issue, we have used a filtering technique named Arc Consistency 3 (AC3) from the constraint programming domain. This algorithm has revealed which is much related to the strategies employed by users in order to solve the Sudoku instances, but in contrast, this technique is executed in a short time, offering a good resolution guide to the users. In general, filtering techniques make easier solving Sudoku puzzles, providing good information to users for this.
Computational Protein Design aims at rationally designing amino-acid sequences that fold into a given three-dimensional structure and that will bestow the designed protein with desirable properties/functions. Usual cr...
详细信息
ISBN:
(纸本)9783319181677;9783319181660
Computational Protein Design aims at rationally designing amino-acid sequences that fold into a given three-dimensional structure and that will bestow the designed protein with desirable properties/functions. Usual criteria for design include stability of the designed protein and affinity between it and a ligand of interest. However, estimating the affinity between two molecules requires to compute the partition function, a #P-complete problem. Because of its extreme computational cost, bio-physicists have designed the K* algorithm, which combines Best-First A* search with dominance analysis to provide an estimate of the partition function with deterministic guarantees of quality. In this paper, we show that it is possible to speed up search and keep reasonable memory requirement using a Cost Function Network approach combining Depth First Search with arc consistency based lower bounds. We describe our algorithm and compare our first results to the CPD-dedicated software Osprey 2.0.
暂无评论