Linear-time filtering algorithms for the disjunctive constraint and a quadratic filtering algorithm for the cumulative not-first not-last

We present new filtering algorithms for Disjunctive and Cumulative constraints, each of which improves the complexity of the state-of-the-art algorithms by a factor of log n. We show how to perform Time-Tabling and Detectable Precedences in linear time on the Disjunctive constraint. Furthermore, we present a linear-time Overload Checking for the Disjunctive and Cumulative constraints. Finally, we show how the rule of Not-first/Not-last can be enforced in quadratic time for the Cumulative constraint. These algorithms rely on the union find data structure, from which we take advantage to introduce a new data structure that we call it time line. This data structure provides constant time operations that were previously implemented in logarithmic time by the Θ-tree data structure. Experiments show that these new algorithms are competitive even for a small number of tasks and outperform existing algorithms as the number of tasks increases. We also show that the time line can be used to solve specific scheduling problems.     

A new algorithm for resolution of the quadratic programming problem with fuzzy relation inequality constraints

The minimization problem of a quadratic objective function with the max-product fuzzy relation inequality constraints is studied in this paper. In this problem, its objective function is not necessarily convex. Hence, its Hessian matrix is not necessarily positive semi-definite. Therefore, we cannot apply the modified simplex method to solve this problem, in a general case. In this paper, we firstly study the structure of its feasible domain. We then use some properties of n × n real symmetric indefinite matrices, Cholesky’s decomposition, and the least square technique, and convert the problem to a separable programming problem. Furthermore, a relation in terms of a closed form is presented to solve it. Finally, an algorithm is proposed to solve the original problem. An application example in the economic area is given to illustrate the problem. Of course, there are other application examples in the area of digital data service and reliability engineering.     

Extension of a linear quadratic tracking algorithm include control constraints

Pindyck's [1] algorithm is extended to include problems with magnitude constraints on the controls. The modification to the original solution involves only an additional term (containing the co-constraint vectors) each in the "tracking vector" and the optimal control. The co-contraint vectors are found by iteration using a gradient procedure.     

基于资源特征的协同过滤算法的研究

以往的协同过滤推荐算法具有数据稀疏性问题,而对于新资源还具有冷启动问题。为此提出了一种基于资源特征的协同过滤推荐方法。通过收集和分析用户的行为,将用户对于资源的喜好转化为用户对于关键词的兴趣权重,将用户兴趣的改变表示为用户兴趣关键词权重的改变,以此来建立和更新用户兴趣模型。最后,通过发现用户兴趣模型与资源模型之间的联系从而达到资源推荐的目的。实验表明,该算法不仅可以跟踪用户的兴趣变迁,而且没有数据稀疏性问题和新资源的冷启动问题。     

离散系统方差约束鲁棒H2/H∞滤波的新算法

考虑带有稳态误差方差约束的线性受扰系统的鲁棒H2/H∞滤波问题.引入了广义逆矩阵,提出了一个新的算法.通过直接解两个Riccati方程后,获得滤波器,并且同时满足3个性能要求:滤波过程是渐近稳定的;每个状态的稳态估计误差方差不超过规定的上界;从外部噪声输入到误差状态输出的传递函数的H∞范数满足规定的上界.一个数字例子说明了这种设计方法的有效性.     

A quadratic mindlin element using shear constraints

“Shear constraints” are used to derive a displacement-based bending element for the analysis of thin and moderately thick plates of general plan form. As a starting point, the eight serendipity modes are adopted for the normal rotations and the nine Lagrangian modes for the transverse displacement, w. Subsequently, the shear constraints are used to eliminate the mid-side and central w variables so that the final element has three degrees-of-freedom at the corners and two at each mid-side. The bending energy is integrated using the standard formulation for the serendipity Mindlin element (with two-point Gaussian integration) so that the only modifications to that element involve the shear strain-displacement matrix. The constraints, which are used to implement these modifications, involve explicit algebraic expressions rather than numerical integration or matrix manipulation. A Fortran subroutine is provided for implementing these changes in a general quadrilateral. Using hierarchical displacement functions, the mid-side displacement variables Δw, that are missing from the standard serendipity element, may be simply constrained to zero as “boundary conditions”. Numerical experiments are presented which show that the element does not “lock” and that it gives excellent results for both thin and moderately thick plates. It also passes the patch test for a general quadrilateral.     

