共查询到20条相似文献,搜索用时 187 毫秒
1.
Constraint Programming (CP) allows to model and solve combinatory problems by specifying some partial information on variables, unknowns of the problem. We have studied musical constraint problems, either stated by contemporary composers, or of musical analysis, or instrumentation, in collaboration with IRCAM (french Institute for Research and Coordination Acoustics / Music). Fourteen such problems have been modeled and solved, which allowed to give a detailed typology. This has been used to conceive and implement OMClouds, a library in the Computer Assisted Composition environment OpenMusic. It is based on a local search algorithm called adaptive search. Its architecture allows in particular to define a constraint problem visually, to solve it, and eventually to edit partial or approached results during the resolution process. 相似文献
2.
Philippe Chapdelaine Nadia Creignou 《Annals of Mathematics and Artificial Intelligence》2005,43(1-4):51-63
The class of generalized satisfiability problems, first introduced by Schaefer in 1978, presents a uniform way of studying the complexity of Boolean constraint satisfaction problems with respect to the nature of constraints allowed in the input. We investigate the complexity of local search for this class of problems. We prove a dichotomy result: any generalized satisfiability local search problem is either in P or PLS-complete. In the meantime our study contributes to a better understanding of the complexity class PLS through the identification of an appropriate tool that captures reducibility among Boolean constraint satisfaction local search problems: sensitive implementation. 相似文献
3.
Philippe Chapdelaine Nadia Creignou 《Annals of Mathematics and Artificial Intelligence》2005,43(1):51-63
The class of generalized satisfiability problems, first introduced by Schaefer in 1978, presents a uniform way of studying the complexity of Boolean constraint satisfaction problems with respect to the nature of constraints allowed in the input. We investigate the complexity of local search for this class of problems. We prove a dichotomy result: any generalized satisfiability local search problem is either in P or PLS-complete. In the meantime our study contributes to a better understanding of the complexity class PLS through the identification of an appropriate tool that captures reducibility among Boolean constraint satisfaction local search problems: sensitive implementation. 相似文献
4.
Julian R. Ullmann 《Information Sciences》2007,177(18):3639-3678
Previous algorithms for unrestricted constraint satisfaction use reduction search, which inferentially removes values from domains in order to prune the backtrack search tree. This paper introduces partition search, which uses an efficient join mechanism instead of removing values from domains. Analytical prediction of quantitative performance of partition search appears to be intractable and evaluation therefore has to be by experimental comparison with reduction search algorithms that represent the state of the art. Instead of working only with available reduction search algorithms, this paper introduces enhancements such as semijoin reduction preprocessing using Bloom filtering. 相似文献
5.
为了求解具有增长取值域的随机约束满足问题(CSP),提出了一种基于禁忌搜索并与模拟退火相结合的算法。首先,利用禁忌搜索得到一组启发式的初始赋值,即由一个随机初始化的可行解通过邻域构造一组候选解,再利用禁忌表使候选解向最小化目标函数值的方向移动;如果得到的最优赋值不是问题的解,就把它作为启发式的初始赋值,再执行模拟退火对这组赋值进行修正直到得到全局最优解。数值实验结果表明,所提算法在接近问题的理论相变阈值时仍然能有效地找到问题的解,与其他局部搜索算法相比,表现出了显著的优越性,可用于随机CSP的算法设计。 相似文献
6.
Backjump-based backtracking for constraint satisfaction problems 总被引:1,自引:0,他引:1
The performance of backtracking algorithms for solving finite-domain constraint satisfaction problems can be improved substantially by look-back and look-ahead methods. Look-back techniques extract information by analyzing failing search paths that are terminated by dead-ends. Look-ahead techniques use constraint propagation algorithms to avoid such dead-ends altogether. This paper describes a number of look-back variants including backjumping and constraint recording which recognize and avoid some unnecessary explorations of the search space. The last portion of the paper gives an overview of look-ahead methods such as forward checking and dynamic variable ordering, and discusses their combination with backjumping. 相似文献
7.
We describe a simple CSP formalism for handling multi-attribute preference problems with hard constraints, one that combines
hard constraints and preferences so the two are easily distinguished conceptually and for purposes of problem solving. Preferences
are represented as a lexicographic order over complete assignments based on variable importance and rankings of values in
each domain. Feasibility constraints are treated in the usual manner. Since the preference representation is ordinal in character,
these problems can be solved with algorithms that do not require evaluations to be represented explicitly. This includes ordinary
CSP algorithms, although these cannot stop searching until all solutions have been checked, with the important exception of
heuristics that follow the preference order (lexical variable and value ordering). We describe relations between lexicographic
CSPs and more general soft constraint formalisms and show how a full lexicographic ordering can be expressed in the latter.
We discuss relations with (T)CP-nets, highlighting the advantages of the present formulation, and we discuss the use of lexicographic
ordering in multiobjective optimisation. We also consider strengths and limitations of this form of representation with respect
to expressiveness and usability. We then show how the simple structure of lexicographic CSPs can support specialised algorithms:
a branch and bound algorithm with an implicit cost function, and an iterative algorithm that obtains optimal values for successive
variables in the importance ordering, both of which can be combined with appropriate variable ordering heuristics to improve
performance. We show experimentally that with these procedures a variety of problems can be solved efficiently, including
some for which the basic lexically ordered search is infeasible in practice. 相似文献
8.
María-Cristina Riff Marcos Zúñiga Elizabeth Montero 《Neural computing & applications》2010,19(8):1133-1142
We propose an artificial immune algorithm to solve constraint satisfaction problems (CSPs). Recently, bio-inspired algorithms
have been proposed to solve CSPs. They have shown to be efficient in solving hard problem instances. Given that recent publications
indicate that immune-inspired algorithms offer advantages to solve complex problems, our main goal is to propose an efficient
immune algorithm which can solve CSPs. We have calibrated our algorithm using relevance estimation and value calibration (REVAC),
which is a new technique recently introduced to find the parameter values for evolutionary algorithms. The tests were carried
out using randomly generated binary constraint satisfaction problems and instances of the three-colouring problem with different
constraint networks. The results suggest that the technique may be successfully applied to solve CSPs. 相似文献
9.
10.
Barnaby Martin 《Information Processing Letters》2011,111(20):999-1003
Building on a result of Larose and Tesson for constraint satisfaction problems (CSPs), we uncover a dichotomy for the quantified constraint satisfaction problem QCSP(B), where B is a finite structure that is a core. Specifically, such problems are either in ALogtime or are L-hard. This involves demonstrating that if CSP(B) is first-order expressible, and B is a core, then QCSP(B) is in ALogtime.We show that the class of B such that CSP(B) is first-order expressible (indeed trivial) is a microcosm for all QCSPs. Specifically, for any B there exists a C — generally not a core — such that CSP(C) is trivial, yet QCSP(B) and QCSP(C) are equivalent under logspace reductions. 相似文献
11.
12.
We present a general representation for problems that can be reduced to constraint satisfaction problems (CSP) and a model for reasoning about their solution. The novel part of the model is a constraint-driven reasoner that manages a set of constraints specified in terms of arbitrarily complex Boolean expressions and represented in the form of a dependency network. This dependency network incorporates control information (derived from the syntax of the constraints) that is used for constraint propagation, contains dependency information that can be used for explanation and for dependency-directed backtracking, and is incremental in the sense that if the problem specification is modified, a new solution can be derived by modifying the existing solution. The constraint-driven reasoner is coupled to a problem solver which contains information about the problem variables and preference orderings 相似文献
13.
Montserrat Abril Miguel A. Salido Federico Barber 《Journal of Intelligent Manufacturing》2010,21(1):101-110
Many real problems can be naturally modelled as constraint satisfaction problems (CSPs). However, some of these problems are of a distributed nature, which requires problems of this kind to be modelled as distributed constraint satisfaction problems (DCSPs). In this work, we present a distributed model for solving CSPs. Our technique carries out a partition over the constraint network using a graph partitioning software; after partitioning, each sub-CSP is arranged into a DFS-tree CSP structure that is used as a hierarchy of communication by our distributed algorithm. We show that our distributed algorithm outperforms well-known centralized algorithms solving partitionable CSPs. 相似文献
14.
Ian P. Gent Peter Nightingale Andrew Rowley Kostas Stergiou 《Artificial Intelligence》2008,172(6-7):738-771
We make a number of contributions to the study of the Quantified Constraint Satisfaction Problem (QCSP). The QCSP is an extension of the constraint satisfaction problem that can be used to model combinatorial problems containing contingency or uncertainty. It allows for universally quantified variables that can model uncertain actions and events, such as the unknown weather for a future party, or an opponent's next move in a game. In this paper we report significant contributions to two very different methods for solving QCSPs. The first approach is to implement special purpose algorithms for QCSPs; and the second is to encode QCSPs as Quantified Boolean Formulas and then use specialized QBF solvers. The discovery of particularly effective encodings influenced the design of more effective algorithms: by analyzing the properties of these encodings, we identify the features in QBF solvers responsible for their efficiency. This enables us to devise analogues of these features in QCSPs, and implement them in special purpose algorithms, yielding an effective special purpose solver, QCSP-Solve. Experiments show that this solver and a highly optimized QBF encoding are several orders of magnitude more efficient than the initially developed algorithms. A final, but significant, contribution is the identification of flaws in simple methods of generating random QCSP instances, and a means of generating instances which are not known to be flawed. 相似文献
15.
Luc Jaulin 《Computing》2012,94(2-4):297-311
In this paper, we consider the resolution of constraint satisfaction problems in the case where the variables of the problem are subsets of ${\mathbb{R}^{n}}$ . In order to use a constraint propagation approach, we introduce set intervals (named i-sets), which are sets of subsets of ${\mathbb{R}^{n}}$ with a lower bound and an upper bound with respect to the inclusion. Then, we propose basic operations for i-sets. This makes possible to build contractors that are then used by the propagation to solve problem involving sets as unknown variables. In order to illustrate the principle and the efficiency of the approach, a testcase is provided. 相似文献
16.
Pierre Flener Justin Pearson Meinolf Sellmann Pascal Van Hentenryck Magnus Ågren 《Constraints》2009,14(4):506-538
In recent years, symmetry breaking for constraint satisfaction problems (CSPs) has attracted considerable attention. Various
general schemes have been proposed to eliminate symmetries. In general, these schemes may take exponential space or time to
eliminate all the symmetries. We identify several classes of CSPs that encompass many practical problems and for which symmetry
breaking for various forms of value or variable interchangeability is tractable using dedicated search procedures. We also
show the limits of efficient symmetry breaking for such dominance-detection schemes by proving intractability results for
some classes of CSPs. 相似文献
17.
18.
In early phases of designing complex systems, models are not sufficiently detailed to serve as an input for automated synthesis tools. Instead, a design space is constituted by multiple models representing different valid design candidates. Design space exploration aims at searching through these candidates defined in the design space to find solutions that satisfy the structural and numeric design constraints and provide a balanced choice with respect to various quality metrics. Design space exploration in an model-driven engineering (MDE) context is frequently tackled as specific sort of constraint satisfaction problem (CSP). In CSP, declarative constraints capture restrictions over variables with finite domains where both the number of variables and their domains are required to be a priori finite. However, the existing formulation of constraint satisfaction problems can be too restrictive to capture design space exploration in many MDE applications with complex structural constraints expressed over the underlying models. In this paper, we interpret flexible and dynamic constraint satisfaction problems directly in the context of models. These extensions allow the relaxation of constraints during a solving process and address problems that are subject to change and require incremental re-evaluation. Furthermore, we present our prototype constraint solver for the domain of graph models built upon the Viatra2 model transformation framework and provide an evaluation of its performance with comparison to related tools. 相似文献
19.
The Semiring Constraint Satisfaction Problem (SCSP) framework is a popular approach for the representation of partial constraint satisfaction problems. In this framework preferences can be associated with tuples of values of the variable domains. Bistarelli et al. [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraint solving and optimization, Journal of the ACM 44 (2) (1997) 201-236] defines a maximal solution to a SCSP as the best set of solution tuples for the variables in the problem. Sometimes this maximal solution may not be good enough, and in this case we want to change the constraints so that we solve a problem that is slightly different from the original problem but has an acceptable solution. We propose a relaxation of a SCSP, and use a semiring to give a measure of the difference between the original SCSP and the relaxed SCSP. We introduce a relaxation scheme but do not address the computational aspects. 相似文献