Lifting Structural Tractability to CSP with Global Constraints
A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or implicitly, by special-purpose algorithms provided by a solver. Such implicitly represented constraints, known as global constraints, are widely used; indeed, they are one of the key reasons for the success of constraint programming in solving real-world problems. In recent years, a variety of restrictions on the structure of CSP instances that yield tractable classes have been identified. However, many such restrictions fail to guarantee tractability for CSPs with global constraints. In this paper, we investigate the properties of extensionally represented constraints that these restrictions exploit to achieve tractability, and show that there are large classes of global constraints that also possess these properties. This allows us to lift these restrictions to the global case, and identify new tractable classes of CSPs with global constraints.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Structural Decompositions for Problems with Global Constraints
A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly…
A Structural Complexity Analysis of Hierarchical Task Network Planning
We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network Planning: the verification of a provided plan, whether an executable plan exists, and whether a g…
NP-hardness of sortedness constraints
In Constraint Programming, global constraints allow to model and solve many combinatorial problems. Among these constraints, several sortedness constraints have been defined, for which propagation algorithms are availabl…
LiftPool: Lifting-based Graph Pooling for Hierarchical Graph Representation Learning
Graph pooling has been increasingly considered for graph neural networks (GNNs) to facilitate hierarchical graph representation learning. Existing graph pooling methods commonly consist of two stages, i.e., selecting the…
Graph ClassificationGraph Representation LearningRepresentation LearningAn Optimal Control Approach To Transformer Training
In this paper, we develop a rigorous optimal control-theoretic approach to Transformer training that respects key structural constraints such as (i) realized-input-independence during execution, (ii) the ensemble control…