New Tractable Classes From Old

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.     

一种量词约束满足问题的混合易解子类

量词约束满足问题是人工智能和自动推理领域的一个重要问题.寻找多项式时间易解子类,是研究此类问题计算复杂性的关键.通过分析二元量词约束满足问题中的约束关系特征,以及量词前缀中的全称量词排列的顺序,提出了针对全称量词变量子结构的易解性质的分析方法.通过该方法,扩展了已知的基于Broken-Triangle Property的多项式时间易解子类,提出了一个更一般化的量词约束满足问题的混合易解子类.讨论了易解子类在问题结构分析中的一个应用,即通过易解子类确定量词约束满足问题的隐蔽变量集合,并通过实验分析不同易解子类所确定的集合大小.实验改造了基于回溯算法的求解器,在回溯过程中加入了易解子类的识别算法,并采用随机约束满足问题的生成模型作为测试基准.通过对比实验,验证了提出的多项式时间易解子类可以识别出更小的隐蔽变量集合,因此,新提出的易解子类在确定隐蔽变量集合方面更具优势.最后阐述了其他已有的混合易解子类也可以通过类似方法进行扩展,从而得到更多的一般化的理论结果.     

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 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 have been shown to yield tractable classes of CSPs. However, most such restrictions fail to guarantee tractability for CSPs with global constraints. We therefore study the applicability of structural restrictions to instances with such constraints. We show that when the number of solutions to a CSP instance is bounded in key parts of the problem, structural restrictions can be used to derive new tractable classes. Furthermore, we show that this result extends to combinations of instances drawn from known tractable classes, as well as to CSP instances where constraints assign costs to satisfying assignments.     

Hybrid tractability of valued constraint problems

The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligence: it provides a common framework for many theoretical problems as well as for many real-life applications. Valued constraint problems are a generalisation of the CSP which allow the user to model optimisation problems. Considerable effort has been made in identifying properties which ensure tractability in such problems. In this work, we initiate the study of hybrid tractability of valued constraint problems; that is, properties which guarantee tractability of the given valued constraint problem, but which do not depend only on the underlying structure of the instance (such as being tree-structured) or only on the types of valued constraints in the instance (such as submodularity). We present several novel hybrid classes of valued constraint problems in which all unary constraints are allowed, which include a machine scheduling problem, constraint problems of arbitrary arities with no overlapping nogoods, and the SoftAllDiff constraint with arbitrary unary valued constraints. An important tool in our investigation will be the notion of forbidden substructures.     

Implementing a Test for Tractability

The question of determining which sets of constraints give rise to NP-complete problems, and which give rise to tractable problems, is an important open problem in the theory of constraint satisfaction. It has been shown in previous papers that certain sufficient conditions for tractability and NP-completeness can be identified using algebraic properties of relations, and that these conditions can be tested by solving a particular form of constraint satisfaction problem (the so-called indicator problem).This paper describes a program which can solve the relevant indicator problems for arbitrary sets of constraints over small domains, and for some sets of constraints over larger domains. The main innovation in the program is its ability to deal with the many symmetries present in the problem; it also has the ability to preserve symmetries in cases where this speeds up the solution.Using this program, we have systematically investigated the complexity of all individual binary relations over a domain of size four or less, and of all individual ternary relations over a domain of size three or less. This automated analysis includes the derivation of more than 450 000 new NP-completeness results, and precisely identifies the small set of individual relations which cannot be classified as either tractable or NP-complete using the algebraic conditions presented in previous papers.     

Optic flow segmentation as an ill-posed and maximum likelihood problem

It is shown how the segmentation problem encountered in the interpretation of visual motion, for example, may be formulated as an ill-posed problem using the notion of maximum likelihood to provide a general framework and guide the choice of regularizing constraints. The statistical consequences of the segmentation procedure proposed are examined and it is shown how the notion of maximum likelihood leads to a natural way of estimating parameters in the optimization function, especially the noise levels to be assigned. A minimum entropy regularization constraint is then used to ensure that the interpretation of the visual data elicits as much spatial structure as possible. It is shown by means of a ‘toy’ optic flow example how this is achieved when there are several parameter dimensions over which to segment.     

Addition and removal of information for a knowledge base with incomplete information

A knowledge base containing incomplete information in the form of disjunctions and negative information shows difficulties regarding the update operators. In this paper simple and straightforward definitions are given for an ‘adding’ operator (‘+’) and a ‘removing’ operator (‘−’) using Hebrand models.     

On the maximum acyclic subgraph problem under disjunctive constraints