Domain filtering consistencies for non-binary constraints

In non-binary constraint satisfaction problems, the study of local consistencies that only prune values from domains has so far been largely limited to generalized arc consistency or weaker local consistency properties. This is in contrast with binary constraints where numerous such domain filtering consistencies have been proposed. In this paper we present a detailed theoretical, algorithmic and empirical study of domain filtering consistencies for non-binary problems. We study three domain filtering consistencies that are inspired by corresponding variable based domain filtering consistencies for binary problems. These consistencies are stronger than generalized arc consistency, but weaker than pairwise consistency, which is a strong consistency that removes tuples from constraint relations. Among other theoretical results, and contrary to expectations, we prove that these new consistencies do not reduce to the variable based definitions of their counterparts on binary constraints. We propose a number of algorithms to achieve the three consistencies. One of these algorithms has a time complexity comparable to that for generalized arc consistency despite performing more pruning. Experiments demonstrate that our new consistencies are promising as they can be more efficient than generalized arc consistency on certain non-binary problems.     

Improved filtering for weighted circuit constraints

We study the weighted circuit constraint in the context of constraint programming. It appears as a substructure in many practical applications, particularly routing problems. We propose a domain filtering algorithm for the weighted circuit constraint that is based on the 1-tree relaxation of Held and Karp. In addition, we study domain filtering based on an additive bounding procedure that combines the 1-tree relaxation with the assignment problem relaxation. Experimental results on Traveling Salesman Problem instances demonstrate that our filtering algorithms can dramatically reduce the problem size. In particular, the search tree size and solving time can be reduced by several orders of magnitude, compared to existing constraint programming approaches. Moreover, for medium-size problem instances, our method is competitive with the state-of-the-art special-purpose TSP solver Concorde.     

A modular algorithm for resource allocation

This paper concerns resource allocation in distributed message passing systems, i.e., the scheduling of accesses to exclusive system resources shared among concurrent processes. An efficient modular resource allocation algorithm is presented that uses any arbitrary resource allocation algorithm as a subroutine. It improves the performance of the subroutine by letting each process wait only for its currently conflicting processes, and therefore, allows more concurrency. For appropriate choices of the subroutine, we obtain resource allocation algorithms with the minimum worst case response times. Simulation studies were conducted which also indicate that on average, the obtained algorithms perform faster and require a smaller number of messages than other previously known algorithms, especially when resource contention among processes is high and the average time that a process remains in the critical region is large. Received: May 1997 / Accepted: May 1998     

A one-pass algorithm for shape-preserving quadratic spline interpolation

Schumaker (1983) and McAllister and Roulier (1981) have proposed algorithms for shape-preserving interpolation using quadratic splines. The former requires the user to provide and perhaps to adjust estimates of the slope at the data points. Here we show that, for a particular slope estimation technique, the two methods are identical, and that in this case the Schumaker algorithm automatically generates shape-preserving interpolants. Furthermore, in case of convex data the slopes are improved iteratively to produce more visually pleasing curves.     

A resource aware software partitioning algorithm based on mobility constraints in pervasive grid environments

