A new constructive approach to constraint-based geometric design

In the paper, a new constructive approach to solving geometric constraints in 2-D space is presented. Constraints are employed on lines and points only, but more sophisticated geometric elements like Bézier curves and ellipses can also be constrained by mapping them onto auxiliary lines and points. The algorithm is based on local propagation, but first, the problem is transformed into a form that guarantees success of employing this simple technique. The most important steps are substitution of complex constraints with sets of simpler ones and insertion of redundant constraints by solving triangles and determining sums and differences of adjacent angles. In this way, various well-constrained problems with a few exceptions are solved, over-constrained scenes and input data contradictory to some well-known mathematical theorems are detected, and the algorithm is proved successful in many under-constrained cases as well.     

A framework to model and manipulate constraints for over-constrained geographic applications

Geographic applications are often over-constrained because of the stakeholders’ multiple requirements and the various spatial, alphanumeric and temporal constraints to be satisfied. In most cases, solving over-constrained problems is based on the relaxation of some constraints according to values of preferences. This article proposes the modelling and the management of constraints in order to provide a framework to integrate stakeholders in the expression and the relaxation of their constraints. Three families of constraints are defined: static vs. dynamic, intra-entity vs. inter-entities and intra-instance vs. inter-instances. Constraints are modelled from two points of view: system with the complexity in time of the different involved operators and user with stakeholders’ preferences. The methodology of constraints relaxation is based on primitive, complex and derived operations. These operations allow a modification of the constraints in order to provide a relevant solution to a simulation. The developed system was applied to reduce the streaming/floods risks in the territory of Pays de Caux (Seine Maritime, France).     

复杂陈述式仿真模型的相容性分析

模型的相容性分析是复杂产品多领域建模面临的一个关键问题.研究了陈述式基于方程仿真模型的方程系统过约束或欠约束判定、检测与修正策略.首先,将方程系统表示为二部图,通过二部图分解判定模型的相容性,并分离出方程系统的过约束和欠约束部分.然后,通过检测、判定与缩减过程,自动判别出过约束或欠约束发生的大致范围,并给出修正方案.所提出的策略与算法能够显著地提高用户发现与排除过约束或欠约束问题的效率,已在多领域物理系统混合建模与仿真平台MWorks中实现.     

Multi-criteria decision making for assembly line balancing

Assembly line balancing often has significant impact on performance of manufacturing systems, and is usually a multiple-objective problem. Neither an algorithmic nor a procedural assembly line balancing methodology is usually effective in solving these problems. This article proposes a data envelopment analysis (DEA) approach to solve an assembly line balancing problem. A computer-aided assembly line balancing tool as Flexible Line Balancing software is used to generate a considerable number of solutions alternatives as well as to generate quantitative decision-making unit outputs. The quantitative performance measures were considered in this article. Then DEA was used to solve the multiple-objective assembly line balancing problem. An illustrative example shows the effectiveness of the proposed methodology.     

Solving Hierarchical Constraints over Finite Domains with Local Search

Many real world problems have requirements and constraints which conflict with each other. One approach for dealing with such over-constrained problems is with constraint hierarchies. In the constraint hierarchy framework, constraints are classified into ranks, and appropriate solutions are selected using a comparator which takes into account the constraints and their ranks. In this paper, we present a local search solution to solving hierarchical constraint problems over finite domains (HCPs). This is an extension of local search for over-constrained integer programs WSAT(OIP) to constraint hierarchies and general finite domain constraints. The motivation for this work arose from solving large airport gate allocation problems. We show how gate allocation problems can be formulated as HCPs using typical gate allocation constraints. Using the gate allocation benchmarks, we investigate how constraint heirarchy selection strategies and the problem formulation using two models: a 0–1 linear constraint hierarchy model and a nonlinear finite domain constraint hierarchy model.     

A constraint solver to define correctly dimensioned and overdimensioned parts

Creating mechanical parts through conceptual design implies the use of constraints. When developing conceptual design-based CAD programs, two independent modules must be created: on the one hand, the sketcher module, which must define the model's geometrical constraints and interpret the user's intention through a system of rules. On the other, the calculation module which must resolve the final geometry and eventually dimension the mechanical part. This paper presents a new approach to the constraint-based solvers. The proposed approach establishes the complete two-dimensional geometry and constraints of a sketch and relates it with the complete dimensioning of the sketch. The developed methodology gives as result a complete and consistent dimensioning of the sketch following the rules established by a standard like ISO, determining also if the system is over-constrained and detecting the redundant dimensions. The methodology establishes the most suitable dimensioning but, it is also possible to obtain other alternatives of full sets of dimensions.First, the geometric constraints considered are described, and the use of each one justified, together with the numerical methods used to resolve the set of non-linear constraints obtained. A procedure has also been developed for choosing the set of independent constraints of the system, by introducing the priority factor concept, which lets the overriding constraints in the system be decided, and then the algorithms developed for automatically assigning the constraints are presented. Also described are the criteria followed that lead to an automatic generation of dimensions, as well as to equivalent and alternative dimensioning. Finally, a series of examples are presented to show the possibilities of the developed methodology.     

