Dulmage-Mendelsohn Canonical Decomposition as a generic pruning technique

We introduce a new generic propagation mechanism for constraint programming. A first advantage of our pruning technique stems from the fact that it can be applied on various global constraints. In this work we describe a filtering scheme for such a family based on Dulmage-Mendelsohn Structure Theorem. Our method checks the feasibility in polynomial time and then ensures hyper-arc consistency in linear time. It is also applicable to any soft version of global constraint expressed in terms of a maximum matching in a bipartite graph and remains of linear complexity.     

Boosting MUC extraction in unsatisfiable constraint networks

One very fertile domain of applied Artificial Intelligence is constraint solving technologies. Especially, constraint networks that concern problems that can be represented using discrete variables, together with constraints on allowed instantiation values for these variables. Every solution to a constraint network must satisfy every constraint. When no solution exists, the user might want to know the actual reasons leading to the absence of global solution. In this respect, extracting mucs (Minimal Unsatisfiable Cores) from an unsatisfiable constraint network is a useful process when causes of unsatisfiability must be understood so that the network can be re-engineered and relaxed to become satisfiable. Despite bad worst-case computational complexity results, various muc-finding approaches that appear tractable for many real-life instances have been proposed. Many of them are based on the successive identification of so-called transition constraints. In this respect, we show how local search can be used to possibly extract additional transition constraints at each main iteration step. In the general constraint networks setting, the approach is shown to outperform a technique based on a form of model rotation imported from the sat-related technology and that also exhibits additional transition constraints. Our extensive computational experimentations show that this enhancement also boosts the performance of state-of-the-art DC(WCORE)-like MUC extractors.     

The complexity of constraint satisfaction games and QCSP

We study the complexity of two-person constraint satisfaction games. An instance of such a game is given by a collection of constraints on overlapping sets of variables, and the two players alternately make moves assigning values from a finite domain to the variables, in a specified order. The first player tries to satisfy all constraints, while the other tries to break at least one constraint; the goal is to decide whether the first player has a winning strategy. We show that such games can be conveniently represented by a logical form of quantified constraint satisfaction, where an instance is given by a first-order sentence in which quantifiers alternate and the quantifier-free part is a conjunction of (positive) atomic formulas; the goal is to decide whether the sentence is true.While the problem of deciding such a game is PSPACE-complete in general, by restricting the set of allowed constraint predicates, one can obtain infinite classes of constraint satisfaction games of lower complexity. We use the quantified constraint satisfaction framework to study how the complexity of deciding such a game depends on the parameter set of allowed predicates. With every predicate, one can associate certain predicate-preserving operations, called polymorphisms. We show that the complexity of our games is determined by the surjective polymorphisms of the constraint predicates. We illustrate how this result can be used by identifying the complexity of a wide variety of constraint satisfaction games.     

Constraints—A language for expressing almost-hierarchical descriptions

We present an interactive system organized around networks of constraints rather than the programs which manipulate them. We describe a language of hierarchical constraint networks. We describe one method of deriving useful consequences of a set of constraints which we call propagation. Dependency analysis is used to spot and track down inconsistent subsets of a constraint set. Propagation of constraints is most flexible and useful when coupled with the ability to perform symbolic manipulations on algebraic expressions. Such manipulations are in turn best expressed as alterations or augmentations of the constraint network.Almost-Hierarchical Constraint Networks can be constructed to represent the multiple viewpoints used by engineers in the synthesis and analysis of electrical networks. These multiple viewpoints are used in terminal equivalence and power arguments to reduce the apparent synergy in a circuit so that it can be attacked algebraically.     

Applying Ad-hoc Global Constraints with the {\tt case} Constraint to Still-Life

