基于细胞元模型拓扑约束求解

在模型制造领域,对于拓扑约束的求解是一个比较新的课题,以往的研究一直局限在拓扑优化方面。而且对其应用也仅限于模型的定义方面,在模型的声明与约束求解方面却没有得到应用。文章提出一种基于细胞元模型拓扑约束求解方法,通过该方法可以确定模型拓扑声明的关系,文章假设一个模型是由一个或多个细胞元组成的,并且能够用这些细胞元的组合来表示,对模型进行拓扑约束求解就是用来确定细胞模型中的每个细胞元是否是全约束的。要做到这点,文章将每个细胞元用一个布尔变量表示,把拓扑约束问题映射成为布尔可满足性问题。再对新的问题进行求解,从而解决了模型的拓扑约束求解问题。     

一种求解混合约束问题的快速完备算法

布尔与数值变量相混合的约束问题有着广泛盼应用，但是当约束中的数值变量间存在非线性关系时该问题求解起来十分困难．目前的许多求解方法都是不完备的，即这些方法不能完全肯定某些包含非线性数值表达式的约束是否能够成立．针对这种问题，提出了数值与区间分析相结合进行数值约束求解的方法．已经实现了一个基于此方法的原型工具．实验结果表明。该方法能够有效、快速、完备地求解非线性混合约束问题．     

基于布尔表达式约束的测试用例生成技术

布尔表达式约束在软件规格说明和程序中广泛存在，这些约束可作为软件系统的模型，成为测试用例生成依据。本文调研分析基于布尔表达式约束的测试用例生成方法，主要分为基于约束语法的测试和基于约束语义的测试。归纳总结基于约束语法测试的各种故障类型和测试策略，并比较各种测试策略的适用情形和故障检测能力，也对基于约束语义测试的各种约束获取和求解方法进行性能分析，并介绍了典型工具。最后对未来的研究发展进行展望。     

求解布尔与非线性数值约束相混合的约束问题

布尔与数值变量相混合的约束问题有着广泛的应用,但是当约束中的数值变量间存在非线性关系时该问题求解起来十分困难.目前的许多求解方法都是不完备的,即这些方法不能完全肯定某些包含非线性数值表达式的约束是否能够成立.针对这种问题,提出了将非线性数值约束转化为特殊形式的优化问题,采用全局优化算法对其进行求解的方法.已经实现了一个基于此方法的原型工具.实验结果表明,该方法能够有效地求解非线性混合约束问题,并且总能够得到该约束条件是否可满足的结果.     

基于约束规划的一类排序问题通用求解方法

多约束排序问题是生产调度中常遇到的问题,传统的优化模型及方法在适应约束改变等方面存在诸多不足。鉴于此,将多约束排序问题定义为约束满足问题,系统设计时将模型定义与求解算法分离,利用约束规划平台的基本约束构建特定领域的抽象约束库,形成可重构的多约束排序问题通用求解框架。应用时,根据问题需求不同可利用抽象约束库快速重构优化模型,针对重构的优化模型配置相应的求解算法即可实现问题求解。应用结果表明,提出的方法通用性强,可满足实际应用的要求。     

基于特征参数空间的交互约束自动求解方法*

提出了一种新的约束求解方法求解特征交互过程中两个特征形状在空间上发生重叠的约束。这个约束求解器在特征模型的参数空间进行取样的基础之上,利用蒙特卡罗技术来减少样本数据量。该方法不但可以产生一组正确的几何约束,而且提高了效率约束转换的效率。     

数值与符号的耦合约束求解模型

采用约束关系依赖图(CRDG)表达耦合约束之间的依赖关系,从而建立数值与符号耦合约束模型.提出耦合约束的求解算法:对CRDG进行最小独立子图分解,对存在耦合约束的子图用"孪生变量法"进行一阶解耦,对没有耦合约束的子图用传统方法进行独立求解,求解之后再对孪生变量进行等效性验算.该耦合约束模型及其求解算法拓展了传统约束理论,实现了教学求解和推理求解有机地结合.     

