the problem of finding an optimal solution in a constraint satisfaction problem with preferences has attracted a lot of researchers in Artificial Intelligence in general, and in the constraintprogramming community in...
详细信息
ISBN:
(纸本)9783540859574
the problem of finding an optimal solution in a constraint satisfaction problem with preferences has attracted a lot of researchers in Artificial Intelligence in general, and in the constraintprogramming community in particular. As a consequence, several approaches for expressing and reasoning about satisfiability problems with preferences have been proposed, and viable solutions exist for finding one optimal Solution. However, in many cases, it is not desirable to find just one solution. Indeed, it might be desirable to he able to compute more, and possibly all, optimal solutions, e.g.. for comparatively evaluate them on the basis of other criteria not captured by the preferences. In this paper we present a procedure for computing all optimal solutions of a satisfiability problem with preferences. the procedure is guaranteed to compute all and only the optimal solutions, i.e., models which are not optimal are not even computed.
We introduce the SOFTALLEQUAL global constraint. which maximizes the number of equalities holding between hairs of assignments to a set of variables. MO study the computational complexity of propagating this constrain...
详细信息
ISBN:
(纸本)9783540859574
We introduce the SOFTALLEQUAL global constraint. which maximizes the number of equalities holding between hairs of assignments to a set of variables. MO study the computational complexity of propagating this constraint, showing that it is intractable in general. Since maximizing the number of pairs of equally assigned variables ill a set is NP-hard. We propose three: ways of coping with NP-hardness Firstly, we develop a greedy linear-time algorithm to approximate the maximum number of equalities within a factor on. Secondly. we identify a tractable (polynomial) class for this constraint. thirdly;we identify a parameter based oil this class and show that the SOFTALLEQUAL constraint is fixed-parameter tractable with respect to this parameter.
We present tin incremental refinement algorithm for approximate compilation of constraint satisfaction models into multivalued decision diagrams (MDDs). the algorithm uses a vertex splitting operation that relies on t...
详细信息
ISBN:
(纸本)9783540859574
We present tin incremental refinement algorithm for approximate compilation of constraint satisfaction models into multivalued decision diagrams (MDDs). the algorithm uses a vertex splitting operation that relies on the detection of equivalent paths in the MDD. Although the algorithm is quite general, it can be adapted to exploit constraint structure by specializing the equivalence tests for partial assignments to particular constraints. We show how to modify the algorithm in a principled way to obtain an approximate MDD when the exact MDD is too large for practical purposes. this is done by replacing the equivalence test with a constraint-specific measure of distance. We demonstrate the value of the approach for approximate and exact MDD compilation and evaluate its benefits in one of the main MDD application domains, interactive configuration.
In a constraint optimization problem (COP), many feasible assignment's have the same objective value. this usually means huge search space and poor propagation among the objective variables (which appear in the ob...
详细信息
ISBN:
(纸本)9783540859574
In a constraint optimization problem (COP), many feasible assignment's have the same objective value. this usually means huge search space and poor propagation among the objective variables (which appear in the objective function) and the problem variables (which do not). In this paper, we investigate a. search strategy that focuses oil the objective function, namely, the objective variables are assigned before the problem variables Despite the larger search space;we may indeed solve a COP faster, provided that the constraint propagation is strong - the search can reach the optimal objective value faster in the objective space, and by strong propagation it knows if the constraints are unsatisfiable with little search ill tile problem space. To obtain strong propagation we study the use of dual encoding [1] for COP's. Our COP formulation and search strategy are general and can handle any dual COPS.
While the efficiency and scalability of modern SARI technology offers an intriguing alternative approach to constraint Solving via translation to SAT, previous work has mostly focused of the translation of specific ty...
详细信息
ISBN:
(纸本)9783540859574
While the efficiency and scalability of modern SARI technology offers an intriguing alternative approach to constraint Solving via translation to SAT, previous work has mostly focused of the translation of specific types of constraints, such as pseudo Boolean constraints;finite integer linear constraints, and constraints given as explicit listings of allowed triples. BY contrast, we present a translation of constraint models to SAT at language level, using the recently proposed constraint modeling language MiniZine, such that any satisfaction or optimization problem written in the language (not involving floats) can be automatically Booleanized and solved by one or more calls to a SAT solver. We discuss the strengths and weaknesses of such a universal constraint solver, Mid report oil a large-scale empirical evaluation of it against two existing solvers for MiniZinc: the finite domain solver distributed with MiniZinc and one based on the Gecode constraint;programming platform. our results indicate that, Booleanization indeed offers a competitive alternative, exhibiting superior performance on some classes of problems involving large numbers of constraints and complex integer arithmetic, ill addition to, naturally, problems dial arc already largely Boolean.
Many tasks in automated reasoning can be modeled as weighted constraint satisfaction problems over Boolean variables (Boolean WCSPs). Tractable classes of Such problems have traditionally been identified by exploiting...
详细信息
ISBN:
(纸本)9783540859574
Many tasks in automated reasoning can be modeled as weighted constraint satisfaction problems over Boolean variables (Boolean WCSPs). Tractable classes of Such problems have traditionally been identified by exploiting either: (a) the topology of the associated constraint network, or (b) the structure of the weighted constraints. In this paper, we introduce the notion of a constraint composite graph (CCG) associated with a given (Boolean) WCSP. the CCG provides it unifying framework for characterizing/exploiting boththe graphical structure of the constraint network as well as the structure of the weighted constraints. We show that a given (Boolean) WCSP can be reduced to the problem of computing the minimum weighted vertex cover for its associated CM and we establish the following two important results: ( 1) "the CCG of a given Boolean WCSP has the same treewidth as its associated constraint network," and (2) "many classes of Boolean WCSPs that are tractable by, virtue of the structure of their weighted constraints have associated CCGs that arc bipartite in nature."
Table constraints play an important role within constraintprogramming. Recently, many schemes or algorithms have been proposed to propagate table constraints or/and to compress their representation. We show that simp...
详细信息
ISBN:
(纸本)9783540859574
Table constraints play an important role within constraintprogramming. Recently, many schemes or algorithms have been proposed to propagate table constraints or/and to compress their representation. We show that simple tabular reduction (STR), a technique proposed by J. Ullmann to dynamically maintain the tables of Supports, is very often the most efficient practical approach to enforce generalized arc consistency within MAC. We also describe an optimization of STR which allows limiting the number of operations related to validity checking or search of supports. Interestingly enough, this optimization makes STIR potentially r times faster where r is the arity of the constraint(s). the results of an extensive experimentation that we have conducted with respect to random and structured instances indicate that the optimized algorithm we propose is usually around twice as fast its the original STR and can be up to one order of magnitude faster than previous state-of-the-art algorithms on some series of instances.
Rectangle (square) packing problems involve packing all squares with sires 1 x 1 to n x n into the minimum area enclosing rectangle (respectively, square). Rectangle packing is a variant of an important problem in a v...
详细信息
ISBN:
(纸本)9783540859574
Rectangle (square) packing problems involve packing all squares with sires 1 x 1 to n x n into the minimum area enclosing rectangle (respectively, square). Rectangle packing is a variant of an important problem in a variety of real-world settings. For example, in electronic design automation, the packing of blocks into it circuit layout is essentially a rectangle packing problem. Rectangle packing problems are also motivated by applications in scheduling. In this paper we demonstrate thin an "off-the-shelf" constraintprogramming system. SICStus Prolog. outperforms recently developed ad-hoc approaches by over three orders of magnitude. We adopt the standard cp model for these problems, and study a variety of search strategies and improvements to solve large rectangle packing problems. As well as being over three orders of magnitude faster than the current state-of-the-art, we close eight open problems: two rectangle packing problems and six square packing problems. Our approach has other advantages over the state-of-the-art, Such its being trivially modifiable to exploit multi-core computing platforms to parallelise search, although we use only a single-core in our experiments. We argue that rectangle packing is a domain where constraint pro-ramming significantly outperforms hand-crafted ad-hoc systems developed for this problem. this provides the cp community with a convincing success story.
this paper presents a global constraintthat enforces rules written in a language based on arithmetic and first-order logic to hold among a set of objects. In a first step, the rules are rewritten to Quantifier-Free P...
详细信息
ISBN:
(纸本)9783540859574
this paper presents a global constraintthat enforces rules written in a language based on arithmetic and first-order logic to hold among a set of objects. In a first step, the rules are rewritten to Quantifier-Free Presburger Arithmetic (QFPA) formulas. Secondly. such formulas arc compiled to generators of k-dimensional forbidden sets. Such generators are a generalization of the indexicals of cc(FD). Finally, the forbidden sets generated by such indexicals are aggregated by a sweep-based algorithm and used for filtering. the business rules allow to express a great variety of packing and placement constraints, while admitting effective filtering of the domain variables of the k-dimensional object, without the need to use spatial data structures.
Decomposition is it powerful technique for reducing the size of a backtracking search tree. However, when solving constraint optimization problems (COP'S) the standard technique of invoking a separate recursion to...
详细信息
ISBN:
(纸本)9783540859574
Decomposition is it powerful technique for reducing the size of a backtracking search tree. However, when solving constraint optimization problems (COP'S) the standard technique of invoking a separate recursion to solve each independent component can significantly reduce the strength of the bounds that can be applied when using branch rind bound techniques. In this paper we present a new search algorithm that can obtain many of the computational benefits of decomposition without having to resort to separate recursions. that is, the algorithm explores a standard OR tree not an AND-OR tree. In this way incremental information gathered from any component can be immediately applied to improve the bounding information for all of the other components. We also discuss how caching and local propagation can be combined with our approach and finally test our methods empirically to verify their potential.
暂无评论