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.     

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.     

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.     

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.     

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.     

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.     

On boundary conditions for adjoint variables in problems with state variable inequality constraints

This correspondence discusses boundary conditions for adjoint variables in problems with state variable inequality constraints. Particular attention is given to inequality terminal constraints. It is shown that it is important to identify whether the boundary of the state space is "absorbing" or not. An example is given to show the importance of these considerations in determining optimal trajectories.     

A hybrid formulation for treatment of point-wise state variable constraints in dynamic response optimization

This paper presents methods of design sensitivity analysis and optimization of dynamic response of mechanical and structural systems. The point-wise state variable constraint function is divided into time sub-domains such that each sub-domain contains only one local maximum point. Then, the original constraint is replaced by a number of equivalent functional constraints. Each functional constraint is the integration of the positive value of the original constraint over its own time sub-domain. A direct differentiation method and three adjoint variable methods of design sensitivity analysis are presented. All of these methods are discussed and compared. It turns out that two of the adjoint variable methods are more efficient than others. A hybrid optimization algorithm based on these methods is proposed in detail. Two problems are solved for optimal design. Comparisons of results with those available in the literature are made. Numerical experience with the proposed method is discussed in detail. It is concluded that the new formulation is extremely efficient and converges to either optimal or near optimal solutions without any difficulty.     

Trees and linked lists with variable ordering relations (RTR structures)

In the paper, new forms of structural trees and linked lists with variable ordering relations (RTR trees and RTR lists) are considered. The use of them makes it possible to apply a scheme of forward kinematics to simulating the behavior of 3D objects with a reorganizable structure as well as to make the logic of the behavior simulation more reasonable.     

Partial symmetries for nonlinear systems

We define the concept of partial symmetry for nonlinear systems, which is an intermediate notion between the concepts of symmetry and controlled invariance. It is shown how this concept can be used for a decomposition theory of nonlinear systems and is particularly suited as a framework for treating input-output decoupling problems.     

A note on some collapse results of valued constraints

Valued constraint satisfaction problem (VCSP) is an optimisation framework originally coming from Artificial Intelligence and generalising the classical constraint satisfaction problem (CSP). The VCSP is powerful enough to describe many important classes of problems. In order to investigate the complexity and expressive power of valued constraints, a number of algebraic tools have been developed in the literature. In this note we present alternative proofs of some known results without using the algebraic approach, but by representing valued constraints explicitly by combinations of other valued constraints.     

On some families of languages related to developmental systems

OL systems and TOL systems are the simplest mathematical models for the study of the development of biological organisms with or without a variable environment, respectively. This paper contributes to the study of the properties of the languages generated by these systems and by their generalizations. Macro OL (TOL) languages are languages obtained by substituting languages of a given type in OL (TOL) languages. We study properties of certain families of macro OL (TOL) languages in particular we show that they are full AFL's.

We observe that OL, TOL systems and many of their generalizations can be viewed as special classes of index grammars.     

Reduction of some linear optimal control problems with integral constraints

We consider the relationship between the continuous and the impulse control forms of the problem of sequential optimization of a finite system of deviations. Dual mathematical programming constructs are considered. Equivalence conditions by the end result are established for control procedures using ordinary and simple generalized functions.Translated from Kibernetika, No. 4, pp. 59–64, July–August, 1990.     

Topology optimization of truss-like continua with three families of members model under stress constraints

A method to minimize structural volume under stress constraints subject to multiple load cases is presented. A new material model is developed and employed to simulate the constitutive relation of the truss-like continuum. It is assumed that there are infinite numbers of members with infinitesimal spaces along three orientations at any position. The densities and orientations of members at all nodes are taken as design variables. An iterative optimization method is presented. In one iteration step, design variables are optimized separately and independently. The orientations of three families of members at every node are optimized by mathematics program method. Fully stressed criterion is adapted to optimize member densities. In the every iteration step, member densities are adjusted to make their strains smaller than the permissible values while the stress states is assumed to keep unchanged. The densities and orientations of members at any point inside an element are obtained by their interpolating the corresponding values (i.e., the densities and orientations) at the nodes of the element. These values vary continuously inside an element and the intermediate values are not suppressed. By using this technique the optimal truss-like continuum is formed, which represents for member distribution field. Once parts of members are chosen, discrete truss can be constructed according to the continuous member distributive field. This discrete structure is a nearly optimal structure. In above process, there are no numerical instabilities such as checkerboard and mesh-dependency. Numerical examples are presented to demonstrate the effectiveness of the present method.     

Multiplicity results for some elliptic problems with nonlinear boundary conditions involving variable exponents

In this paper we analyze an elliptic partial differential equation involving variable exponent growth conditions coupled with a nonlinear boundary condition. We show the existence of infinitely many bounded weak solutions provided there is a suitable oscillatory behavior of the nonlinearity either at infinity or at zero. Our proofs rely on a method due to Saint Raymond.     

Algorithms to solve some problems of concave programming with linear constraints

Consideration was given to the separable problem of concave programming with linear constraints for which two groups of new algorithms relying on a unique theoretical basis were proposed. The first group of (precise) algorithms approximates the optimal value of a functional from below, the second group of (mostly approximate) algorithms, does this from above.