In real-life temporal scenarios, uncertainty and preferences are often essential, coexisting aspects. We present a formalism where temporal constraints with both preferences and uncertainty can be defined. We show how...
详细信息
Local search (LS) and multi-agent-based search (ERA [1]) are stochastic and incomplete procedures for solving a constraint Satisfaction Problem (CSP). their performance is seriously undermined by local optima and dead...
ISBN:
(纸本)3540232419
Local search (LS) and multi-agent-based search (ERA [1]) are stochastic and incomplete procedures for solving a constraint Satisfaction Problem (CSP). their performance is seriously undermined by local optima and deadlocks, respectively. Although complete, backtrack (BT) search suffers from thrashing and a high degree of unpredictability in its run-time even within the same problem domain. Further, when the problem is large, the completeness of BT cannot be guaranteed in practice. Gomes et al. [2] proposed to use randomization and rapid restarts (RRR) to overcome the heavy tail behavior of BT. RRR requires the specification of a cutoff value determined from an overall profile of the cost of search for solving the problem. When no such profile is known, the cutoff value is chosen by trial-and-error. Walsh [3] proposed the strategy Randomization and Geometric Restart (RGR), which does not rely on a cost profile but determines the cutoff value as a function of a constant parameter and the number of variables in the problem. Neither RRR nor RGR takes into account the intermediate results of search (i.e., across restarts). We propose an improved restart strategy, Randomization and Dynamic Geometric Restarts (RDGR), which dynamically adapts the value of the cutoff parameter to the results of the search process.
We give an approximate and often extremely fast method of solving a portfolio optimisation (PO) problem in financial mathematics, which has applications in the credit derivatives market. Its corresponding satisfaction...
详细信息
Promise is the ability to make choices that lead to a solution when one exists. the traditional intuition behind variable ordering heuristics is Haralick and Elliotts fail-first principle: choose the variable such tha...
ISBN:
(纸本)3540232419
Promise is the ability to make choices that lead to a solution when one exists. the traditional intuition behind variable ordering heuristics is Haralick and Elliotts fail-first principle: choose the variable such that assigning it is most likely to lead to a domain wipe-out (in AIJ 14, 1980). In contrast, the standard belief about value ordering heuristics is based on Geelens discussion (in ECAI92): choose a value that is most likely to participate in a solution. It is not clear a priori that changes in variable ordering change the likelihood of finding a solution in a way that will affect overall performance significantly. In this paper we show that promise does have a meaning for variable ordering heuristics and that the level of promise of a variable ordering heuristic can be measured. In addition, we show that the promise of different variable ordering heuristics is different and that the level of promise of a variable ordering heuristic correlates with search cost for problems with many solutions.
When solving constraint Satisfaction Problems (CSPs), it is desirable to find multiple solutions, or to find solutions that are robust, allowing us to modify the values of variables without breaking the solution. Furt...
ISBN:
(纸本)3540232419
When solving constraint Satisfaction Problems (CSPs), it is desirable to find multiple solutions, or to find solutions that are robust, allowing us to modify the values of variables without breaking the solution. Furthermore, we would like to be able to represent these multiple solutions in a compact manner. We present a method for improving the performance of, and solutions returned by, stochastic local search using maximal independent sets1 of the constraint graph. Given an independent set, this information can be used to significantly speed up the process of solving a CSP by reducing the search space. the CSP is partitioned into two sets of variables I and [`(I)]\bar{I}, where I is a maximal independent set of the constraint graph. In this way, search is concentrated only on the variables of [`(I)]\bar{I}, reducing the search space by a factor exponential in the size of I. Also this technique can provide multiple solutions in a compact form with no extra cost, since if we find a set of valid domain values for each variable in I, every element of the Cartesian product of these sets is a solution to the CSP. We focus on exploiting this information in local search. this technique is limited to low-density graphs, since dense graphs are less likely to contain a large independent set. the resulting solutions are robust with respect to the variables in the independent set. We compare the technique with WalkSAT, as defined for CSPs by [2], on low-density random CSP instances generated according to model B, with 16 variables, domain size 8, tightness 0.3 and density 0.1. the average CPU run-time for WalkSAT was 96.5 seconds, while the average for WalkSAT_IS was 0.36 seconds. Also, while WalkSAT returns one solution, the average number of solutions returned by WalkSAT_IS per instance was 47,536,305 solutions this is a dramatic improvement in performance, as well as in the number of solutions returned. this technique falls in the category of algorithms exploiting backdoor
We explore to what extent and how efficiently constraintprogramming can be used in the context of automated reasoning for modal logics. We encode modal satisfiability problems as constraint satisfaction problems with...
详细信息
ISBN:
(纸本)3540202021
We explore to what extent and how efficiently constraintprogramming can be used in the context of automated reasoning for modal logics. We encode modal satisfiability problems as constraint satisfaction problems with non-boolean domains, together with suitable constraints. Experiments show that the approach is very promising.
暂无评论