并行设计中基于特征约束的变更传播研究*

为了解决工程变更传播中难以搜索变更传播路径和难以计算变更程度的问题,本文以产品特征约束为基础分析并行设计中的变更传播过程。首先提出了约束结构树的概念和构建方法,用以表达产品特征约束的拓扑关系。然后对不同类型特征约束的变更传播进行了推理,给出了被影响的特征约束的求解算法。最后以某型号人孔为例说明了变更传播实现机制和方法,实验结果表明,文中方法在很大程度上改进了分析变更传播的准确性和有效性。     

基于图的参数化设计方法

参数化系统中约束的表达和约束的求解是两大关键性技术问题。作者提出的基于图的参数化方法是将约束分成拓扑约束和几何约束,并以图结构表达这两类约束,然后对约束网络图进行拓扑排序、分解,以确定求解序列和检测约束一致性,最后按照几何约束网中的约束关系进行“几何参数驱动”,以实现参数化。     

三维装配几何约束闭环系统的递归分解方法

由于现有几何约束分解方法无法分解三维装配几何约束闭环系统,故常采用数值迭代方法对其进行求解,但存在效率低、稳定性差等问题.为此,通过分析几何约束闭环图的拓扑结构和串联运动链的结构约束,提出基于串联运动链结构约束等价替换的三维几何约束闭环系统的递归分解方法.该方法通过不断地引入几何约束组合等价替换串联运动链的结构约束,从几何约束闭环系统中分离出可独立求解的子系统,实现几何约束闭环系统的递归分解.该方法可将此前许多必须整体迭代求解的三维几何约束闭环系统分解为一系列可解析求解的2个刚体之间的几何约束系统,明显提高了约束求解的效率和稳定性.最后用实例验证了方法的正确性和有效性.     

Solving topological constraints for declarative families of objects

Parametric and feature-based CAD models can be considered to represent families of similar objects. In current modelling systems, however, the semantics of such families are unclear and ambiguous.We present the Declarative Family of Objects Model (DFOM), which enables us to adequately specify and maintain family semantics. In this model, not only geometry, but also topology is specified declaratively, by means of constraints. A family of objects is modelled by a DFOM with multiple realizations. A member of the family is modelled by adding constraints, e.g. to set dimension variables, until a single realization remains. The declarative approach guarantees that the realization of a family member is also a realization of the family.The realization of a family member is found by solving first the geometric constraints, and then the topological constraints. From the geometric solution, a cellular model is constructed. Topological constraints indirectly specify which combinations of cellular model entities are allowed in the realization. The system of topological constraints is mapped to a Boolean constraint satisfaction problem. The realization is found by solving this problem using a SAT solver.     

Making constraint solvers more usable: overconstraint problem

The richness and expressive power of geometric constraints causes unintended ambiguities and inconsistencies during their solution or realization. For example, geometric constraint problems may turn out to be overconstrained requiring the user to delete one or more of the input constraints, and the solutions must then be dynamically updated. Without proper guidance by the constraint solver, the user must have profound insight into the mathematical nature of constraint systems and understand the internals of the solver algorithm. But a general user is most likely unfamiliar with those problems, so that the required interaction with the constraint solver may well be beyond the user's ability. In this paper, we present strategies and techniques to empower the user to deal effectively with the overconstraint problem while not requiring him or her to become an expert in the mathematics of constraint solving.We formulate this problem as a series of formal requirements that gel with other essentials of constraint solvers. We then give algorithmic solutions that are both general and efficient (running time typically linear in the number of relevant constraints).     

On Stability of Constrained Receding Horizon Control with Finite Terminal Weighting Matrix

