An Algorithm for Timing Verification of Systems Constrained by Min–max Inequalities

To determine the maximum separation between events for nonrepetitive systems with max and linear constraints, there are the “iterative tightening from above” (ITA) approach and the “iterative tightening from below” (ITB) approach. Since such systems can be formulated as systems constrained by min–max inequalities, this paper gives an algorithm named MMIMaxSep for solving min–max inequalities. The algorithm is a generalization and a mathematically elegant reformulation of Yen et al.’s MaxSeparation algorithm which uses the ITB approach. Our numerical experiments indicate that MMIMaxSep is very efficient. Moreover, MMIMaxSep has a unique advantage of being able to directly handle tree-represented min–max functions, and its complexity is closely related to the complexity of computing cycle time of min–max functions.

Fuzzy min–max neural networks: from classification to regression

 In this paper we show two new learning algorithms for a fuzzy min–max neural network. The top down fuzzy min–max (TDFMM) algorithm modifies the classic Simpson's learning algorithm overcoming its main difficulties: the dependence on the presentation order of the patterns and the poor resolutive adaptation to the characteristics of input space. The top down fuzzy min–max regressor (TDFMMR) algorithm extends our neural network to solve regression problems by using a hybrid fuzzy classifier and a gradient descent algorithm.     

Min–Max Inequalities and the Timing Verification Problem with Max and Linear Constraints

In this paper the timing verification problem with max and linear constraints is formulated in min–max inequalities. An algorithm MMIsolve, based on the UBCsolve algorithm of Walkup, is proposed for solving min-max inequalities and for efficiently finding the maximum time separations between events. A concept of structural finite separation is introduced, and it is found that structural finite separation is a sufficient, but not necessary condition for finite separation. The two conditions are equivalent when the parameters are only allowed to take nonnegative values.This revised version was published online in May 2005 with corrections to the affiliations.     

Scenario relaxation algorithm for finite scenario-based min–max regret and min–max relative regret robust optimization

Most practical decision-making problems are compounded in difficulty by the degree of uncertainty and ambiguity surrounding the key model parameters. Decision makers may be confronted with problems in which no sufficient historical information is available to make estimates of the probability distributions for uncertain parameter values. In these situations, decision makers are not able to search for the long-term decision setting with the best long-run average performance. Instead, decision makers are searching for the robust long-term decision setting that performs relatively well across all possible realizations of uncertainty without attempting to assign an assumed probability distribution to any ambiguous parameter. In this paper, we propose an iterative algorithm for solving min–max regret and min–max relative regret robust optimization problems for two-stage decision-making under uncertainty (ambiguity) where the structure of the first-stage problem is a mixed integer (binary) linear programming model and the structure of the second-stage problem is a linear programming model. The algorithm guarantees termination at an optimal robust solution, if one exists. A number of applications of the proposed algorithm are demonstrated. All results illustrate good performance of the proposed algorithm.     

Robust iterative learning control for linear systems with multiple time-invariant parametric uncertainties

This article presents a novel robust iterative learning control algorithm (ILC) for linear systems in the presence of multiple time-invariant parametric uncertainties.The robust design problem is formulated as a min–max problem with a quadratic performance criterion subject to constraints of the iterative control input update. Then, we propose a new methodology to find a sub-optimal solution of the min–max problem. By finding an upper bound of the worst-case performance, the min–max problem is relaxed to be a minimisation problem. Applying Lagrangian duality to this minimisation problem leads to a dual problem which can be reformulated as a convex optimisation problem over linear matrix inequalities (LMIs). An LMI-based ILC algorithm is given afterward and the convergence of the control input as well as the system error are proved. Finally, we apply the proposed ILC to a generic example and a distillation column. The numerical results reveal the effectiveness of the LMI-based algorithm.     

A convex optimization approach to robust iterative learning control for linear systems with time-varying parametric uncertainties

In this paper, we present a new robust iterative learning control (ILC) design for a class of linear systems in the presence of time-varying parametric uncertainties and additive input/output disturbances. The system model is described by the Markov matrix as an affine function of parametric uncertainties. The robust ILC design is formulated as a min–max problem using a quadratic performance criterion subject to constraints of the control input update. Then, we propose a novel methodology to find a suboptimal solution of the min–max optimization problem. First, we derive an upper bound of the worst-case performance. As a result, the min–max problem is relaxed to become a minimization problem in the form of a quadratic program. Next, the robust ILC design is cast into a convex optimization over linear matrix inequalities (LMIs) which can be easily solved using off-the-shelf optimization solvers. The convergences of the control input and the error are proved. Finally, the robust ILC algorithm is applied to a physical model of a flexible link. The simulation results reveal the effectiveness of the proposed algorithm.     

Output feedback model predictive control for LPV systems based on quasi-min–max algorithm

This paper proposes a robust output feedback model predictive control (MPC) scheme for linear parameter varying (LPV) systems based on a quasi-min–max algorithm. This approach involves an off-line design of a robust state observer for LPV systems using linear matrix inequality (LMI) and an on-line robust output feedback MPC algorithm using the estimated state. The proposed MPC method for LPV systems is applicable for a variety of systems with constraints and guarantees the robust stability of the output feedback systems. A numerical example for an LPV system subject to input constraints is given to demonstrate its effectiveness.     