The Still-Life problem is challenging for CP techniques because the basic constraints of the game of Life are loose and give poor propagation for Still-Life. In this paper, we show how ad hoc global constraints can be customized to construct various models to provide much stronger propagation with CP solvers. Since we use custom ad hoc constraints of high arity where the number of tuples to define the constraint are large, the actual constraint representation becomes important to avoid excessive space consumption. We demonstrate how to use BDDs to construct good representations for the constraint which is critical for efficiency. Our results seem comparable to hybrid CP/IP models even though we are only using propagation albeit on ad hoc global constraints. This paper shows an extensive example of how to systematically build models using different kinds of ad hoc constraints. It also demonstrates the solving potential of ad hoc global constraints.     

Optimization-Oriented Global Constraints

In this paper, we propose a way of exploiting Operations Research techniques within global constraints for cost-based domain filtering. In Constraint Programming, constraint propagation is aimed at removing from variable domains combinations of values which are proven infeasible. Pruning derives from feasibility reasoning. When coping with optimization problems, pruning can be performed also on the basis of costs, i.e., optimality reasoning. Cost-based filtering removes combination of values which are proven sub-optimal. For this purpose, we encapsulate in global constraints optimization components representing suitable relaxations of the constraint itself. These components embed efficient Operations Research algorithms computing the optimal solution of the relaxed problem and a gradient function representing the estimated cost of each variable-value assignment. We exploit these pieces of information for pruning and for guiding the search. We have applied these techniques to a couple of ILOG Solver global constraints (a constraint of difference and a path constraint) and tested the approach on a variety of combinatorial optimization problems such as Timetabling, Travelling Salesman Problems and Scheduling Problems with sequence dependent setup times. Comparisons with pure Constraint Programming approaches and related literature clearly show the benefits of the proposed approach.     

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.     

An optimal coarse-grained arc consistency algorithm

The use of constraint propagation is the main feature of any constraint solver. It is thus of prime importance to manage the propagation in an efficient and effective fashion. There are two classes of propagation algorithms for general constraints: fine-grained algorithms where the removal of a value for a variable will be propagated to the corresponding values for other variables, and coarse-grained algorithms where the removal of a value will be propagated to the related variables. One big advantage of coarse-grained algorithms, like AC-3, over fine-grained algorithms, like AC-4, is the ease of integration when implementing an algorithm in a constraint solver. However, fine-grained algorithms usually have optimal worst case time complexity while coarse-grained algorithms do not. For example, AC-3 is an algorithm with non-optimal worst case complexity although it is simple, efficient in practice, and widely used. In this paper we propose a coarse-grained algorithm, AC2001/3.1, that is worst case optimal and preserves as much as possible the ease of its integration into a solver (no heavy data structure to be maintained during search). Experimental results show that AC2001/3.1 is competitive with the best fine-grained algorithms such as AC-6. The idea behind the new algorithm can immediately be applied to obtain a path consistency algorithm that has the best-known time and space complexity. The same idea is then extended to non-binary constraints.     

基于SDN分级分域架构的QoS约束路由算法

传统分布式的网络架构制约路由算法的创新,软件定义网络的出现为路由算法的优化提供了新思路。已有研究中,启发式算法广泛应用于服务质量路由,但由于计算复杂度高而无法在大型网络中应用。而其他算法均存在不同程度的问题,要么复杂度较高,要么算法性能较差,如最短路径算法。基于 SDN 分级分域架构,提出了 LC-LD 路由算法,综合时延条件和代价度量约束并在计算复杂度和算法性能之间保持平衡。仿真分析表明,LC-LD路由算法在有较低的计算复杂度的同时还有较高的服务质量路由选路性能。     

A Foundation of Solution Methods for Constraint Hierarchies

Constraint hierarchies provide a framework for soft constraints, and have been applied to areas such as artificial intelligence, logic programming, and user interfaces. In this framework, constraints are associated with hierarchical preferences or priorities called strengths, and may be relaxed if they conflict with stronger constraints. To utilize constraint hierarchies, researchers have designed and implemented various practical constraint satisfaction algorithms. Although existing algorithms can be categorized into several approaches, what kinds of algorithms are possible has been unclear from a more general viewpoint. In this paper, we propose a novel theory called generalized local propagation as a foundation of algorithms for solving constraint hierarchies. This theory formalizes a way to express algorithms as constraint scheduling, and presents theorems that support possible approaches. A benefit of this theory is that it covers algorithms using constraint hierarchy solution criteria known as global comparators, for which only a small number of algorithms have been implemented. With this theory, we provide a new classification of solution criteria based on their difficulties in constraint satisfaction. We also discuss how existing algorithms are related to our theory, which will be helpful in designing new algorithms.     

