One of the most appealing features of constraintprogramming is its rich constraint language for expressing combinatorial optimization problems. this paper demonstrates that traditional combinators from constraint pro...
详细信息
ISBN:
(纸本)3540232419
One of the most appealing features of constraintprogramming is its rich constraint language for expressing combinatorial optimization problems. this paper demonstrates that traditional combinators from constraintprogramming have natural counterparts for local search, although their underlying computational model is radically different. In particular, the paper shows that constraint combinators, such as logical and cardinality operators, reification, and first-class expressions can all be viewed as differentiable objects. these combinators naturally support elegant and efficient modelings, generic search procedures, and partial constraint satisfaction techniques for local search. Experimental results on a variety of applications demonstrate the expressiveness and the practicability of the combinators.
the contribution of this paper is in demonstrating the impact of AND/OR search spaces view on solutions counting. In contrast to the traditional (OR) search space view, the AND/OR search space displays independencies ...
详细信息
ISBN:
(纸本)3540232419
the contribution of this paper is in demonstrating the impact of AND/OR search spaces view on solutions counting. In contrast to the traditional (OR) search space view, the AND/OR search space displays independencies present in the graphical model explicitly and may sometimes reduce the search space exponentially. Empirical evaluation focusing on counting demonstrates the spectrum of search and inference within the AND/OR search spaces.
the quantified constraint satisfaction problem (QCSP) is a natural and useful generalization of the constraint satisfaction problem (CSP) in which both universal and existential quantification of variables is permitte...
详细信息
ISBN:
(纸本)3540232419
the quantified constraint satisfaction problem (QCSP) is a natural and useful generalization of the constraint satisfaction problem (CSP) in which both universal and existential quantification of variables is permitted. Because the CSP and QCSP are in general intractable, much effort has been directed towards identifying restricted cases of these problems that are tractable in polynomial time. In this paper, we investigate restricted cases of the QCSP having 2-semilattice polymorphisms. We prove a complete classification of 2-semilattice polymorphisms, demonstrating that each gives rise to a case of the QCSP that is either tractable in polynomial time, or coNP-hard.
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.
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.
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.
the paper presents a new look-ahead scheme for backtracking search for solving constraint satisfaction problems. this look-ahead scheme computes a heuristic for value ordering and domain pruning. the heuristic is base...
详细信息
ISBN:
(纸本)3540232419
the paper presents a new look-ahead scheme for backtracking search for solving constraint satisfaction problems. this look-ahead scheme computes a heuristic for value ordering and domain pruning. the heuristic is based on approximating the number of solutions extending each partial solution. In particular, we investigate a recent partition-based approximation of tree-clustering algorithms, Iterative Join-Graph Propagation (IJGP), which belongs to the class of belief propagation algorithms that attracted substantial interest due to their success for probabilistic inference. Our empirical evaluation demonstrates that the counting-based heuristic approximated by IJGP yields a scalable, focused search.
Symmetry in constraint problems can be exploited to greatly improve search performance. A form of symmetry that has been the subject of considerable research is value interchangeability. Automatically detecting full i...
详细信息
ISBN:
(纸本)3540232419
Symmetry in constraint problems can be exploited to greatly improve search performance. A form of symmetry that has been the subject of considerable research is value interchangeability. Automatically detecting full interchangeability is thought to be intractable, so research has focused on either discovery of local interchangeability or programmer knowledge of full interchangeability. this paper shows that full dynamic substitutability can be broken in a CSP by reformulating it as a SAT problem. No analysis is necessary, space requirements are modest, solutions are collected into Cartesian products, and unit propagation enforces forward checking on the CSP. In experiments on unsatisfiable problems, better results are obtained than with standard SAT encodings.
暂无评论