Propagation algorithms for lexicographic ordering constraints

Finite-domain constraint programming has been used with great success to tackle a wide variety of combinatorial problems in industry and academia. To apply finite-domain constraint programming to a problem, it is modelled by a set of constraints on a set of decision variables. A common modelling pattern is the use of matrices of decision variables. The rows and/or columns of these matrices are often symmetric, leading to redundancy in a systematic search for solutions. An effective method of breaking this symmetry is to constrain the assignments of the affected rows and columns to be ordered lexicographically. This paper develops an incremental propagation algorithm, GACLexLeq, that establishes generalised arc consistency on this constraint in O(n) operations, where n is the length of the vectors. Furthermore, this paper shows that decomposing GACLexLeq into primitive constraints available in current finite-domain constraint toolkits reduces the strength or increases the cost of constraint propagation. Also presented are extensions and modifications to the algorithm to handle strict lexicographic ordering, detection of entailment, and vectors of unequal length. Experimental results on a number of domains demonstrate the value of GACLexLeq.     

Minimal parallelism for associative computations under time constraints

The parallel evaluation ofA _N =a ₁ °a ₂ °...°a _N , where ° is binary associative, is studied. Under an idealized model of parallel computation, the minimal number of parallel processors required to computeA _N in at mostt steps is determined for ?log₂ N?≤t≤N?1. This indicates that it is not always desirable to reduce the running time to an absolute minimum, and provides a lower bound on the processing power required for time-constrained evaluation of general arithmetic expressions. Results for two-input processors, are generalized tob-input processors, and then to non-homogeneous collections of processors. The latter does not have a closed-form solution, so approximations are analyzed.     

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.     

Short-Time Scaling of Variable Orderingof OBDDs

A short-time scaling criterion of variable ordering of OBDDs is proposed.By this criterion it is easy and fast to determine which one is better when several variable orders are given,especially when they differ 10% or more in resulted BDD size from each other.An adaptive variable order selection method,based on the short-time scaling criterion,is also presented.The experimental results show that this method is efficient and it makes the heuristic variable ordering methods more practical.     

对象族拓扑约束求解的研究

针对当前对象族模型在求解拓扑约束时存在的缺陷,提出一种求解拓扑约束的新方法,这种方法在求解拓扑约束时,把拓扑约束映射为布尔约束满足问题,通过用SAT求解器求解布尔约束来求解拓扑约束。实践证明,该方法不仅直接关联与拓扑约束指定的特征的语义,而且当模型中存在大量相交的特征时也是可行的,提高了拓扑约束求解的效率。     

On mechanical control systems with nonholonomic constraints and symmetries

This paper presents a computationally efficient method for deriving coordinate representations for the equations of motion and the affine connection describing a class of Lagrangian systems. We consider mechanical systems endowed with symmetries and subject to nonholonomic constraints and external forces. The method is demonstrated on two robotic locomotion mechanisms known as the snakeboard and the roller racer. The resulting coordinate representations are compact and lead to straightforward proofs of various controllability results.     

Algorithms for point-wise state variable constraints in structural optimization

This paper presents algorithms to treat the point-wise state variable constraints in finite dimensional and distributed parameter structural optimization problems. The idea is to impose such constraints at all local maximum points, or over a small region around the maximum points. Therefore, methods for design sensitivity analysis to handle the constraints at some particular point for the distributed parameter problem are presented. The direct differentiation and adjoint variable methods are employed to derive the design sensitivity expressions. For the finite dimensional problem the new idea is easily carried out in optimization process. Simply supported and clamped beams are optimized using the new approach. These are modeled with nonuniform beam elements. Comparisons of finite dimensional and distributed parameter problems are also made.     

变约束高效预测控制

为改善离线鲁棒预测控制算法的最优性引入了变终端约束集的思想,即在原离线方法基础上通过在线优化方法获得构建当前反馈矩阵的凸组合系数,然后再产生当前控制量.与原方法相比增加了在线求解的自由度,改善了系统的最优性.在此基础上,又提出了变约束预测控制(VC-MPC)算法,根据状态所处的不同稳定椭圆域确定其对应的控制约束,在取得...     