Local reasoning and knowledge compilation for efficient temporal abduction

Generating abductive explanations is the basis of several problem solving activities such as diagnosis, planning, and interpretation. Temporal abduction means generating explanations that do not only account for the presence of observations, but also for temporal information on them, based on temporal knowledge in the domain theory. We focus on the case where such a theory contains temporal constraints that are required to be consistent with temporal information on observations. Our aim is to propose efficient algorithms for computing temporal abductive explanations. Temporal constraints in the theory and in the observations can be used actively by an abductive reasoner in order to prune inconsistent candidate explanations at an early stage during their generation. However, checking temporal constraint satisfaction frequently generates some overhead. We analyze two incremental ways of making this process efficient. First we show how, using a specific class of temporal constraints (which is expressive enough for many applications), such an overhead can be reduced significantly, yet preserving a full pruning power. In general, the approach does not affect the asymptotic complexity of the problem, but it provides significant advantages in practical cases. We also show that, for some special classes of theories, the asymptotic complexity is also reduced. We then show how, compiled knowledge based on temporal information, can be used to further improve the computation, thus, extending to the temporal framework previous results in the case of atemporal abduction. The paper provides both analytic and experimental evaluations of the computational advantages provided by our approaches.     

Bases for Boolean co-clones

The complexity of various problems in connection with Boolean constraints, like, for example, quantified Boolean constraint satisfaction, have been studied recently. Depending on what types of constraints may be used, the complexity of such problems varies. A very interesting observation of the recent past has been that the thus derived classification of constraints can be explained with the help of universal algebra. More precisely, the difficulty of such a constraint problem often depends on the co-clone the constraints are from. A co-clone is a set of Boolean relations that is closed under very natural closure operations. Nearly all these co-clones can be generated by said operators out of a finite set of relations, a so-called base. Knowing a, preferably simple, base for each co-clone can therefore be of great value when studying the complexity of Boolean constraint problems, since this knowledge reduces the infinitely many cases of equivalent problems to a single one—the constraint satisfaction problem for this base. In this paper we give a finite and simple base for every Boolean co-clone, where this is possible. We give evidence that the presented bases are as easy as possible.     

Variable partial-update NLMS algorithms with data-selective updating

We note that some existing algorithms are based on the normalized least-mean square （NLMS） algorithm and aim to reduce the computational complexity of NLMS all inherited from the solution of the same optimization problem, but with different constraints. A new constraint is analyzed to substitute an extra searching technique in the set-membership partial-update NLMS algorithm （SM-PU-NLMS） which aims to get a variable number of updating coefficients for a further reduction of computational complexity. We get a closed form expression of the new constraint without extra searching technique to generate a novel set-membership variable-partial-update NLMS （SM-VPU-NLMS） algorithm. Note that tile SM-VPU-NLMS algorithm obtains a faster convergence and a smaller mean-squared error （MSE） than the existing SM-PU-NLMS. It is pointed out that the closed form expression can also be applied to the conventional variable-step-size partial-update NLMS （VSS-PU-NLMS） algorithm. The novel variable-step-size variable-partial-update NLMS （VSS-VPU-NLMS） algorithm is also verified to get a further computational complexity reduction. Simulation results verify that our analysis is reasonable and effective.     

PAIDD: a hybrid P2P-based architecture for improving data distribution in social networks

