In CP literature combinatorial design problems such as sport scheduling, Steiner systems, error-correcting codes and more, are typically solved using Finite Domain (FD) models despite often being more naturally expres...
详细信息
ISBN:
(纸本)3540232419
In CP literature combinatorial design problems such as sport scheduling, Steiner systems, error-correcting codes and more, are typically solved using Finite Domain (FD) models despite often being more naturally expressed as Finite Set (FS) models. Existing FS solvers have difficulty with such problems as they do not make strong use of the ubiquitous set cardinality information. We investigate a new approach to strengthen the propagation of FS constraints in a tractable way: extending the domain representation to more closely approximate the true domain of a set variable. We show how this approach allows us to reach a stronger level of consistency, compared to standard FS solvers, for arbitrary constraints as well as providing a mechanism for implementing certain symmetry breaking constraints. By experiments on Steiner Systems and error correcting codes, we demonstrate that our approach is not only an improvement over standard FS solvers but also an improvement on recently published results using FD 0/1 matrix models as well.
Great progress has been made on DPLL based SAT solvers operating on CNF encoded SAT theories. However, for most problems CNF is not a very natural representation. Typically these problems are more easily expressed usi...
详细信息
ISBN:
(纸本)3540232419
Great progress has been made on DPLL based SAT solvers operating on CNF encoded SAT theories. However, for most problems CNF is not a very natural representation. Typically these problems are more easily expressed using unrestricted propositional formulae and hence must be converted to CNF before modem SAT solvers can be applied. this conversion entails a considerable loss of information about the problem's structure. In this work we demonstrate that conversion to CNF is both unnecessary and undesirable. In particular, we demonstrate that a SAT solver which operates directly on a propositional formula can achieve the same efficiency as a highly optimized modern CNF solver. Furthermore, since the original formula remains intact, such a solver can exploit the original problem structure to improve over CNF solvers. We present empirical evidence showing that exploiting the original structure can yield considerable benefits.
Until recently, planning research focused on solving problems of feasibility using models consisting of causal rules. Propositional logic is sufficient for representing such rules. However, many planning problems also...
ISBN:
(纸本)3540232419
Until recently, planning research focused on solving problems of feasibility using models consisting of causal rules. Propositional logic is sufficient for representing such rules. However, many planning problems also contain time and resource constraints. It is often impractical to represent such planning domains with propositions. Large time horizons and possible resource states lead to enormous domain representations. Propositional representations can often obscure information that is useful during search. Finally, propositional representations can make it difficult for human modelers to express the domain in a convenient and natural way. the constraint-based Planning paradigm employs constraints as the building blocks of both planning domain rules and plans. the building blocks of such plans are intervals of time over which some state holds or an action occurs in a plan. Each interval is represented by variables describing its properties (e.g. start, end, duration). At each step of the planning process, a mapping is maintained between the plan under construction and an underlying constraint network. As actions are added to the plan, constraints are posted on variables representing the action, its preconditions and its effects (a generalization of causal links). the domain rules contain directives for adding new intervals and for posting constraints over the variables on those intervals as plans are modified. Employing constraints in rules makes it easy to represent disjunctive preconditions, conditional effects, and mutual exclusions directly. the semantics of this mapping ensure that logical inference (e.g. propagation) on the constraint network can be used directly by search engines operating on plans.
We combine mixed integer linear programming (MILP) and constraintprogramming (CP) to solve planning and scheduling problems. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked...
详细信息
this paper presents an algorithm that achieves hyper-arc consistency for the soft alldifferent constraint. To this end, we prove and exploit the equivalence with a minimum-cost flow problem. Consistency of the constra...
详细信息
Generating all constitutional isomers (chemical compounds that have the same molecular formula but different chemical structures) is a challenging problem. the structures are normally represented by molecular graphs, ...
ISBN:
(纸本)3540232419
Generating all constitutional isomers (chemical compounds that have the same molecular formula but different chemical structures) is a challenging problem. the structures are normally represented by molecular graphs, where vertices are atoms and edges are chemical bonds. the degree of a vertex in the graph represents the valency of the corresponding atom. the problem can be extended to generating all sets of molecules that can result from a reaction. I have formulated this chemistry problem as a constraint satisfaction problem (CSP). As an initial representation of the problem, I represent each bond as a pair of variables. the atoms are represented by integers and connected by the bonds. the domain of each variable is all of the atoms in the problem. Each atom must appear a fixed number of times (its valency). For example, consider a problem that consists of two oxygens, two carbons and four hydrogens, i.e. eight atoms in three types. the number of bonds is half the sum of the atoms valencies. For the sample problem we need 8 bonds. It is easy to specify the valency constraint with help of the Ilog Solver constraint IloDistribute, which restricts the appearance of variables that take a given value in an array. We believe this is the first constraint encoding of the problem.
Although algorithms for Distributed constraint Optimization Problems (DCOPs) have emerged as a key technique for distributed reasoning, their application faces significant hurdles in many multiagent domains due to the...
详细信息
the paper introduces value precedence on integer and set sequences. A useful application of the notion is in breaking symmetries of indistinguishable values, an important class of symmetries in practice. Although valu...
详细信息
We study the global cardinality constraint (gcc) and propose an O(n1.5d) algorithm for domain consistency and an O(cn + dn) algorithm for range consistency where n is the number of variables, d the number of values in...
详细信息
We introduce a new approach for focusing constraint reasoning using so-called streamlining constraints. Such constraints partition the solution space to drive the search first towards a small and structured combinator...
详细信息
暂无评论