A new Algorithm for the Solution of under Constraint Graph in Sketch Drawing

A new algorithm for the solution of under constraint graph in sketch drawing is put forward. The directed process of constraint graph is completed by picking concealed constraints of adjacent entities in sketch of few or no dimensions. In this paper, the priority of concealed constraint is given by the different constraint types and constructing orders, and some more priority concealed constraints are forced into obvious ones by the need number of constraint for every node in constraint solution process.     

几何约束有向图的规划分解研究

在基于有向图表达的几何约束系统中,几何约束的匹配方向、分布状态以及有向图中强连通分量的规模直接影响到整个约束系统的求解;如何对几何约束系统进行合理规划,得到正确有效的求解序列,是目前约束分解研究的重要内容。该文提出了一个规划分解算法,它针对欠约束几何系统的特点,能够优化约束的初始匹配方向,对于约束匹配过程中生成的强连通子图,通过调整约束匹配方向,自适应地改善约束分布,从而减小强连通子图的规模,以求得到几何约束系统正确而高效的求解序列。同时,基于规划分解算法,完成了约束的奇异性分析,提供了面向分解的奇异性分析算法。     

Modelling and managing disjunctions in scheduling problems

In this paper is presented a method for modelling and managing various constraints encountered in task scheduling problems. The approach aims at characterizing feasible schedules through the analysis of the set of constraints and their interaction, regardless of any optimization criteria. This analysis is achieved by a constraint propagation process on a constraint graph and produces both restricted domains for the decision variables and an updated formulation of the initial constraints. The graphs usually used to model temporal constraints seem to be limited because they only allow the representation of strict precedence relations between two tasks. In order to model a larger variety of temporal constraints, particularly any constraint that connects two events (start- or finish- time of a task), a model called a time-bound-on-node (TBON) graph is proposed in which each task is featured by two nodes. Then it becomes possible to handle constraints on task durations, due for example to flexibilities in resource utilization. This kind of graph is not new and has already been investigated in related works on project planning and Constraint Satisfaction Problems. But its processing and interpretation deserved to he developed, particularly for the present purpose, which is the search for the necessary conditions of feasibility. With respect to conjunctive temporal constraints, the analysis is achieved with a polynomial algorithm based on the longest path search on a conjunctive TBON graph, yielding the necessary and sufficient conditions of feasibility. Taking account of resource constraints leads to defining disjunctive constraints. To this end, disjunctive sets of arcs are introduced, making the TBON graph nonconjunctive. In this case, a complete characterization of feasibility cannot reasonably be faced, due to the combinatorial feature. Nevertheless, a polynomial algorithm that applies reduction and deletion rules on the nonconjunctive part of the graph is proposed to restart new propagations on the conjunctive part until all deductions have been made.     

一种欠约束草图求解方法的研究

基于约束的参数化描述及求解是计算机辅助设计研究的一个热点，欠约束图的求解是参数化设计的基本问题，为了提高欠约束草图求解的参数化设计效率，提出了一种基于隐式约束优先级的欠约束草图求解方法，并首先给出了欠约束图求解的一般方法以及欠约束图的基本特征，提出了利用隐式约束去匹配缺少的显式约束；然后将隐式约束按照一定的规则分成不同的优先级，再利用优先级高的隐式约束去匹配变动约束图中的欠约束，直到完成约束图的有向化；最后，探讨了无尺寸约束图有向化过程中的基本特点，并给出了无尺寸约束图的求解算法和应用实例。实例应用结果表明，效果较好。     

Genetic algorithm for the personnel assignment problem with multiple objectives