Regularized Linear Fuzzy Clustering and Probabilistic PCA Mixture Models

Fuzzy$c$-means (FCM)-type fuzzy clustering approaches are closely related to Gaussian mixture models (GMMs) and EM-like algorithms have been used in FCM clustering with regularized objective functions. Especially, FCM with regularization by Kullback–Leibler information (KLFCM) is a fuzzy counterpart of GMMs. In this paper, we propose to apply probabilistic principal component analysis (PCA) mixture models to linear clustering following a discussion on the relationship between local PCA and linear fuzzy clustering. Although the proposed method is a kind of the constrained model of KLFCM, the algorithm includes the fuzzy$c$-varieties (FCV) algorithm as a special case, and the algorithm can be regarded as a modified FCV algorithm with regularization by K–L information. Numerical experiments demonstrate that the proposed clustering algorithm is more flexible than the maximum likelihood approaches and is useful for capturing local substructures properly.     

Bi-objective parallel machines scheduling with sequence-dependent setup times using hybrid metaheuristics and weighted min–max technique

In the literature of multi-objective problem, there are different algorithms to solve different optimization problems. This paper presents a min–max multi-objective procedure for a dual-objective, namely make span, and sum of the earliness and tardiness of jobs in due window machine scheduling problems, simultaneously. In formulation of min–max method when this method is combined with the weighting method, the decision maker can have the flexibility of mixed use of weights and distance parameter to yield a set of Pareto-efficient solutions. This research extends the new hybrid metaheuristic (HMH) to solve parallel machines scheduling problems with sequence-dependent setup time that comprises three components: an initial population generation method based on an ant colony optimization (ACO), a simulated annealing (SA) as an evolutionary algorithm employs certain probability to avoid becoming trapped in a local optimum, and a variable neighborhood search (VNS) which involves three local search procedures to improve the population. In addition, two VNS-based HMHs, which are a combination of two methods, SA/VNS and ACO/VNS, are also proposed to solve the addressed scheduling problems. A design of experiments approach is employed to calibrate the parameters. The non-dominated sets obtained from HMH and two best existing bi-criteria scheduling algorithms are compared in terms of various indices and the computational results show that the proposed algorithm is capable of producing a number of high-quality Pareto optimal scheduling plans. Aside, an extensive computational experience is carried out to analyze the different parameters of the algorithm.     

Explicit solution of min–max MPC with additive uncertainties and quadratic criterion

Min–max model predictive control (MMMPC) is one of the strategies proposed to control plants subject to bounded uncertainties. This technique is very difficult to implement in real time because of the computation time required. Recently, the piecewise affine nature of this control law has been proved for unconstrained linear systems with quadratic performance criterion. However, no algorithm to compute the explicit form of the control law was given. This paper shows how to obtain this explicit form by means of a constructive algorithm. An approximation to MMMPC in the presence of constraints is presented based on this algorithm.     

CUDA架构下大规模稠密线性方程组的并行求解

在Gauss-Jordan消去法的基础上,给出了一种适应于CUDA架构的改进Gauss-Jordan消去并行算法。通过分析该方法的处理过程以及CUDA架构的相应限制,在CUDA的grid-block-thread三层组织结构的基础上,从算法构造的角度提出了grid-strip-group-block-thread五层结构,给出了基础行以及全局基础行等概念,并构建了适应于CUDA架构的Gauss-Jordan消去法的并行版本,在最高维数为4 000维的大规模稠密线性方程组的算例求解上与串行Gauss-Jordan消去法进行了比较,实验结果表明,该算法能够充分利用GPU的硬件特性,有效地降低了大规模稠密线性方程组的求解时间。     

Dynamic Min-Max Problems

In this paper a method to check the solvability of a set of linear equations in the (max, min, +) algebra is described. Then, extensions to dynamic (or periodic) systems in the (max, min, +) algebra are provided. Further, some results regarding the uniqueness of solutions in both cases are given. Finally, we address a more general quasi periodic problem and provide an algorithm for its solution.     

Scheduling Equal-Length Jobs with Delivery times on Identical Processors

The problem of scheduling n jobs of equal duration p with release and delivery times on m identical processors with the objective to minimize the maximal job completion time is considered. An algorithm is proposed that has the time complexity O ( mn log n ) if the maximal job delivery time q max is bounded by some constant. This is better than the earlier known best bound of O ( mn 2 log( np / m )) for the version of the problem with non-restricted q max . The algorithm has the time complexity O(q_{\max }^2 n\log n\max \{ m,\;q_{\max } \} ) without the restriction on q max . As the presented computational experiments show, practical behavior of the algorithm remains good without restriction on q max , i.e., for arbitrarily long delivery times, the running time of the algorithm, in practice, does not depend on q max .     

Detecting and reconstructing subdivision connectivity

