Cost-Based Arc Consistency for Global Cardinality Constraints

A global cardinality constraint (gcc) is specified in terms of a set of variables X={x ₁,...,x _p} which take their values in a subset of V={v ₁,...,v _d}. It constrains the number of times each value v _iV is assigned to a variable in X to be in an interval [l _i,u _i]. A gcc with costs (costgcc) is a generalization of a gcc in which a cost is associated with each value of each variable. Then, each solution of the underlying gcc is associated with a global cost equal to the sum of the costs associated with the assigned values of the solution. A costgcc constrains the global cost to be less than a given value. Cardinality constraints with costs have proved very useful in many real-life problems, such as traveling salesman problems, scheduling, rostering, or resource allocation. For instance, they are useful for expressing preferences or for defining constraints such as a constraint on the sum of all different variables. In this paper, we present an efficient way of implementing arc consistency for a costgcc. We also study the incremental behavior of the proposed algorithm.     

The extended global cardinality constraint: An empirical survey

The Extended Global Cardinality Constraint (EGCC) is a vital component of constraint solving systems, since it is very widely used to model diverse problems. The literature contains many different versions of this constraint, which trade strength of inference against computational cost. In this paper, I focus on the highest strength of inference usually considered, enforcing generalized arc consistency (GAC) on the target variables. This work is an extensive empirical survey of algorithms and optimizations, considering both GAC on the target variables, and tightening the bounds of the cardinality variables. I evaluate a number of key techniques from the literature, and report important implementation details of those techniques, which have often not been described in published papers. Two new optimizations are proposed for EGCC. One of the novel optimizations (dynamic partitioning, generalized from AllDifferent) was found to speed up search by 5.6 times in the best case and 1.56 times on average, while exploring the same search tree. The empirical work represents by far the most extensive set of experiments on variants of algorithms for EGCC. Overall, the best combination of optimizations gives a mean speedup of 4.11 times compared to the same implementation without the optimizations.     

Complete Bound Consistency for the Global Cardinality Constraint

We show an algorithm for bound consistency of global cardinality constraints, which runs in time O(n + n′) plus the time required to sort the assignment variables by range endpoints, where n is the number of assignment variables and n′ is the number of values in the union of their domains. It is the first efficient algorithm that achieves bound consistency for all variables, and not only the assignment variables.Partially supported by DFG grant SA 933/1-1.Partially supported by the EU IST Programme, IST-1999-14186 (ALCOM-FT).     

The Complexity of Reasoning with Global Constraints

Constraint propagation is one of the techniques central to the success of constraint programming. To reduce search, fast algorithms associated with each constraint prune the domains of variables. With global (or non-binary) constraints, the cost of such propagation may be much greater than the quadratic cost for binary constraints. We therefore study the computational complexity of reasoning with global constraints. We first characterise a number of important questions related to constraint propagation. We show that such questions are intractable in general, and identify dependencies between the tractability and intractability of the different questions. We then demonstrate how the tools of computational complexity can be used in the design and analysis of specific global constraints. In particular, we illustrate how computational complexity can be used to determine when a lesser level of local consistency should be enforced, when constraints can be safely generalized, when decomposing constraints will reduce the amount of pruning, and when combining constraints is tractable.     

Robustness of a Spline Element Method with Constraints

The spline element method with constraints is a discretization method where the unknowns are expanded as polynomials on each element and Lagrange multipliers are used to enforce the interelement conditions, the boundary conditions and the constraints in numerical solution of partial differential equations. Spaces of piecewise polynomials with global smoothness conditions are known as multivariate splines and have been extensively studied using the Bernstein-Bézier representation of polynomials. It is used here to write the constraints mentioned above as linear equations. In this paper, we illustrate the robustness of this approach on two singular perturbation problems, a fourth order problem and a Stokes-Darcy flow. It is shown that the method converges uniformly in the perturbation parameter.     

Combining Tree Partitioning,Precedence, and Incomparability Constraints

The tree constraint partitions a directed graph into node-disjoint trees. In many practical applications that involve such a partition, there exist side constraints specifying requirements on tree count, node degrees, or precedences and incomparabilities within node subsets. We present a generalisation of the tree constraint that incorporates such side constraints. The key point of our approach is to take partially into account the strong interactions between the tree partitioning problem and all the side constraints, in order to avoid thrashing during search. We describe filtering rules for this extended tree constraint and evaluate its effectiveness on three applications: the Hamiltonian path problem, the ordered disjoint paths problem, and the phylogenetic supertree problem. Some of this work was done while the second author was Visiting Faculty Member and Erasmus Exchange Teacher at Sabancı University in İstanbul, Turkey, during the academic year 2006/2007.     

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.     