On the influence of the variable ordering for algorithmic learning using OBDDs

OBDDs with a fixed variable ordering are used successfully as data structure in experiments with learning heuristics based on examples. In this paper, it is shown that, for some functions, it is necessary to develop an algorithm to learn also a good OBDD variable ordering. There are functions with the following properties. They have OBDDs of linear size for optimal variable orderings. But for all but a small fraction of all variable orderings one needs large size to represent a list of randomly chosen examples. These properties are shown for simple functions like the multiplexer and the inner product.     

同一变量排序下的多OBDD合并算法

有序决策图（OBDD）是一种用于表示布尔表达式的数据结构,并在许多领域得到了广泛应用。在分布式或者动态环境下,利用已知布尔表达式的OBDD构造目标布尔表达式的OBDD是一个决定实际问题解决效率的关键问题。基于Shannon分解原理提出了一个同一变量排序下的OBDD合并算法。该算法首先建立目标布尔表达式的表存储模型,然后按照变量排序的逆序,依次处理各个变量,并且合并取值相同的行,直到所有变量处理完毕。     

A variable reduction strategy for evolutionary algorithms handling equality constraints

Efficient constraint handling techniques are of great significance when Evolutionary Algorithms (EAs) are applied to constrained optimization problems (COPs). Generally, when use EAs to deal with COPs, equality constraints are much harder to satisfy, compared with inequality constraints. In this study, we propose a strategy named equality constraint and variable reduction strategy (ECVRS) to reduce equality constraints as well as variables of COPs. Since equality constraints are always expressed by equations, ECVRS makes use of the variable relationships implied in such equality constraint equations. The essence of ECVRS is it makes some variables of a COP considered be represented and calculated by some other variables, thereby shrinking the search space and leading to efficiency improvement for EAs. Meanwhile, ECVRS eliminates the involved equality constraints that providing variable relationships, thus improves the feasibility of obtained solutions. ECVRS is tested on many benchmark problems. Computational results and comparative studies verify the effectiveness of the proposed ECVRS.     

Coordinated ordering decisions for products with short lifecycle and variable selling price

The supplier–buyer coordination is an important policy in the supply chain management. The buyer in the two-echelon inventory system with regular selling season has to face the uncertainty of customer demand, supplier’s delivery time and variable price change. At the same time, the supplier has to consider the inventory holding and delay cost. The objective of this study is to develop an integrated supply chain strategy for products with short lifecycle and variable selling price to entice cooperation. The strategy must provide a win–win situation for both the supplier and the buyer. A numerical case example, sensitivity analysis and compensation mechanism are given to illustrate the model.     

An extension of singular value analysis for assessing manipulated variable constraints

A new approach called feasible output radius analysis for linear or linearised models is introduced to address the problem of scaling dependency. This problem arises when assessing the effect of manipulated variable constraints (MVCs) on the closed-loop performance of chemical processes prior to carrying out control designs. The new indicators, and can be used to rank alternative control schemes on the basis that the larger and , the better the closed-loop performance in the presence of control constraints. These indicators are determined from extending the concept of the ‘feasible output amplitude region’ and are independent of the input scaling chosen. Theoretical analysis shows that this method is an extension of the more traditional singular value analysis approach and is more flexible in dealing with various kinds of manipulated variable constraints. A case study, i.e. a two-CSTR process, is investigated using the new method. Via the case study, some superior characteristics of the new technique are demonstrated, such as ease of calculation, and flexibility in coping with different kinds of constraints.     

Optimal carbon reduction level and ordering quantity under financial constraints

