constraint handling rules provide descriptions for constraint solvers. However, they fall short when those constraints specify some binding structure, like higher-rank types in a constraint-based type inference algori...
详细信息
constraint handling rules provide descriptions for constraint solvers. However, they fall short when those constraints specify some binding structure, like higher-rank types in a constraint-based type inference algorithm. In this paper, the term syntax of constraints is replaced by lambda-tree syntax, in which binding is explicit, and a new del generic quantifier is introduced, which is used to create new fresh constants.
作者：
Sulzmann, MartinLam, Edmund S. L.Programming
Logics and Semantics Group IT University of Copenhagen Rued Langgaards Vej 7 2300 Copenhagen S Denmark School of Computing
National University of Singapore S16 Level 5 3 Science Drive 2 Singapore 117543 Singapore
Multi-set constraint rewriting allows for a highly parallel computational model and has been used in a multitude of application domains such as constraint solving, agent specification etc. Rewriting steps can be appli...
详细信息
constraint propagation is one of the techniques central to the success of constraintprogramming. Fast algorithms are used to prune the search space either before or during backtracking search. Propagating global cons...
详细信息
ISBN:
(纸本)3540232419
constraint propagation is one of the techniques central to the success of constraintprogramming. Fast algorithms are used to prune the search space either before or during backtracking search. Propagating global constraints is intractable in general. In this paper, we characterize a number of important questions related to constraint propagation. For example, we consider the two questions: "Is this problem generalized arc-consistent?" and "What are the maximal generalized arc-consistent domains?". We identify dependencies between the tractability and intractability of these questions for finite domain variables. Finally, we prove intractability for a range of global constraints.
We show that intractability of the constraint satisfaction problem over a fixed finite constraint language can, in all known cases, be replaced by an infinite hierarchy of intractable promise problems of increasingly ...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
We show that intractability of the constraint satisfaction problem over a fixed finite constraint language can, in all known cases, be replaced by an infinite hierarchy of intractable promise problems of increasingly disparate promise conditions. the instances are guaranteed to either have no solutions at all, or to be k-robustly satisfiable (for any fixed k), meaning that every "reasonable" partial instantiation on k variables extends to a solution.
In this talk we present a number of problems for network design, planning and analysis and show how they can be addressed with different hybrid CP solutions. Clearly, this problem domain is of huge practical importanc...
详细信息
ISBN:
(纸本)3540232419
In this talk we present a number of problems for network design, planning and analysis and show how they can be addressed with different hybrid CP solutions. Clearly, this problem domain is of huge practical importance, but it also provides us with interesting, complex problem structures. CP directly competes with MILP and local search approaches to these problems, with best results often obtained by a combination of different solution techniques. Teams at Parc Technologies and IC-Parc have been working in this field over the last years, with a number of applications now embedded in commercial products.
A key feature of constraintprogramming is the ability to design specific search strategies to solve problems. On the contrary, integer programming solvers have used efficient general-purpose strategies since their ea...
详细信息
ISBN:
(纸本)3540232419
A key feature of constraintprogramming is the ability to design specific search strategies to solve problems. On the contrary, integer programming solvers have used efficient general-purpose strategies since their earliest implementations. We present a new general purpose search strategy for constraintprogramming inspired from integer programming techniques and based on the concept of the impact of a variable. the impact measures the importance of a variable for the reduction of the search space. Impacts are learned from the observation of domain reduction during search and we show how restarting search can dramatically improve performance. Using impacts for solving multiknapsack, magic square, and Latin square completion problems shows that this new criteria for choosing variables and values can outperform classical general-purpose strategies.
constraintprogramming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express r...
详细信息
constraintprogramming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express relations among the decision variables. One key concept in constraintprogramming is propagation: reasoning on a constraint or set of constraints to derive new facts, typically to remove values from the domains of decision variables. Specialized propagation algorithms (propagators) exist for many classes of constraints. the concept of support is pervasive in the design of propagators. Traditionally, when a domain value ceases to have support, it may be removed because it takes part in no solutions. Arc-consistency algorithms such as AC2001 [in: Proceedings 17thinternational Joint conference on Artificial Intelligence (IJCAI 2001), 2001, pp. 309-315] make use of support in the form of a single domain value. GAC algorithms such as GAC-Schema [in: Proceedings 15thinternational Joint conference on Artificial Intelligence (IJCAI 97), 1997, pp. 398-404] use a tuple of values to support each literal. We generalize these notions of support in two ways. First, we allow a set of tuples to act as support. Second, the supported object is generalized from a set of literals (GAC-Schema) to an entire constraint or any part of it. We design a methodology for developing correct propagators using generalized support. A constraint is expressed as a family of support properties, which may be proven correct against the formal semantics of the constraint. We show how to derive correct propagators from the constructive proofs of the support properties. the framework is carefully designed to allow efficient algorithms to be produced. Derived algorithms may make use of dynamic literal triggers or watched literals [in: Proc. 12thinternationalconference on the principles and practice of constraintprogramming (CP 2006), 2006, pp. 182-197] for efficiency. Finally, three case st
the stretch constraint occurs in many rostering problems that arise in the industrial and public service sectors. In this paper we present an efficient algorithm for domain consistency propagation of the stretch const...
详细信息
ISBN:
(纸本)3540232419
the stretch constraint occurs in many rostering problems that arise in the industrial and public service sectors. In this paper we present an efficient algorithm for domain consistency propagation of the stretch constraint. Using benchmark and random instances, we show that this stronger consistency sometimes enables our propagator to solve more difficult problems than a previously proposed propagation algorithm for the stretch constraint. We also discuss variations of the stretch constraintthat seem simple and useful, but turn out to be intractable to fully propagate.
Despite boththe commercial and academic success of optimization technology and specifically constraintprogramming, using the technology still requires significant expertise. For non-trivial applications the quality ...
ISBN:
(纸本)3540232419
Despite boththe commercial and academic success of optimization technology and specifically constraintprogramming, using the technology still requires significant expertise. For non-trivial applications the quality of a system still has much to do withthe quality of the person that implemented it. We investigate algorithm control techniques aimed at achieving strong scheduling performance using off-the-shelf algorithms without requiring significant human expertise. Rather than building knowledge-intensive models relating algorithm performance to problem features, we base the control decisions on the evolution of solution quality over time. Such an approach is crucial to our goal of the reduction of expertise.
Dynamic constraint Satisfaction Problems play a very important role in modeling and solving real-life problems where the set of constraints is changing. the paper addresses a problem of maintaining arc consistency aft...
详细信息
ISBN:
(纸本)3540232419
Dynamic constraint Satisfaction Problems play a very important role in modeling and solving real-life problems where the set of constraints is changing. the paper addresses a problem of maintaining arc consistency after removing a constraint from the constraint model. A new dynamic arc consistency algorithm is proposed that improves the practical time efficiency of the existing AC\DC algorithm by using additional data-structures. the algorithm achieves real time efficiency close to the so far fastest DynAC-6 algorithm while keeping the memory consumption low.
暂无评论