The assignment problem is a well-known graph optimization problem defined on weighted-bipartite graphs. The objective of the standard assignment problem is to maximize the summation of the weights of the matched edges of the bipartite graph. In the standard assignment problem, any node in one partition can be matched with any node in the other partition without any restriction. In this paper, variations of the standard assignment problem are defined with matching constraints by introducing structures in the partitions of the bipartite graph, and by defining constraints on these structures. According to the first constraint, the matching between the two partitions should respect the hierarchical-ordering constraints defined by forest and level graph structures produced by using the nodes of the two partitions respectively. In order to define the second constraint, the nodes of the partitions of the bipartite graph are distributed into mutually exclusive sets. The set-restriction constraint enforces the rule that in one of the partitions all the elements of each set should be matched with the elements of a set in the other partition. Even with one of these constraints the assignment problem becomes an NP-hard problem. Therefore, the extended assignment problem with both the hierarchical-ordering and set-restriction constraints becomes an NP-hard multi-objective optimization problem with three conflicting objectives; namely, minimizing the numbers of hierarchical-ordering and set-restriction violations, and maximizing the summation of the weights of the edges of the matching. Genetic algorithms are proven to be very successful for NP-hard multi-objective optimization problems. In this paper, we also propose genetic algorithm solutions for different versions of the assignment problem with multiple objectives based on hierarchical and set constraints, and we empirically show the performance of these solutions.     

基于指向更新的优先权指针分析算法

指针分析是数据流分析中的关键性技术,其分析结果是编译优化和程序变换的基础。在基于包含的指针分析算法研究的基础上,对 Narse 优先权约束评估算法中存在的冗余约束评估和优先权评估模型计算开销较大的问题进行分析,以指针的指向集更新信息确定约束评估的候选集,提出了基于指向更新的约束评估算法。采用约束语句间的解,引用依赖和标量依赖构建约束依赖图,通过依赖关系确定约束评估的优先权,提出了基于约束依赖图的优先权算法,简化了既有算法中复杂的优先权评估模型,进一步给出了优化后算法的整体框架。在基准测试集 SPEC 2000/SPEC 2006上进行实验,其结果表明,该算法与Narse优先权算法相比,在时间开销和存储开销上都有明显的性能提升。     

Revisiting decomposition analysis of geometric constraint graphs

Geometric problems defined by constraints can be represented by geometric constraint graphs whose nodes are geometric elements and whose arcs represent geometric constraints. Reduction and decomposition are techniques commonly used to analyze geometric constraint graphs in geometric constraint solving.In this paper we first introduce the concept of deficit of a constraint graph. Then we give a new formalization of the decomposition algorithm due to Owen. This new formalization is based on preserving the deficit rather than on computing triconnected components of the graph and is simpler. Finally we apply tree decompositions to prove that the class of problems solved by the formalizations studied here and other formalizations reported in the literature is the same.     

基于有向图的二维约束求解算法研究

针对过约束、几何完全定义状态判定和约束求解效率等问题,提出了基于约束图,利用自由度理论和约束冲突机制,通过反向约束方向平衡约束,进而通过排序进行约束求解的算法。算法采用约束图记录约束和几何的关系;通过约束平衡的方法进行过约束和几何完全定义的判定;采用排序求解方法,将庞大计算问题转化为一组相对简单的计算问题。算法已得到初步应用,对过约束和几何完全定义状态的判定有明显的效果,而且提高了约束求解效率。     

Optimal Graph Constraint Reduction for Symbolic Layout Compaction

The compaction problem in VLSI layout can be formulated as a linear program. To reduce the execution time and memory usage in compaction, it is important to reduce the size of the linear program. Since most constraints in compaction are derived directly or indirectly from physical separation and electrical connectivity requirements which can be expressed in the form of graph constraints, we study the graph constraint reduction problem. That is the problem of producing, for a given system of graph constraints, an equivalent system with the fewest graph constraints. After observing that the problem as previously formulated is NP-hard and overrestrictive in that the maximum possible reduction is not always attainable, we propose a new formulation in which the maximum possible reduction is guaranteed. We further present a polynomial-time algorithm for the new formulation. Received September 13, 1994; revised December 4, 1995.     

A constrained approach to multifont Chinese character recognition