Carbon tax policy is widely adopted by many countries to curb carbon emissions. In the context of carbon tax policy, firms have more incentive to improve carbon reduction levels by reducing their carbon tax costs. However, firms need to bear carbon reduction costs that may cause shortage of capital. Thus, firms may face problems of financial constraints, which may demotivate firms to produce greener products. To address the decision‐making challenges of firms in the contexts of carbon tax policy and financial constraints, we consider a supply chain with a manufacturer who produces green products and a retailer who sells these products. Our study develops five models to investigate the two firms’ optimal wholesale price, carbon reduction level and ordering quantity, according to the manufacturer and retailer with or without financial constraints. Our goal in this study is to explore how carbon tax policy and banks’ interest rates affect the profits of the two firms, supply chain and consumer surplus. Certain managerial insights are obtained as follows. We demonstrate that carbon tax policy and banks’ interest rates demotivate the manufacturer to produce greener products and demotivate the retailer to order more products. If the interest rate to the manufacturer (retailer) is relatively low, then the manufacturer with financial constraint benefits (harms) the consumers compared with the retailer with financial constraint. Importantly, our analysis suggests that carbon tax policy harms the firms but benefits consumers, and the government in some conditions should reduce unit carbon tax.     

基于灾变遗传算法的二叉判定图最小化算法

二叉判定图广泛应用于形式验证,但相关算法存在节点规模过大的问题。提出了一种基于灾变遗传算法的二叉判定图最小化算法,它能在不扩大种群规模的情况下增加个体多样性,改善遗传算法局部收敛的问题。试验结果表明该算法的全局特性显著优于传统遗传算法,能够进一步减小节点规模,改善程度最高可达25%。而且,由于使用何种进化策略并不影响灾变的发生,因此,算法可扩展性好,极易与其他改进策略结合起来,在原有特性的基础上引入全局优势,以进一步减小节点规模。     

Solving connected row convex constraints by variable elimination

We propose an algorithm for the class of connected row convex constraints. In this algorithm, we introduce a novel variable elimination method to solve the constraints. This method is simple and able to make use of the sparsity of the problem instances. One of its key operations is the composition of two constraints. We have identified several nice properties of connected row convex constraints. Those properties enable the development of a fast composition algorithm whose complexity is linear to the size of the variable domains. Compared with the existing work including randomized algorithms, the new algorithm has favorable worst case time and working space complexity. Experimental results also show a significant performance margin over the existing consistency based algorithms.     

Parameter constraints in generalized linear latent variable models

Parameter constraints in generalized linear latent variable models are discussed. Both linear equality and inequality constraints are considered. Maximum likelihood estimators for the parameters of the constrained model and corrected standard errors are derived. A significant reduction in the dimension of the optimization problem is achieved with the proposed methodology for fitting models subject to linear equality constraints.     

几个非线性偏微分方程的非古典对称及相似解

研究了一些非线性偏微分方程的非古典势对称和非古典对称,得到了某些方程的新的势对称和新的对称,同时也得到了其伴随系统的新的对称,并求出了一些相似解．这些解对进一步研究这些非线性偏微分方程所描述的物理现象具有广泛的应用价值．     

An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints

A table constraint is explicitly represented as its set of solutions or non-solutions. This ad hoc (or extensional) representation may require space exponential to the arity of the constraint, making enforcing GAC expensive. In this paper, we address the space and time inefficiencies simultaneously by presenting the mddc constraint. mddc is a global constraint that represents its (non-)solutions with a multi-valued decision diagram (MDD). The MDD-based representation has the advantage that it can be exponentially smaller than a table. The associated GAC algorithm (called mddc) has time complexity linear to the size of the MDD, and achieves full incrementality in constant time. In addition, we show how to convert a positive or negative table constraint into an mddc constraint in time linear to the size of the table. Our experiments on structured problems, car sequencing and still-life, show that mddc is also a fast GAC algorithm for some global constraints such as sequence and regular. We also show that mddc is faster than the state-of-the-art generic GAC algorithms in Gent et al. (2007), Lecoutre and Szymanek (2006), Lhomme and Régin (2005) for table constraint.