Disjunctively constrained versions of classic problems in graph theory such as shortest paths, minimum spanning trees and maximum matchings were recently studied. In this article we introduce disjunctive constrained versions of the Maximum Acyclic Subgraph problem. Negative disjunctive constraints state that a certain pair of edges cannot be contained simultaneously in a feasible solution. Positive disjunctive constraints enforces that at least one arc for the underlying pair is in a feasible solution. It is convenient to represent these disjunctive constraints in terms of an undirected graph, called constraint graph, whose vertices correspond to the arcs of the original graph, and whose edges encode the disjunctive constraints. For the Maximum Acyclic Subgraph problem under Negative Disjunctive Constraints we develop 1/2-approximative algorithms that are polynomial for certain classes of constraint graphs. We also show that determining if a feasible solution exists for an instance of the Maximum Acyclic Subgraph problem under Positive Disjunctive Constraints is an NP-Complete problem.     

Canonical constraints for parameterized data types

This paper presents a comparatively general method for specifying a ‘data constraint’ on a parameterized data type (i.e., specifying just which category of algebras it is supposed to be defined or correct on), and shows that there is a simple canonical form for such constraint specifications. We also show how such constraints may be employed to give ‘loose’ specifications of data types.     

Generalizing constraint satisfaction on trees: Hybrid tractability and variable elimination

The Constraint Satisfaction Problem (CSP) is a central generic problem in artificial intelligence. Considerable progress has been made in identifying properties which ensure tractability in such problems, such as the property of being tree-structured. In this paper we introduce the broken-triangle property, which allows us to define a novel tractable class for this problem which significantly generalizes the class of problems with tree structure. We show that the broken-triangle property is conservative (i.e., it is preserved under domain reduction and hence under arc consistency operations) and that there is a polynomial-time algorithm to determine an ordering of the variables for which the broken-triangle property holds (or to determine that no such ordering exists). We also present a non-conservative extension of the broken-triangle property which is also sufficient to ensure tractability and can also be detected in polynomial time.We show that both the broken-triangle property and its extension can be used to eliminate variables, and that both of these properties provide the basis for preprocessing procedures that yield unique closures orthogonal to value elimination by enforcement of consistency. Finally, we also discuss the possibility of using the broken-triangle property in variable-ordering heuristics.     

The least-disturbance principle and weak constraints

Certain problems, notably in computer vision, involve adjusting a set of real-valued labels to satisfy certain constraints. They can be formulated as optimisation problems, using the ‘least-disturbance’ principle: the minimal alteration is made to the labels that will achieve a consistent labelling. Under certain linear constraints, the solution can be achieved iteratively and in parallel, by hill-climbing. However, where ‘weak’ constraints are imposed on the labels — constraints that may be broken at a cost — the optimisation problem becomes non-convex; a continuous search for the solution is no longer satisfactory. A strategy is proposed for this case, by construction of convex envelopes and by the use of ‘graduated’ non-convexity.     

Learning hierarchical clustering from examples — application to the adaptive construction of dissimilarity indices

A classical problem of Pattern Recognition consists in looking for an operator of classification (a ‘classifier’) induced from a learning set on which classes are known. A problem frequently encountered in practice is that of looking for an operator of clustering (a ‘clusterfier’, in opposition to ‘classifier’) from a learning set on which clusters are also known. In the first case, we have to find an operator which allocates each new object to one of the classes defined by the learning set. In the second case, we have to find an operator which detects classes in the complete population, taking in account as well as possible the information given by the classes on the learning set. We propose a new approach permitting to induce and aggregation index from knowledge acquiring on the learning set; the aggregation index thus obtained permits to induce a hierarchy which infers the desired classes on the whole population.

A nearest neighbours algorith with validity constraints has been realized to induce the final hierarchy. We obtain a CPU time clearly shorter than with the classical hierarchical ascending classification algorithm which does not use inference.

This program has permitted to find aggregation indices adapted to particular learning sets (elongated classes, spherical class with central kernel, half spherical class with central kernel, noising elongated classes…), and some of new indices permit to recognize more specific classes than the usual indices.     

相接行凸约束网络的快速识别算法

约束网络为计算机科学中的许多问题提供了一种有效的表示方法.一般而言,约束满足问题是NP完全的.然而,许多实际问题通常对约束的结构或形式施加了特殊的限制,从而能够高效地加以解决.迄今,为了识别易处理约束类,人们对特殊的约束或约束网络方面进行了许多研究.相接行凸(connected row-convex,简称CRC)约束网络是Deville等人提出的一类易处理问题.为了给该类问题寻求有效的快速识别算法,在CRC约束网络相关工作基础上,提出了CRC约束矩阵的标准型.在分析CRC约束矩阵的标准型性质的基础上,利用行凸(row-convex,简称RC)约束网络的判定,结合PQ树(由P节点和Q节点构成的树)的性质和矩阵的索引表示法,给出了CRC约束网络的快速识别算法.该算法的时间复杂度为O(n³d²),其中,n为约束网络涉及的变量数,d为各变量的定义域中最大定义域的大小.该时间复杂度达到该类问题的最佳时间复杂度,从而为实际的CRC约束满足问题的求解提供了可行的方法.     

