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...
详细信息
this book constitutes the thoroughly refereed post-conference proceedings of the 18thinternationalconference on principles and practice of constraintprogramming (cp 2012), held in Québec, Canada, in October 20...
详细信息
ISBN:
(数字)9783642335587
ISBN:
(纸本)9783642335570
this book constitutes the thoroughly refereed post-conference proceedings of the 18thinternationalconference on principles and practice of constraintprogramming (cp 2012), held in Québec, Canada, in October 2012.
the 68 revised full papers were carefully selected from 186 submissions. Beside the technical program, the conference featured two special tracks. the former was the traditional application track, which focused on industrial and academic uses of constraint technology and its comparison and integration with other optimization techniques (MIP, local search, SAT, etc.) the second track, featured for the first time in 2012, concentrated on multidisciplinary papers: cross-cutting methodology and challenging applications collecting papers that link cp technology with other techniques like machine learning, data mining, game theory, simulation, knowledge compilation, visualization, control theory, and robotics. In addition, the track focused on challenging application fields with a high social impact such as cp for life sciences, sustainability, energy efficiency, web, social sciences, finance, and verification.
this book constitutes the proceedings of the 25thinternationalconference on principles and practice of constraintprogramming, cp 2019, held in Stamford, CT, USA, France, in September/October 2019.
ISBN:
(数字)9783030300487
ISBN:
(纸本)9783030300470
this book constitutes the proceedings of the 25thinternationalconference on principles and practice of constraintprogramming, cp 2019, held in Stamford, CT, USA, France, in September/October 2019.
this book constitutes the refereed proceedings of the 17th international conference on principles and practice of constraint programming, cp 2011, held in Perugia, Italy, September 12-16, 2011. the 51 revised full pap...
详细信息
ISBN:
(数字)9783642237867
ISBN:
(纸本)9783642237850
this book constitutes the refereed proceedings of the 17th international conference on principles and practice of constraint programming, cp 2011, held in Perugia, Italy, September 12-16, 2011.
the 51 revised full papers and 7 short papers presented together withthree invited talks were carefully reviewed and selected from 159 submissions. the papers are organized in topical sections on algorithms, environments, languages, models and systems, applications such as decision making, resource allocation and agreement technologies.
暂无评论