Restarted Iterated Pareto Greedy algorithm for multi-objective flowshop scheduling problems

Multi-objective optimisation problems have seen a large impulse in the last decades. Many new techniques for solving distinct variants of multi-objective problems have been proposed. Production scheduling, as with other operations management fields, is no different. The flowshop problem is among the most widely studied scheduling settings. Recently, the Iterated Greedy methodology for solving the single-objective version of the flowshop problem has produced state-of-the-art results. This paper proposes a new algorithm based on Iterated Greedy technique for solving the multi-objective permutation flowshop problem. This algorithm is characterised by an effective initialisation of the population, management of the Pareto front, and a specially tailored local search, among other things. The proposed multi-objective Iterated Greedy method is shown to outperform other recent approaches in comprehensive computational and statistical tests that comprise a large number of instances with objectives involving makespan, tardiness and flowtime. Lastly, we use a novel graphical tool to compare the performances of stochastic Pareto fronts based on Empirical Attainment Functions.     

VLSI Design Methodology for Edge-Preserving Image Reconstruction

This paper proposes a design methodology for the semi-automatic derivation of hardware dedicated to a generic class of image analysis reconstruction problems. The study will focus on the implications on the hardware of the associated estimation algorithm and of the built-in underlying minimization. A specific minimization strategy has been designed with a view to improving the efficiency of specialized hardware (in terms of clock cycle and surface area). Convergence proofs are given in the Appendix. This new nonlinear minimization has proved to be almost four times faster than the classical method used in such a context. The VLSI derivation tool presented here is based on a high-level specification of the updating rules defining the problem at hand. The complete derivation is illustrated on an edge-preserving optical flow estimator and on image restoration.     

Automatic parameter tuning for Evolutionary Algorithms using a Bayesian Case-Based Reasoning system

The widespread use and applicability of Evolutionary Algorithms is due in part to the ability to adapt them to a particular problem-solving context by tuning their parameters. This is one of the problems that a user faces when applying an Evolutionary Algorithm to solve a given problem. Before running the algorithm, the user typically has to specify values for a number of parameters, such as population size, selection rate, and probability operators.This paper empirically assesses the performance of an automatic parameter tuning system in order to avoid the problems of time requirements and the interaction of parameters. The system, based on Bayesian Networks and Case-Based Reasoning methodology, estimates the best parameter setting for maximizing the performance of Evolutionary Algorithms. The algorithms are applied to solve a basic problem in constraint-based, geometric parametric modeling, as an instance of general constraint-satisfaction problems.The experimental results demonstrate the validity of the proposed system and its potential effectiveness for configuring algorithms.     

Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems

This paper describes new ways to tackle several important problems encountered in geometric constraint solving, in the context of CAD, and which are linked to the handling of under- and over-constrained systems. It presents a powerful decomposition algorithm of such systems.Our methods are based on the witness principle whose theoretical background is recalled in a first step. A method to generate a witness is then explained. We show that having a witness can be used to incrementally detect over-constrainedness and thus to compute a well-constrained boundary system. An algorithm is introduced to check if anchoring a given subset of the coordinates brings the number of solutions to a finite number.An algorithm to efficiently identify all maximal well-constrained parts of a geometric constraint system is described. This allows us to design a powerful algorithm of decomposition, called W-decomposition, which is able to identify all well-constrained subsystems: it manages to decompose systems which were not decomposable by classic combinatorial methods.     

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

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

Consistency and error analysis of Prior-Knowledge-Based Kernel Regression

Incorporating prior knowledge (PK) into learning methods is an effective means to improve learning performance. The consistency and error theories of PK-based methods, which are of great theoretical importance, are still far from well established. Concentrating on the PK-based kernel regression, this paper proposes a methodology of analyzing the consistency and error. This methodology converts the specific methods firstly to a unified optimization problem and then to a unified solution expression, and a general consistency and error analysis tool is proposed and applied. A few examples are given to illustrate the analysis procedure.     

Tool path planning for compound surfaces in spray forming processes