Reformulation of Global Constraints Based on Constraints Checkers

This article deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in n, where n is the number of variables of the corresponding global constraint. By reducing the automaton to a conjunction of signature and transition constraints we show how to systematically obtain an automaton reformulation. Under some restrictions on the signature and transition constraints, this reformulation maintains arc-consistency. An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available. For a restricted class of automata we provide an automaton reformulation for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.     

Temporal Constraints: A Survey

Temporal Constraint Satisfaction is an information technology useful for representing and answering queries about temporal occurrences and temporal relations between them. Information is represented as a Constraint Satisfaction Problem (CSP) where variables denote event times and constraints represent the possible temporal relations between them. The main tasks are two: (i) deciding consistency, and (ii) answering queries about scenarios that satisfy all constraints. This paper overviews results on several classes of Temporal CSPs: qualitative interval, qualitative point, metric point, and some of their combinations. Research has progressed along three lines: (i) identifying tractable subclasses, (ii) developing exact search algorithms, and (iii) developing polynomial-time approximation algorithms. Most available techniques are based on two principles: (i) enforcing local consistency (e.g. path-consistency) and (ii) enhancing naive backtracking search.     

A parametric filtering algorithm for the graph isomorphism problem

We introduce a new filtering algorithm, called IDL(d)-filtering, for a global constraint dedicated to the graph isomorphism problem—the goal of which is to decide if two given graphs have an identical structure. The basic idea of IDL(d)-filtering is to label every vertex with respect to its relationships with other vertices around it in the graph, and to use these labels to filter domains by removing values that have different labels. IDL(d)-filtering is parameterized by a positive integer value d which gives a limit on the distance between a vertex to be labelled and the set of vertices considered to build its label. We experimentally compare different instantiations of IDL(d)-filtering with state-of-the-art dedicated algorithms and show that IDL(d)-filtering is more efficient on regular sparse graphs and competitive on other kinds of graphs.     

基于全局和局部约束直推学习的鲁棒跟踪研究

在目标跟踪中, 大部分算法都是假设目标亮度不变或者目标子空间不变, 然而, 这些假设在实际场景中并不一定满足, 特别是当目标和背景都发生较大变化时, 目标容易丢失. 针对这种情况, 本文从直推学习的角度重新描述跟踪问题, 并提出一种鲁棒的目标跟踪方法.为获得更好的跟踪效果, 目标当前状态估计不仅要逼近目标模型, 而且要与以前的结果具有相同的聚类. 本方法利用目标模型对跟踪问题进行全局约束, 利用以前的结果约束状态局部分布, 构造代价函数. 将以前的状态估计作为正样本, 当前的候选状态作为未标记样本, 以所有样本为顶点建立图, 同时学习目标的全局外观模型和所有状态的局部聚类结构. 最后利用图拉普拉斯, 通过简单的线性代数运算, 获得代价函数的最优解. 在实验中, 选取包含各种情形的视频, 如目标的姿势改变、表情变化、部分遮挡以及周围光照的变化等, 利用本文提出的方法测试, 并和其他算法比较. 实验结果表明, 本文方法能够很好处理这些情形, 实现对目标的鲁棒跟踪.     

Maintaining Global Integrity Constraints in Distributed Databases

Given some integrity constraints over a distributed database, we consider the problem of incrementally checking global consistency in response to updates made to the base relations but without accessing all these base relations. In many application areas such as collaborative design, mobile computing and enterprise information systems, total data availability cannot be assumed. Even if all the base data is available, some of it may incur such a high cost that its use should only be considered as a last resort. Without looking at all the relations that participate in the constraint, how can one meaningfully check a constraint for violation? When the constraint is known to be satisfied prior to the update, the state of the relations that are available (aka local) can in principle be used to infer something about the relations that are not available (aka remote). This observation is the basis for the existence of tests that guarantee that global consistency is preserved under a given update, without looking at all the base data. In order to make consistency maintenance practical, the challenge is to find those tests that are most general (we call Complete Local Tests) and that are efficient to generate and execute. This paper addresses the problem of finding efficient complete local tests for an important class of constraints that are very common in practice: constraints expressible as conjunctive queries with negated subgoals. For constraints where the predicates for the remote relations do not occur more than once, we present complete local tests under insertions and deletions to the local relations. These tests can be expressed as safe, nonrecursive Datalog ¬ queries against the local relations. These results also apply to other constraints with negation that are not conjunctive.     

Cost-based Filtering for Shorter Path Constraints