inverse subdivision algorithms , with linear time and space complexity, to detect and reconstruct uniform Loop, Catmull–Clark, and Doo–Sabin subdivision structure in irregular triangular, quadrilateral, and polygonal meshes. We consider two main applications for these algorithms. The first one is to enable interactive modeling systems that support uniform subdivision surfaces to use popular interchange file formats which do not preserve the subdivision structure, such as VRML, without loss of information. The second application is to improve the compression efficiency of existing lossless connectivity compression schemes, by optimally compressing meshes with Loop subdivision connectivity. Our Loop inverse subdivision algorithm is based on global connectivity properties of the covering mesh, a concept motivated by the covering surface from Algebraic Topology. Although the same approach can be used for other subdivision schemes, such as Catmull–Clark, we present a Catmull–Clark inverse subdivision algorithm based on a much simpler graph-coloring algorithm and a Doo–Sabin inverse subdivision algorithm based on properties of the dual mesh. Straightforward extensions of these approaches to other popular uniform subdivision schemes are also discussed. Published online: 3 July 2002     

A Dirichlet–Neumann type algorithm for contact problems with friction

Domain decomposition techniques provide a powerful tool for the numerical approximation of partial differential equations. We introduce a new algorithm for the numerical solution of a nonlinear contact problem with Coulomb friction between linear elastic bodies. The discretization of the nonlinear problem is based on mortar techniques. We use a dual basis Lagrange multiplier space for the coupling of the different bodies. The boundary data transfer at the contact zone is essential for the algorithm. It is realized by a scaled mass matrix which results from the mortar discretization on non-matching triangulations. We apply a nonlinear block Gauss–Seidel method as iterative solver which can be interpreted as a Dirichlet–Neumann algorithm for the nonlinear problem. In each iteration step, we have to solve a linear Neumann problem and a nonlinear Signorini problem. The solution of the Signorini problem is realized in terms of monotone multigrid methods. Numerical results illustrate the performance of our approach in 2D and 3D. Received: 20 March 2001 / Accepted: 1 February 2002 Communicated by P. Deuflhard     

Optimal Fleet Allocation of Freeway Service Patrols

As one component of traffic incident management systems, freeway service patrols (FSP) facilitate quick removal of incidents through faster response and reduced clearance time. This paper is to investigate how to allocate tow trucks among patrol beats to maximize the effectiveness of the FSP services. A min–max bi-level programming model is proposed to determine an optimal fleet allocation that minimizes the maximal system travel time that incidents may incur. A heuristic iterative solution algorithm is proposed to solve the model. Both the model and the algorithm are demonstrated and validated through a numerical example.     

An evolutionary algorithm for the resource-constrained project scheduling problem with minimum and maximum time lags

In this paper, we present an evolutionary algorithm (EVA) for solving the resource-constrained project scheduling problem with minimum and maximum time lags (RCPSP/max). EVA works on a population consisting of several distance-order-preserving activity lists representing feasible or infeasible schedules. The algorithm uses the conglomerate-based crossover operator, the objective of which is to exploit the knowledge of the problem to identify and combine those good parts of the solution that have really contributed to its quality. In a recent paper, Valls et al. (European J. Oper. Res. 165, 375–386, 2005) showed that incorporating a technique called double justification (DJ) in RCPSP heuristic algorithms can produce a substantial improvement in the results obtained. EVA also applies two double justification operators DJmax and DJU adapted to the specific characteristics of problem RCPSP/max to improve all solutions generated in the evolutionary process. Computational results in benchmark sets show the merit of the proposed solution method.     

Distributed model predictive control for polytopic uncertain systems subject to actuator saturation

In this paper, we present a distributed model predictive control (MPC) algorithm for polytopic uncertain systems subject to actuator saturation. The global system is decomposed into several subsystems. A set invariance condition for polytopic uncertain system with input saturation is identified and a min–max distributed MPC strategy is proposed. The distributed MPC controller is designed by solving a linear matrix inequalities (LMIs) optimization problem. An iterative algorithm is developed for making coordination among subsystems. Case studies are carried out to illustrate the effectiveness of the proposed algorithm.     

Shrinkage of arcs in solving systems of linear inequalities with graph structure

To solve systems of linear equalities with graph structure, it is necessary to execute operations of sequential shrinkage of terminal and intermediated arcs. The paper deals with an algorithm of shrinkage of these arcs for a graph specified as an adjancency matrix. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 167–170, March–April, 2000.     

T–S fuzzy model adopted SLAM algorithm with linear programming based data association for mobile robots

This paper describes a Takagi–Sugeno (T–S) fuzzy model adopted solution to the simultaneous localization and mapping (SLAM) problem with two-sensor data association (TSDA) method. Nonlinear process model and observation model are formulated as pseudolinear models and rewritten with a composite model whose local models are linear according to T–S fuzzy model. Combination of these local state estimates results in global state estimate. This paper introduces an extended TSDA (ETSDA) method for the SLAM problem in mobile robot navigation based on an interior point linear programming (LP) approach. Simulation results are given to demonstrate that the ETSDA method has low computational complexity and it is more accurate than the existing single-scan joint probabilistic data association method. The above system is implemented and simulated with Matlab to claim that the proposed method yet finds a better solution to the SLAM problem than the conventional extended Kalman filter–SLAM algorithm.