The constraint graph is introduced as a general character representation framework for recognizing multifont, multiple-size Chinese characters. Each character class is described by a constraint graph model. Sampling points on a character skeleton are taken as nodes in the graph. Connection constraints and position constraints are taken as arcs in the graph. For patterns of the same character class, the model captures both the topological invariance and the geometrical invariance in a general and uniform way. Character recognition is then formulated as a constraint-based optimization problem. A cooperative relaxation matching algorithm that solves this optimization problem is developed. A practical optical character recognition (OCR) system that is able to recognize multifont, multiple-size Chinese characters with a satisfactory performance was implemented     

半监督聚类中基于密度的约束扩展方法

现有的半监督聚类方法较少利用数据集空间结构信息,限制了聚类算法的性能。该文提出一种基于密度的约束扩展方法(DCE),将数据集以图的形式表达,定义一种基于密度的图形相似度。根据样本点间的距离和相似度关系,对已知约束集进行扩展,扩展后的约束集可用于各种半监督聚类算法。以约束完全连接聚类和成对约束K均值方法为例,说明了约束扩展方法的应用。实验表明,DCE能够有效地提升半监督聚类算法的性能。     

Predicting phase transitions of binary constraint satisfaction problems with constraint graph information

Constraint satisfaction is at the core of many applications, such as scheduling. The study of phase transition has benefited algorithm selection and algorithm development in constraint satisfaction. Recent research provides evidence that constraint graph topology affects where phase transitions occur in constraint satisfaction problems. In this article, a new phase transition predictor which takes constraint graph information into consideration is proposed. The new predictor allows variation in the tightness of individual constraints and node degree variation in constraint graph. Experiments were conducted to study the usefulness of the new predictor on random binary constraint satisfaction problems. Results show that the new predictor is able to produce predictions as good as the state-of-the-art predictor in general, but do considerably better in sparsely constrained problems, particularly when the node degree variation in their constraint graphs is high.     

基于遗传算法的平面图平面正交直线画图算法

提出了一种基于遗传算法的新的平面图平面正交直线画图算法,算法将平面图画图问题转化为约束优化问题,根据画图问题选定的美观准则构造约束函数,用遗传算法求解目标函数的最优解的近似值,从而得到平面图的平面正交直线画法。新算法的优点是方法简单,易于实现,画出的图形美观,算法稳定性好。实验结果表明,画图算法的最终结果不依赖于图的初始状态。     

Boosting Search with Variable Elimination in Constraint Optimization and Constraint Satisfaction Problems

There are two main solving schemas for constraint satisfaction and optimization problems: i) search, whose basic step is branching over the values of a variables, and ii) dynamic programming, whose basic step is variable elimination. Variable elimination is time and space exponential in a graph parameter called induced width, which renders the approach infeasible for many problem classes. However, by restricting variable elimination so that only low arity constraints are processed and recorded, it can be effectively combined with search, because the elimination of variables may reduce drastically the search tree size.In this paper we introduce BE-BB(k), a hybrid general algorithm that combines search and variable elimination. The parameter k controls the tradeoff between the two strategies. The algorithm is space exponential in k. Regarding time, we show that its complexity is bounded by k and a structural parameter from the constraint graph. We provide experimental evidence that the hybrid algorithm can outperform state-of-the-art algorithms in constraint satisfaction, Max-CSP and Weighted CSP. Especially in optimization tasks, the advantage of our approach over plain search can be overwhelming.     

一个改进的基本方向约束一致性的判定算法

基本方向约束的一致性判定是定性空间推理中的基本问题之一。本文采用将基本方向约束集转化成有向图的方法,给出了一致性判定的相关结论,并据此在Skiadopoulos算法基础上提出了一种改进算法。新算法不但能判定出所有导致不一致的约束子集,而且还提高了执行效率。     

Analytic performance comparison of hypercubes and star graphs with implementation constraints