Spray forming is an emerging manufacturing process. The automated tool planning for this process is a nontrivial problem, especially for geometry-complicated parts consisting of multiple freeform surfaces. Existing tool planning approaches are not able to deal with this kind of compound surface. This paper proposes a tool-path planning approach which optimizes the tool motion performance and the thickness uniformity. There are two steps in this approach. The first step partitions the part surface into flat patches based on the topology and normal directions. The second step determines the tool movement patterns and the sweeping directions for each flat patch. Based on the above two steps, optimal tool paths can be calculated. Experimental tests are carried out on automotive body parts and the results validate the proposed approach. Note to Practitioners-This paper was motivated by the problem of automatically planning tool paths for spray forming using Programmable Powdered Preforming Process (P4) technology. However, the proposed approach can be applied to other surface manufacturing applications such as spray painting, spray cleaning, rapid tooling, etc. Existing tool planning approaches are not able to handle complicated, multi-patch surfaces. This paper proposes a methodology to partition complicated surfaces into easy-to-handle patches and generate tool paths with optimized thickness uniformity and tool motion performance. We tested the approach using simulation on sample automotive body parts and proved its feasibility. However, this approach requires that the parts to be sprayed belong to the sheet-metal type so that the part geometry can be analyzed on a plane. In our future research, we will run physical tests on actual parts and investigate the deposition effects on the thickness uniformity.     

Reliability-based topology optimization of continuum structures subject to local stress constraints

Topology optimization of continuum structures is a challenging problem to solve, when stress constraints are considered for every finite element in the mesh. Difficulties are compounding in the reliability-based formulation, since a probabilistic problem needs to be solved for each stress constraint. This paper proposes a methodology to solve reliability-based topology optimization problems of continuum domains with stress constraints and uncertainties in magnitude of applied loads considering the whole set of local stress constrains, without using aggregation techniques. Probabilistic constraints are handled via a first-order approach, where the principle of superposition is used to alleviate the computational burden associated with inner optimization problems. Augmented Lagrangian method is used to solve the outer problem, where all stress constraints are included in the augmented Lagrangian function; hence sensitivity analysis may be performed only for the augmented Lagrangian function, instead of for each stress constraint. Two example problems are addressed, for which crisp black and white topologies are obtained. The proposed methodology is shown to be accurate by checking reliability indices of final topologies with Monte Carlo Simulation.     

Multi-objective optimization and bio-inspired methods applied to machinability of stainless steel

Nowadays, due to the growing needs of market, the simultaneous optimization of various responses is configured as a necessary strategy in real process. Machinability of stainless steel has always been considered a difficult task and any movement toward optimization of this process are really worthy. Traditionally, the treatment of this problem is done through the application of the desirability function that consists in transforming the original multi-response problem in a similar with one objective. In spite of various applications involving this methodology, the quality of the solution obtained is dependent on the choice of the inferior and superior limits and on goals for each one of the responses. To overcome this disadvantage, the present work proposes a methodology to solve the original multi-objective problem by using the Bio-inspired Optimization Methods (BiOM). The strategy proposed consists in the extension of the BiOM to problems with multiple objectives, through the incorporation of two operators into the original algorithm: (i) the rank ordering, and (ii) the crowding distance. The proposed algorithm is applied to the machinability of stainless steel AISI (ABNT) 420 using a model that considers the tool life and cutting forces responses in terms of cutting speed, feed per tooth and axial depth of cut, in end milling process. The effects of these variables in the responses were investigated crossing information contained in response surfaces of material removal rate and cutting forces. The results obtained showed that the methodology used represents an interesting approach to the treatment of the optimization problem formulated.     

Development and analysis of cooperative model-based metaheuristics

The paper proposes a methodology to construct cooperative metaheuristic methods for solving combinatorial optimization problems using model-based algorithms. Its distinctive feature is that the original problem is solved by a search (optimization) in the space of models. Such a search is performed on the basis of models formed by basic algorithms. Cooperative metaheuristics underlain by ant colony optimization and MH-method algorithms are developed, and the efficiency of the proposed methodology is evaluated by means of a computational experiment.     

DOC-BRelax: A new multi-agent system to solve Distributed Constraint Optimization Problems

Many problems in multi-agent systems can be described as Distributed Constraint Satisfaction Problems (DCSPs), where the goal is to find a set of assignments to variables that satisfies all constraints among agents. However, when real-life application problems are formalized as DCSPs, they are often over-constrained and have no solution that satisfies all constraints. Moreover, the globalization of the economy and democratization of the Internet, boosted by the huge growth in information and communication technologies, have largely contributed to the expansion of numerous distributed architectures. Thus this paper provides a new distributed management and decision support system suitable to these interdependencies and these complex environments. We present a Distributed Optimization under Constraints Basic Relax (DOC-BRelax) as a new framework for dealing with over-constrained situations. We also present a version of this framework called DOC-MaxRelax and a new algorithm for solving Distributed Maximal Constraint Satisfaction Problems (DMCSPs).