Pervasive computing suffers from resource limitations of mobile devices, while grid computing can utilize almost unlimited resources distributed in the whole Internet. The conjunction of such two paradigms generates a new promising one, called pervasive grid computing, where mobile users can use handheld devices to access abundant resources and services in the grid. In this paper, a novel software partitioning algorithm is presented, which is suitable for pervasive grid to optimally allocate software components between a mobile device and one or more servers, with the goal of saving the resources of mobile devices. The algorithm takes into account component mobility constraints to not only prevent violating execution requirements of the application, but also to fully exploit component mobility, replication and rebinding to conserve more resources as compared to previous works. Another distinguishing feature of the algorithm is its generality, which can be applied to minimize network bandwidth usage, response time and energy consumption, respectively or simultaneously. Extensive simulation results have demonstrated the validity and effectiveness of the proposed algorithm in various environments.     

Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints

Most publications in shop scheduling area focus on the static scheduling problems and seldom take into account the dynamic disturbances such as machine breakdown or new job arrivals. Motivated by the computational complexity of the scheduling problems, genetic algorithms (GAs) have been applied to improve both the efficiency and the effectiveness for NP-hard optimization problems. However, a pure GA-based approach tends to generate illegal schedules due to the crossover and the mutation operators. It is often the case that the gene expression or the genetic operators need to be specially tailored to fit the problem domain or some other schemes may be combined to solve the scheduling problems. This study presents a GA-based approach combined with a feasible energy function for multiprocessor scheduling problems with resource and timing constraints in dynamic real-time scheduling. Moreover, an easy-understood genotype is designed to generate legal schedules. The results of the experiments demonstrate that the proposed approach performs rapid convergence to address its applicability and generate good-quality schedules.     

Constraint propagation on quadratic constraints

This paper considers constraint propagation methods for continuous constraint satisfaction problems consisting of linear and quadratic constraints. All methods can be applied after suitable preprocessing to arbitrary algebraic constraints. The basic new techniques consist in eliminating bilinear entries from a quadratic constraint, and solving the resulting separable quadratic constraints by means of a sequence of univariate quadratic problems. Care is taken to ensure that all methods correctly account for rounding errors in the computations. Various tests and examples illustrate the advantage of the presented method.     

A new branch-and-bound algorithm for standard quadratic programming problems

In this paper we propose convex and LP bounds for standard quadratic programming (StQP) problems and employ them within a branch-and-bound approach. We first compare different bounding strategies for StQPs in terms both of the quality of the bound and of the computation times. It turns out that the polyhedral bounding strategy is the best one to be used within a branch-and-bound scheme. Indeed, it guarantees a good quality of the bound at the expense of a very limited computation time. The proposed branch-and-bound algorithm performs an implicit enumeration of all the KKT (stationary) points of the problem. We compare different branching strategies exploiting the structure of the problem. Numerical results on randomly generated problems (with varying density of the underlying convexity graph) are reported which show the effectiveness of the proposed approach, in particular in limiting the growth of the number of nodes in the branch-and-bound tree as the density of the underlying graph increases.     

Stability analysis for time-varying systems via quadratic constraints

In this paper, we introduce the concept of “quadratic constraint” (QC) to deal with various stability problems for infinite dimensional linear discrete time-varying (LTV) systems. First, we derive a necessary and sufficient condition for the close-loop stability based on quadratic constraints (QCs). An equivalent condition of this stability criterion presents the relationship between the stabilization of each finite dimensional truncation system and that of the whole system. Moreover, applying this stability criterion and the complete finiteness of the nest algebra, we show that the plant is stabilizable if and only if it has a single strong representation. Finally, we use QCs to give a necessary and sufficient condition for the robust stabilization of connected uncertainty set defined by gap metric.     

A Lagrangian heuristic for satellite range scheduling with resource constraints

The data exchange between ground stations and satellite constellations is becoming a challenging task, as more and more communication requests must be daily scheduled on a few, expensive stations located all around the Earth. Most of the scheduling procedures adopted in practice cannot cope with such complexity, and the development of optimization-based tools is strongly spurred.     

中值滤波的快速算法

利用矩形相邻窗口间的相关信息,提出了中值滤波的快速算法。该算法可将传统算法的复杂度O(n^2）简化为O(n）,运算速度大大提高。