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.
We analyze the complexity of optimization problems expressed using valued constraints. this very general framework includes a number of well-known optimization problems such as MAX-SAT, and WEIGHTED MAX-SAT, as well a...
详细信息
ISBN:
(纸本)3540232419
We analyze the complexity of optimization problems expressed using valued constraints. this very general framework includes a number of well-known optimization problems such as MAX-SAT, and WEIGHTED MAX-SAT, as well as properly generalizing the classical CSP framework by allowing the expression of preferences. We focus on valued constraints over Boolean variables, and we establish a dichotomy theorem which characterizes the complexity of any problem involving a fixed set of constraints of this kind.
It is well known that the Davis-Putnam-Logemann-Loveland (DPLL) algorithm for satisfiability (SAT) can be extended to an algorithm for maximum SAT (max-SAT). In this paper, we propose a number of strategies to signifi...
详细信息
ISBN:
(纸本)3540232419
It is well known that the Davis-Putnam-Logemann-Loveland (DPLL) algorithm for satisfiability (SAT) can be extended to an algorithm for maximum SAT (max-SAT). In this paper, we propose a number of strategies to significantly improve this max-SAT method. the first strategy is a set of unit propagation rules;the second is an effective lookahead heuristic based on linear programming;and the third strategy is a dynamic variable ordering that exploits problem constrainedness during search. We integrate these strategies in an efficient complete solver for both max-SAT and weighted max-SAT. Our experimental results on random problem instances and many instances from SATLIB demonstrate the efficacy of these strategies and show that the new solver is able to significantly outperform most of the existing complete max-SAT solvers, with a few orders of magnitude of improvement in running time in many cases.
A distributed concurrent search algorithm for distributed constraint satisfaction problems (DisCSPs) is presented. Concurrent search algorithms are composed of multiple search processes (SPs) that operate concurrently...
详细信息
ISBN:
(纸本)3540232419
A distributed concurrent search algorithm for distributed constraint satisfaction problems (DisCSPs) is presented. Concurrent search algorithms are composed of multiple search processes (SPs) that operate concurrently and scan non-intersecting parts of the global search space. Search processes are generated dynamically, started by the initializing agent, and by any number of agents during search. In the proposed, ConcDB, algorithm, all search processes perform dynamic backtracking (DB). As a consequence of DB, a search space scanned by one search process can be found unsolvable by a different search process. this enhances the efficiency of the ConcDB algorithm. Concurrent search is an asynchronous distributed algorithm and is shown to be faster than asynchronous backtracking (ABT). the network load of ConcDB is also much lower than that of ABT.
this article deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in n, where n is the number of variables of the corresp...
详细信息
ISBN:
(纸本)3540232419
this article deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in n, where n is the number of variables of the corresponding global constraint. By reformulating the automaton as a conjunction of signature and transition constraints we show how to systematically obtain a filtering algorithm. Under some restrictions on the signature and transition constraints this filtering algorithm achieves arc-consistency. An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available. For a restricted class of automata we provide a filtering algorithm for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.
Existing random models for the constraint satisfaction problem (CSP) all require an extremely low constraint tightness in order to have non-trivial threshold behaviors and guaranteed hard instances at the threshold. W...
详细信息
ISBN:
(纸本)3540232419
Existing random models for the constraint satisfaction problem (CSP) all require an extremely low constraint tightness in order to have non-trivial threshold behaviors and guaranteed hard instances at the threshold. We study the possibility of designing random CSP models that have interesting threshold and typical-case complexity behaviors while at the same time, allow a much higher constraint tightness. We show that random CSP models that enforce the constraint consistency have guaranteed exponential resolution complexity without putting much restriction on the constraint tightness. A new random CSP model is proposed to generate random CSPs with a high tightness whose instances are always consistent. Initial experimental results are also reported to illustrate the sensitivity of instance hardness to the constraint tightness in classical CSP models and to evaluate the proposed new random CSP model.
暂无评论