Tractable Decision for a Constraint Language Implies Tractable Search

A constraint satisfaction problem (CSP) instance has a set of variables, each of which can take values in some domain. It also has a set of constraints, each of which restricts the variables in its scope to take values limited by its constraint relation.The language of a constraint satisfaction problem instance is the set of different constraint relations used in its specification. For a given set of relations over some domain we define the problem CSP () to the set of CSP instances whose language is contained in .The decision problem for a set of CSP instances is, given an instance in the class, to decide whether a solution exists. The search problem is to find such a solution. Here we address the connection between the tractability of the decision and search problems. We prove that given a constraint language over a finite domain for which the decision problem for CSP () is tractable, the search problem is always tractable.We define a surjective language over a finite domain in a standard way. We also show that we can determine in polynomial time whether an instance over a surjective language with a tractable decision problem has fewer than k solutions, and that we can generate all of its solutions with polynomial delay.     

Periodic Constraint Satisfaction Problems: Tractable Subclasses

We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of generating constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints; the problem is to decide whether or not the larger set of constraints has a satisfying assignment. This model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP.     

A polynomial relational class of binary CSP

Finding a solution to a constraint satisfaction problem (CSP) is known to be an NP-hard task. Considerable effort has been spent on identifying tractable classes of CSP, in other words, classes of constraint satisfaction problems for which there are polynomial time recognition and resolution algorithms. In this article, we present a relational tractable class of binary CSP. Our key contribution is a new ternary operation that we name mjx. We first characterize mjx-closed relations which leads to an optimal algorithm to recognize such relations. To reduce space and time complexity, we define a new storage technique for these relations which reduces the complexity of establishing a form of strong directional path consistency, the consistency level that solves all instances of the proposed class (and, indeed, of all relational classes closed under a majority polymorphism).     

Complexity of Clausal Constraints Over Chains

We investigate the complexity of the satisfiability problem of constraints over finite totally ordered domains. In our context, a clausal constraint is a disjunction of inequalities of the form x≥d and x≤d. We classify the complexity of constraints based on clausal patterns. A pattern abstracts away from variables and contains only information about the domain elements and the type of inequalities occurring in a constraint. Every finite set of patterns gives rise to a (clausal) constraint satisfaction problem in which all constraints in instances must have an allowed pattern. We prove that every such problem is either polynomially decidable or NP-complete, and give a polynomial-time algorithm for recognizing the tractable cases. Some of these tractable cases are new and have not been previously identified in the literature.     

Consistency techniques for continuous constraints

We consider constraint satisfaction problems with variables in continuous, numerical domains. Contrary to most existing techniques, which focus on computing one single optimal solution, we address the problem of computing a compact representation of the space of all solutions admitted by the constraints. In particular, we show how globally consistent (also called decomposable) labelings of a constraint satisfaction problem can be computed.Our approach is based on approximating regions of feasible solutions by 2 ^k -trees, a representation commonly used in computer vision and image processing. We give simple and stable algorithms for computing labelings with arbitrary degrees of consistency. The algorithms can process constraints and solution spaces of arbitrary complexity, but with a fixed maximal resolution.Previous work has shown that when constraints are convex and binary, path-consistency is sufficient to ensure global consistency. We show that for continuous domains, this result can be generalized to ternary and in fact arbitrary n-ary constraints using the concept of (3,2)-relational consistency. This leads to polynomial-time algorithms for computing globally consistent labelings for a large class of constraint satisfaction problems with continuous variables.     

Structural tractability of enumerating CSP solutions

The problem of deciding whether CSP instances admit solutions has been deeply studied in the literature, and several structural tractability results have been derived so far. However, constraint satisfaction comes in practice as a computation problem where the focus is either on finding one solution, or on enumerating all solutions, possibly projected to some given set of output variables. The paper investigates the structural tractability of the problem of enumerating (possibly projected) solutions, where tractability means here computable with polynomial delay (WPD), since in general exponentially many solutions may be computed. A framework based on the notion of tree projection of hypergraphs is considered, which generalizes all structural decomposition methods that are based on decomposing a given instance into suitable tree-like groups of polynomial-time computable subproblems. Tractability results have been obtained both for classes of structures where output variables are part of their specification, and for classes of structures where computability WPD must be ensured for any possible set of output variables. By exhibiting dichotomies, these results are shown to be tight for classes of structures having bounded arity.