Rapid growth in social networks(SNs)presents a unique scalability challenge for SN operators because of the massive amounts of data distribution among large number of concurrent online users.A request from any user may trigger hundreds of server activities to generate a customized page and which has already become a huge burden.Based on the theoretical model and analytical study considering realistic network scenarios,this article proposes a hybrid P2P-based architecture called PAIDD.PAIDD fulfills effective data distribution primarily through P2P connectivity and social graph among users but with the help of central servers.To increase system efficiency,PAIDD performs optimized content prefetching based on social interactions among users.PAIDD chooses interaction as the criteria because user’s interaction graph is measured to be much smaller than the social graph.Our experiments confirm that PAIDD ensures satisfactory user experience without incurring extensive overhead on clients’network.More importantly,PAIDD can effectively achieve one order of magnitude of load reduction at central servers.     

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.     

Filtering algorithms for the multiset ordering constraint

Constraint programming (CP) has been used with great success to tackle a wide variety of constraint satisfaction problems which are computationally intractable in general. Global constraints are one of the important factors behind the success of CP. In this paper, we study a new global constraint, the multiset ordering constraint, which is shown to be useful in symmetry breaking and searching for leximin optimal solutions in CP. We propose efficient and effective filtering algorithms for propagating this global constraint. We show that the algorithms maintain generalised arc-consistency and we discuss possible extensions. We also consider alternative propagation methods based on existing constraints in CP toolkits. Our experimental results on a number of benchmark problems demonstrate that propagating the multiset ordering constraint via a dedicated algorithm can be very beneficial.     

Improving machine dynamics via geometry optimization

The central thesis of this paper is that the dynamic performance of machinery can be improved dramatically in certain cases through a systematic and meticulous evolutionary algorithm search through the space of all structural geometries permitted by manufacturing, cost and functional constraints. This is a cheap and elegant approach in scenarios where employing active control elements is impractical for reasons of cost and complexity. From an optimization perspective the challenge lies in the efficient, yet thorough global exploration of the multi-dimensional and multi-modal design spaces often yielded by such problems. Moreover, the designs are often defined by a mixture of continuous and discrete variables—a task that evolutionary algorithms appear to be ideally suited for. In this article we discuss the specific case of the optimization of crop spraying machinery for improved uniformity of spray deposition, subject to structural weight and manufacturing constraints. Using a mixed variable evolutionary algorithm allowed us to optimize both shape and topology. Through this process we have managed to reduce the maximum roll angle of the sprayer by an order of magnitude, whilst allowing only relatively inexpensive changes to the baseline design. Further (though less dramatic) improvements were shown to be possible when we relaxed the cost constraint. We applied the same approach to the inverse problem of reducing the mass while maintaining an acceptable roll angle—a 2% improvement proved possible in this case.     

View-based propagation of decomposable constraints

Constraints that may be obtained by composition from simpler constraints are present, in some way or another, in almost every constraint program. The decomposition of such constraints is a standard technique for obtaining an adequate propagation algorithm from a combination of propagators designed for simpler constraints. The decomposition approach is appealing in several ways. Firstly because creating a specific propagator for every constraint is clearly infeasible since the number of constraints is infinite. Secondly, because designing a propagation algorithm for complex constraints can be very challenging. Finally, reusing existing propagators allows to reduce the size of code to be developed and maintained. Traditionally, constraint solvers automatically decompose constraints into simpler ones using additional auxiliary variables and propagators, or expect the users to perform such decomposition themselves, eventually leading to the same propagation model. In this paper we explore views, an alternative way to create efficient propagators for such constraints in a modular, simple and correct way, which avoids the introduction of auxiliary variables and propagators.     

Accelerating column generation for aircraft scheduling using constraint propagation

We discuss how constraint programming can improve the performance of a column generation solution process for the NP-hard Tail Assignment problem in aircraft scheduling. Combining a constraint model of a relaxed Tail Assignment problem with column generation, we achieve substantially improved performance. A generalized preprocessing technique based on constraint propagation is presented that can dramatically reduce the size of the flight network. We also present a heuristic preprocessing method based on the costs of connections, and show how constraint propagation can be used to improve fixing heuristics. Proof of concept is provided using real world Tail Assignment instances.