Many theoretical-based comparison studies, relying on graph structural and algorithmic properties, have been conducted for the hypercube and the star graph. None of these studies, however, have considered real working conditions and implementation limits. We have compared the performance of the star and hypercube networks for different message lengths and number of virtual channels, and considered two implementation constraints, namely the constant bisection bandwidth and constant node pin-out. We use two accurate analytical models, already proposed for the star graph and hypercube, and implement the parameter changes imposed by technological implementation constraints. When no constraint is used, the comparison results reveal that the hypercube has a better performance compared to the equivalent star graph. The hypercube with more channels compared to its equivalent star graph saturates later showing that it can bear heavier traffic loads. However, when implementation constraints are considered, the star graph exhibits a superior performance over its equivalent hypercube in most cases.     

两种空间约束求解算法

进行了3个方面的研究：(1)对由3点3面组成的空间约束系统进行了几何分析和推导，并且利用数值解验证了几何分析和推导的正确性，从而进一步完善了Hoffmann提出的基于图构造方法的约束求解方法；(2)将遗传模拟退火算法结合于空间约束求解中，有效地克服了基于图构造方法的可扩展性差的缺陷，并可以解决过约束和欠约束的情况；(3)应用遗传模拟退火算法对3点3面约束系统进行求解，分析比较了基于图构造方法和基于遗传模拟退火算法两种约束求解算法．     

Dynamic constraint satisfaction problems over models

In early phases of designing complex systems, models are not sufficiently detailed to serve as an input for automated synthesis tools. Instead, a design space is constituted by multiple models representing different valid design candidates. Design space exploration aims at searching through these candidates defined in the design space to find solutions that satisfy the structural and numeric design constraints and provide a balanced choice with respect to various quality metrics. Design space exploration in an model-driven engineering (MDE) context is frequently tackled as specific sort of constraint satisfaction problem (CSP). In CSP, declarative constraints capture restrictions over variables with finite domains where both the number of variables and their domains are required to be a priori finite. However, the existing formulation of constraint satisfaction problems can be too restrictive to capture design space exploration in many MDE applications with complex structural constraints expressed over the underlying models. In this paper, we interpret flexible and dynamic constraint satisfaction problems directly in the context of models. These extensions allow the relaxation of constraints during a solving process and address problems that are subject to change and require incremental re-evaluation. Furthermore, we present our prototype constraint solver for the domain of graph models built upon the Viatra2 model transformation framework and provide an evaluation of its performance with comparison to related tools.     

大规模图上具有约束的多起点路径规划算法

路径规划查询是图数据上的一个基本问题,在众多的领域都有重要的应用价值。通常在实际问题中查询的路径是具有约束的,例如在外卖配送和共享出行问题中路径具有节点约束,其路径需要满足节点之间的先后关系约束。目前对于具有节点约束的路径查询问题,大多数的工作都在研究单起点的节点约束路径查询,但很难拓展到多起点节点约束问题中。因为具有节点约束的多起点路径查询问题是NP-hard的,所以该问题的大多数已有方法是使用贪心增量处理,但对于处理静态规则集拓展性不足。因此,提出了基于子路径的启发式算法和基于约束集拓展的精确算法,并在真实数据集上验证了算法的有效性。实验结果表明,启发式算法能够给出问题的精确解,而启发式算法能快速给出较好的近似解。     

基于最大权团的曲面粗匹配算法

提出一种将曲面匹配问题转化为图论中的最大权团搜索问题、将最优的点对应关系用最大权团表示的曲面粗匹配算法,该算法分为点匹配、点对应图构造和最大权团生成等3个阶段.点匹配使用高曲率点和均匀采样点作为候选点,通过自旋图进行匹配计算,构造初始点对应集合;点对应图构造使用距离约束、法矢约束和唯一性约束构造图的边,并使用自旋图相关系数为顶点赋权值;最大权团生成使用基于分支限界的团搜索算法,从对应点图中提取出代表最优对应的最大权团.实验结果表明,文中算法稳定、有效、可扩展,能够进行部分曲面匹配,并且适用于欠特征曲面.