In this paper, a new stabilizing receding horizon control, based on a finite input and state horizon cost with a finite terminal weighting matrix, is proposed for time-varying discrete linear systems with constraints. We propose matrix inequality conditions on the terminal weighting matrix under which closed-loop stability is guaranteed for both cases of unconstrained and constrained systems with input and state constraints. We show that such a terminal weighting matrix can be obtained by solving a linear matrix inequality (LMI). In the case of constrained time-invariant systems, an artificial invariant ellipsoid constraint is introduced in order to relax the conventional terminal equality constraint and to handle constraints. Using the invariant ellipsoid constraints, a feasibility condition of the optimization problem is presented and a region of attraction is characterized for constrained systems with the proposed receding horizon control.     

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.     

Fourier Elimination for Compiling Constraint Hierarchies

Linear equality and inequality constraints arise naturally in specifying many aspects of user interfaces, such as requiring that one window be to the left of another, requiring that a pane occupy the leftmost 1/3 of a window, or preferring that an object be contained within a rectangle if possible. For interactive use, we need to solve similar constraint satisfaction problems repeatedly for each screen refresh, with each successive problem differing from the previous one only in the position of an input device and the previous state of the system. We present an algorithm for solving such systems of constraints using projection. The solution is compiled into very efficient, constraint-free code, which is parameterized by the new inputs. Producing straight-line, constraint-free code of this sort is important in a number of applications: for example, to provide predictable performance in real-time systems, to allow companies to ship products without including a runtime constraint solver, to compile Java applets that can be downloaded and run remotely (again without having to include a runtime solver), or for applications where runtime efficiency is particularly important. Even for less time-critical user interface applications, the smooth performance of the resulting code is more pleasing than that of code produced using other current techniques.     

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 constructive approach to solving 3-D geometric constraint systems using dependence analysis

Solving geometric constraint systems in 3-D is much more complicated than that in 2-D because the number of variables is larger and some of the results valid in 2-D cannot be extended for 3-D. In this paper, we propose a new DOF-based graph constructive method to geometric constraint systems solving that can efficiently handle well-, over- and under-constrained systems based on the dependence analysis. The basic idea is that the solutions of some geometric elements depend on some others because of the constraints between them. If some geometric elements depend on each other, they must be solved together. In our approach, we first identify all structurally redundant constraints, then we add some constraints to well constrain the system. And we prove that the order of a constraint system after processing under-constrained cases is not more than that of the original system multiplied by 5. After that, we apply a recursive searching process to identify all the clusters, which is shown to be capable of getting the minimum order-reduction result of a well-constrained system. We also briefly describe the constraint evaluation phase and show the implementation results of our method.     

Corner block list representation and its application with boundary constraints

Floorplanning is a critical phase in physical design of VLSI circuits. The stochastic optimization method is widely used to handle this NP-hard problem. The key to the floorplanning algorithm based on stochastic optimization is to encode the floorplan structure properly. In this paper, corner block list (CBL)-a new efficient topological representation for non-slicing floorplan-is proposed with applications to VLSI floorplan. Given a corner block list, it takes only linear time to construct the floorplan. In floorplanning of typical VLSI design, some blocks are required to satisfy some constraints in the final packing. Boundary constraint is one kind of those constraints to pack some blocks along the pre-specified boundaries of the final chip so that the blocks are easier to be connected to certain I/O pads. We implement the boundary constraint algorithm for general floorplan by extending CBL. Our contribution is to find the necessary and sufficient characterization of the blocks along the boundary repre     

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.     

Abstracting soft constraints: Framework, properties, examples

Soft constraints are very flexible and expressive. However, they are also very complex to handle. For this reason, it may be reasonable in several cases to pass to an abstract version of a given soft constraint problem, and then to bring some useful information from the abstract problem to the concrete one. This will hopefully make the search for a solution, or for an optimal solution, of the concrete problem, faster.In this paper we propose an abstraction scheme for soft constraint problems and we study its main properties. We show that processing the abstracted version of a soft constraint problem can help us in finding good approximations of the optimal solutions, or also in obtaining information that can make the subsequent search for the best solution easier.We also show how the abstraction scheme can be used to devise new hybrid algorithms for solving soft constraint problems, and also to import constraint propagation algorithms from the abstract scenario to the concrete one. This may be useful when we don't have any (or any efficient) propagation algorithm in the concrete setting.