Many real world problems, e.g. personnel scheduling and transportation planning, can be modeled naturally as Constrained Shortest Path Problems (CSPPs), i.e., as Shortest Path Problems with additional constraints. A well studied problem in this class is the Resource Constrained Shortest Path Problem. Reduction techniques are vital ingredients of solvers for the CSPP, that is frequently NP-hard, depending on the nature of the additional constraints. Viewed as heuristics, these techniques have not been studied theoretically with respect to their efficiency, i.e., with respect to the relation of filtering power and running time. Using the concepts of Constraint Programming, we provide a theoretical study of cost-based filtering for shorter path constraints on acyclic, on undirected, and on directed graphs that do not contain negative cycles. We then show empirically how reasoning about path-substructures in combination with CP-based Lagrangian relaxation can help to improve significantly over previously developed problem-tailored filtering algorithms for the resource constrained shortest path problem and investigate the impact of required-edge detection, undirected versus directed filtering, and the choice of the algorithm optimizing the Lagrangian dual.     

基于全局空间约束块匹配的目标人体识别

目标人体识别即非重叠多摄像系统中人的重现(person re-identification)问题,当前多数的目标人体识别都是通过提取人体表观特征,并利用特征的相似性对目标人体进行重识别,这些方法对于一些大部分表观区域相似而小部分区域不同的行人仍然无法给出准确的识别结果.考虑到目标人体识别中的行人几乎都处于站立姿势,同一行人的不同图像在垂直方向上的全局结构比不同行人间的更加相似.在基于稠密块匹配的基础上,提出了全局空间约束块匹配的识别方法.该方法不仅考虑2幅图像中局部块的匹配,还考虑各块在自身图像中垂直方向上的全局空间约束.为了减少背景对识别的负面影响,采用姿势评估的方法来提取大致的人体前景.在实验中,提出的方法在经过最具挑战的公用VIPeR数据库和CUHK02数据库测试后,该方法对人体识别率起到了显著的改善作用.     

Global consensus for discrete-time multi-agent systems with input saturation constraints

In this paper, we consider the global consensus problem for discrete-time multi-agent systems with input saturation constraints under fixed undirected topologies. We first give necessary conditions for achieving global consensus via a distributed protocol based on relative state measurements of the agent itself and its neighboring agents. We then focus on two special cases, where the agent model is either neutrally stable or a double integrator. For the neutrally stable case, any linear protocol of a particular form, which solves the consensus problem for the case without input saturation constraints, also solves the global consensus problem for the case with input saturation constraints. For the double integrator case, we show that a subset of linear protocols, which solve the consensus problem for the case without saturation constraints, also solve the global consensus problem for the case with input saturation constraints. The results are illustrated by numerical simulations.     

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.     

Models for Global Constraint Applications

In this paper we give an overview of some industrial applications built using global constraints. We look at three systems from different application domains and show the core models used to express their constraints. We also consider different search strategies that have been applied and discuss some of the application aspects.     

Embedding Relaxations in Global Constraints for Solving TSP and TSPTW

Constraint Programming (CP) has been successfully applied to several combinatorial optimization problems. One of its advantages is the availability of complex global constraints performing efficient propagation and interacting with each other through shared variables. However, CP techniques have shown their limitations in dealing with optimization problems since the link between the objective function and problem decision variables is often quite loose and does not produce an effective propagation. We propose to integrate optimization components in global constraints, aimed at optimally solving a relaxation corresponding to the constraint itself. The optimal solution of the relaxation provides pieces of information which can be exploited in order to perform pruning on the basis of cost-based reasoning. In fact, we exploit reduction rules based on lower bound and reduced costs calculation to remove those branches which cannot improve the best solution found so far. The interest of integrating efficient well-known Operations Research (OR) algorithms into CP is mainly due to the smooth interaction between CP domain reduction and information provided by the relaxation acting on variable domains which can be seen as a communication channel among different techniques. We have applied this technique to symmetric and asymmetric Traveling Salesman Problem (TSP) instances both because the TSP is an interesting problem arising in many real-life applications, and because pure CP techniques lead to disappointing results for this problem. We have tested the proposed optimization constraints using ILOG solver. Computational results on benchmarks available from literature, and comparison with related approaches are described in the paper. The proposed method on pure TSPs improves the performances of CP solvers, but is still far from the OR state of the art techniques for solving the problem. However, due to the flexibility of the CP framework, we could easily use the same technique on TSP with Time Windows, a time constrained variant of the TSP. For this type of problem, we achieve results that are comparable with state of the art OR results.     

状态和控制均受约束的不确定离散时间系统的鲁棒性

研究了参数摄动离散时间线性系统在状态和控制向量均受到约束时的鲁棒性问题。分别给出了开环系统和闭环系统鲁棒性判定的充要条件，均为端点结果。