constraint propagation [10,7,5] (cp) is a cornerstone algorithm of constraintprogramming, mainly devoted to the computation of local consistency properties of constraint satisfaction problems. the abstract formulatio...
ISBN:
(纸本)3540410538
constraint propagation [10,7,5] (cp) is a cornerstone algorithm of constraintprogramming, mainly devoted to the computation of local consistency properties of constraint satisfaction problems. the abstract formulation of cp is the combination of a set of reduction functions (black-box solvers) on a domain [8,9,2,1]. Intuitively, there is a dependence relation between functions and domains, such that a function must be applied if a domain it depends on is reduced. the essential property of cp is confluence or strategy-independence. In other words, the order solvers are applied does not influence the output characterized in terms of a common fixed-point of the solvers. Owing to this remark, several strategies based on heuristics, data structures, or knowledge of the solvers have been implemented.
Many recent systems tackling Distributed constraint Satisfaction Problems (DCSPs) lack a theoretically founded specification and safety or liveness property proofs. this may be due to the difficulty of modeling and ve...
详细信息
作者：
Bistarelli, S.Gennari, R.Rossi, F.Università di Pisa
Dipartimento di Informatica Corso Italia 40 Pisa56125 Italy ILLC
Institute of Logic Language and Computation University of Amsterdam N. Doelenstraat 15 Amsterdam1012 CP Netherlands Università di Padova
Dipartimento di Matematica Pura ed Applicata Via Belzoni 7 Padova35131 Italy
Soft constraints based on semirings are a generalization of classical constraints, where tuples of variables’ values in each soft constraint are uniquely associated to elements from an algebraic structure called semi...
详细信息
Solving non-binary constraint satisfaction problems, a crucial challenge for the next years, can be tackled in two different ways: translating the non-binary problem into an equivalent binary one, or extending binary ...
详细信息
the protein structure prediction problem is one of the most (if not the most) important problem in computational biology. this problem consists of finding the conformation of a protein (i.e., a sequence of amino-acids...
详细信息
ISBN:
(纸本)3540652248
the protein structure prediction problem is one of the most (if not the most) important problem in computational biology. this problem consists of finding the conformation of a protein (i.e., a sequence of amino-acids) with minimal energy. Because of the complexity of this problem, simplified models like Dill's HP-lattice model [12] have become a major tool for investigating general properties of protein folding. Even for this simplified model, the structure prediction problem has been shown to be NP-complete [3, 5]. We describe a constraint formulation of the HP-model structure prediction problem, present the basic constraints and search strategy. We then introduce a novel, general technique for excluding geometrical symmetries in constraintprogramming. To our knowledge, this is the first general and declarative technique for excluding symmetries in constraintprogrammingthat can be added to an existing implementation. Finally, we describe a new lower bound on the energy of an HP-protein. Both techniques yield an efficient pruning of the search tree.
this paper presents a robust approach to solve Hoist Scheduling Problems (HSPs) based on an integration of constraint Logic programming (CLP) and Mixed Integer programming (MIP). By contrast with previous dedicated mo...
详细信息
ISBN:
(纸本)3540652248
this paper presents a robust approach to solve Hoist Scheduling Problems (HSPs) based on an integration of constraint Logic programming (CLP) and Mixed Integer programming (MIP). By contrast with previous dedicated models and algorithms for solving classes of HSPs, we define only one model and run different solvers. the robust approach is achieved by using a CLP formalism. We show that our models for different classes of industrial HSPs are all based on the same generic model. In our hybrid algorithm search is separated from the handling of constraints. constraint handling is performed by constraint propagation and linear constraint solving. Search is applied by labelling of boolean and integer variables. Computational experience shows that the hybrid algorithm, combining CLP and MIP salvers, solves classes of HSPs which cannot be handled by previous dedicated algorithms. For example, the hybrid algorithm derives an optimal solution, and proves its optimality, for multiple-hoists scheduling problems.
this paper explores the performance of a new complete nonsystematic search algorithm learn-SAT on two types of 3-SAT problems, (i) an extended range of AIM problems [1] and (ii) structured unsolvable problems [2]. the...
详细信息
暂无评论