In this report weintroduce a new hybrid class for which arcconsistency is a decision procedure. this new hybrid class includes infinitely many instances whose tractability is not assured by any tractable language or s...
详细信息
this work presents a hybrid approach to solve the maximum stable set problem, using constraint and semidefinite programming. the approach consists of two steps: subproblem generation and subproblem solution. First we ...
详细信息
Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraintprogramming approach. In this paper we present an efficient algorithm f...
详细信息
constraintprogramming is a technology which is now widely used to solve combinatorial problems in industrial applications. However, using it requires considerable knowledge and expertise in the field of constraint re...
详细信息
this paper aims to show that constraintprogramming can be an efficient technique to solve a well-known combinatorial optimization problem: the search for a maximum clique in a graph. A clique of a graph G = (X,E) is ...
详细信息
We study two resolution-like refutation systems for finitedomain constraint satisfaction problems, and the efficiency of these and of common CSP algorithms. By comparing the relative strength of these systems, we show...
详细信息
there are two main solving schemas for constraint satisfaction and optimization problems: i) search, whose basic step is branching over the values of a variables, and ii) dynamic programming, whose basic step is varia...
详细信息
there are two main solving schemas for constraint satisfaction and optimization problems: i) search, whose basic step is branching over the values of a variables, and ii) dynamic programming, whose basic step is variable elimination. Variable elimination is time and space exponential in a graph parameter called induced width, which renders the approach infeasible for many problem classes. However, by restricting variable elimination so that only low arity constraints are processed and recorded, it can be effectively combined with search, because the elimination of variables may reduce drastically the search tree size. In this paper we introduce BE-BB(k), a hybrid general algorithm that combines search and variable elimination. the parameter k controls the tradeoff between the two strategies. the algorithm is space exponential in k. Regarding time, we show that its complexity is bounded by k and a structural parameter from the constraint graph. We provide experimental evidence that the hybrid algorithm can outperform state-of-the-art algorithms in constraint satisfaction, Max-CSP and Weighted CSP. Especially in optimization tasks, the advantage of our approach over plain search can be overwhelming.
Formal models for agent design are important for both practical and theoretical reasons. the constraint-Based Agent (CBA) design approach includes two formal models: constraint Nets and Timed For All-automata. A const...
详细信息
Formal models for agent design are important for both practical and theoretical reasons. the constraint-Based Agent (CBA) design approach includes two formal models: constraint Nets and Timed For All-automata. A constraint net models the agents and the environment symmetrically as, possibly hybrid, dynamical systems;a timed V-automaton specifies the desired real-time dynamic behaviors of the situated agents. Given a constraint-based specification of the desired behavior, a constraint-based agent can be synthesized as a constraint solver. Using formal modeling and specification, it is also possible to verify complex agents as obeying real-time temporal constraint specifications. this overview paper presents a summary of the development and application of the CBA framework.
the constraint satisfaction problem is known to be NP-hard in general, but a number of restrictions of the problem have been identified over the years which ensure tractability. this paper introduces two simple method...
详细信息
the constraint satisfaction problem is known to be NP-hard in general, but a number of restrictions of the problem have been identified over the years which ensure tractability. this paper introduces two simple methods of combining two or more tractable classes over disjoint domains, in order to synthesise larger, more expressive tractable classes. We demonstrate that the classes so obtained are genuinely novel, and have not been previously identified. In addition, we use algebraic techniques to extend the tractable classes which we identify, and to show that the algorithms for solving these extended classes can be less than obvious.
Integration of explanations into a CSP solver is a technique addressing difficult question "why my problem has no solution". Besides providing some sort of answer to the user, explanations can be used for de...
详细信息
暂无评论