In this paper we present and evaluate an evolutionary approach for learning new constraint satisfaction algorithms, specifically for MAX-SAT optimisation problems. Our approach offers two significant advantages over e...
详细信息
ISBN:
(纸本)3540292381
In this paper we present and evaluate an evolutionary approach for learning new constraint satisfaction algorithms, specifically for MAX-SAT optimisation problems. Our approach offers two significant advantages over existing methods: it allows the evolution of more complex combinations of heuristics, and;it can identify fruitful synergies among heuristics. Using four different classes of MAX-SAT problems, we experimentally demonstrate that algorithms evolved withthis method exhibit superior performance in comparison to general purpose methods.
Engineering conceptual design can be defined as that phase of the product development process during which the designer takes a specification for a product to be designed and generates many broad solutions for it. It ...
详细信息
ISBN:
(纸本)3540202021
Engineering conceptual design can be defined as that phase of the product development process during which the designer takes a specification for a product to be designed and generates many broad solutions for it. It is well recognized that few computational tools exist that are capable of supporting the designer work through the conceptual phase of design. However, significant recent developments have been made in solid modeling and 3D computer-aided design. the use of such tools has become a critical element in the more sophisticated product development processes to be found in modem industry. this paper presents a prototype constraint-based computer-aided design (CAD) technology that can be used to support designers working in the early stages of design. the technology has been developed as an add-in application for Autodesk Inventor, a 3D solid-modeling environment. the add-in has, at its core, a constraint filtering system based on generalised arc-consistency processing and backtrack search. We present our current prototype and a detailed demonstration of its functionality. Finally, we describe our current work on a number of additional features for the next prototype, which will be deployed in an industrial context.
tIn this paper we give an overview of applications of constraintprogramming for IP (Internet Protocol) data networks, and discuss the problem of Resilience Analysis in more detail. In this problem we try to predict t...
详细信息
ISBN:
(纸本)3540462678
tIn this paper we give an overview of applications of constraintprogramming for IP (Internet Protocol) data networks, and discuss the problem of Resilience Analysis in more detail. In this problem we try to predict the loading of a network in different failure scenarios, without knowing end-to-end flow values throughout the network;the inference is based only on observed link traffic values. the related problem of Traffic Flow Analysis aims to derive a traffic matrix from the observed link traffic data. this is a severely under-constrained problem, we can show that the obtained flow values vary widely in different, feasible solutions. Experimental results indicate that using the same data much more accurate, bounded results can be obtained for Resilience Analysis.
the problem of finding an optimal solution in a constraint satisfaction problem with preferences has attracted a lot of researchers in Artificial Intelligence in general, and in the constraintprogramming community in...
详细信息
ISBN:
(纸本)9783540859574
the problem of finding an optimal solution in a constraint satisfaction problem with preferences has attracted a lot of researchers in Artificial Intelligence in general, and in the constraintprogramming community in particular. As a consequence, several approaches for expressing and reasoning about satisfiability problems with preferences have been proposed, and viable solutions exist for finding one optimal Solution. However, in many cases, it is not desirable to find just one solution. Indeed, it might be desirable to he able to compute more, and possibly all, optimal solutions, e.g.. for comparatively evaluate them on the basis of other criteria not captured by the preferences. In this paper we present a procedure for computing all optimal solutions of a satisfiability problem with preferences. the procedure is guaranteed to compute all and only the optimal solutions, i.e., models which are not optimal are not even computed.
We propose a new filtering algorithm for the cumulative constraint. It applies the Edge-Finding, the Extended-Edge-Finding and the Time-Tabling rules in O(kn log n) where k is the number of distinct task heights. By a...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
We propose a new filtering algorithm for the cumulative constraint. It applies the Edge-Finding, the Extended-Edge-Finding and the Time-Tabling rules in O(kn log n) where k is the number of distinct task heights. By a proper use of tasks decomposition, it enforces the Time-Tabling rule and the Time-Table Extended-Edge-Finding rule. thus our algorithm improves upon the best known Extended-Edge-Finding propagator by a factor of O(log n) while achieving a much stronger filtering.
We show in this article(1) how the Weighted CSP framework can be used to solve an optimisation version of numerical planning. the WCSP finds an optimal plan in the planning graph containing all solution plans of minim...
详细信息
ISBN:
(纸本)3540462678
We show in this article(1) how the Weighted CSP framework can be used to solve an optimisation version of numerical planning. the WCSP finds an optimal plan in the planning graph containing all solution plans of minimum length. Experimental trials were performed to study the impact of soft arc consistency techniques (FDAC and EDAC) on the efficiency of the search for an optimal plan in this graph. We conclude by giving a possible theoretical explanation for the fact that we were able to solve optimisation problems involving several hundred variables.
We improve an existing propagator for the context-free grammar constraint and demonstrate experimentally the practicality of the resulting propagator. the underlying technique could be applied to other existing propag...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
We improve an existing propagator for the context-free grammar constraint and demonstrate experimentally the practicality of the resulting propagator. the underlying technique could be applied to other existing propagators for this constraint. We argue that constraintprogramming solvers are more suitable than existing solvers for verification tools that have to solve string constraints, as they have a rich tradition of constraints for membership in formal languages.
We propose new filtering algorithms for the SEQUENCE constraint and some extensions of the SEQUENCE constraint based on network flows. We enforce domain consistency on the SEQUENCE constraint in O(n(2)) time down a br...
详细信息
ISBN:
(纸本)9783540859574
We propose new filtering algorithms for the SEQUENCE constraint and some extensions of the SEQUENCE constraint based on network flows. We enforce domain consistency on the SEQUENCE constraint in O(n(2)) time down a branch of the search tree. this improves upon the best existing domain consistency algorithm by a factor of O(log n). the flows used in these algorithms are derived from a linear program. Some of them differ from the flows used to propagate global constraints like GCC since the domains of the variables are encoded as costs on the edges rather than capacities. Such flows are efficient for maintaining bounds consistency over large domains and may be useful for other global constraints.
In practice, constraint satisfaction problems are often structured. By exploiting this structure, solving algorithms can make important gains in performance. In this paper, we focus on structured continuous CSPs defin...
详细信息
ISBN:
(纸本)3540652248
In practice, constraint satisfaction problems are often structured. By exploiting this structure, solving algorithms can make important gains in performance. In this paper, we focus on structured continuous CSPs defined by systems of equations. We use graph decomposition techniques to decompose the constraint graph into a directed acyclic graph of small blocks. We present new algorithms to solve decomposed problems which solve the blocks in partial order and perform intelligent backtracking when a block has no solution. For under-constrained problems, the solution space can be explored by choosing some variables as input parameters. However, in this case, the decomposition is no longer unique and some choices lead to decompositions with smaller blocks than others. We present an algorithm for selecting the input parameters that lead to good decompositions. First experimental results indicate that, even on small problems, significant speedups can be obtained using these algorithms.
the Patient Transportation Problem (PTP) aims to bring patients to health centers and to take them back home once the care has been delivered. All the requests are known beforehand and a schedule is built the day befo...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
the Patient Transportation Problem (PTP) aims to bring patients to health centers and to take them back home once the care has been delivered. All the requests are known beforehand and a schedule is built the day before its use. It is a variant of the well-known Dial-a-Ride Problem (DARP) but it has nevertheless some characteristics that complicate the decision process. three levels of decisions are considered: selecting which requests to service, assigning vehicles to requests and routing properly the vehicles. In this paper, we propose a constraintprogramming approach to solve the Patient Transportation Problem. the model is designed to be flexible enough to accommodate new constraints and objective functions. Furthermore, we introduce a generic search strategy to maximize efficiently the number of selected requests. Our results show that the model can solve real life instances and outperforms greedy strategies typically performed by human schedulers.
暂无评论