A Distributed constraint Optimization Problem (DCOP) is a fundamental problem that can formalize various applications related to multi-agent cooperation. Since it is NP-hard, considering faster incomplete algorithms i...
详细信息
constraint satisfaction problems arise in many diverse areas including software and hardware verification, type inference, static program analysis, test-case generation, scheduling, planning and graph problems. these ...
详细信息
the SEQUENCE constraint is useful in modelling car sequencing, rostering, scheduling and related problems. We introduce half a dozen new encodings of the SEQUENCE constraint, some of which do not hinder propagation. W...
详细信息
ISBN:
(纸本)9783540749691
the SEQUENCE constraint is useful in modelling car sequencing, rostering, scheduling and related problems. We introduce half a dozen new encodings of the SEQUENCE constraint, some of which do not hinder propagation. We prove that, down a branch of a search tree, domain consistency can be enforced on the SEQUENCE constraint in just O(n(2) log n) time. this improves upon the previous bound of O(n(3)) for each call down the tree. We also consider a generalization of the SEQUENCE constraint - the Multiple SEQUENCE constraint. Our experiments suggest that, on very large and tight problems, domain consistency algorithms are best. However, on smaller or looser problems, much simpler encodings are better, even though these encodings hinder propagation. When there are multiple SEQUENCE constraints, a more expensive propagator shows promise.
the paper introduces the notion of freely completable partial solutions to characterize constraint satisfaction problems that have components which are relatively easy to solve and are only loosely connected to the re...
详细信息
ISBN:
(纸本)3540232419
the paper introduces the notion of freely completable partial solutions to characterize constraint satisfaction problems that have components which are relatively easy to solve and are only loosely connected to the remaining parts of the problem. Discovering such partial solutions during the solution process can result in strongly pruned search trees. We give a general definition of freely completable partial solutions, and then apply it to resource-constrained project scheduling. In this domain, we suggest a heuristic algorithm that is able to construct freely completable partial schedules. the method – together with symmetry breaking applied before search – has been successfully tested on real-life resource-constrained project scheduling problems containing up to 2000 tasks.
Over the past few years there has been considerable progress in methods to systematically analyse the complexity of classical (crisp) constraint satisfaction problems with specified constraint types. One very powerful...
详细信息
A difficulty that arises frequently when writing a constraint solver is to determine the constraint propagation and simplification algorithm. In previous work, different methods for automatic generation of propagation...
详细信息
this paper proposes an algorithm for satisfying systems of linear equality and inequality constraints with hierarchical strengths or preferences. Basically, it is a numerical method that incrementally obtains the LU d...
详细信息
A lot of workin constraint satisfaction has been focused on finding solutions to difficult problems. Many real life problems however, while not extremely complicated, have a huge number of solutions, few of which are ...
详细信息
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.
暂无评论