A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity

This paper proposes a two-stage stochastic programming model for the parallel machine scheduling problem where the objective is to determine the machines' capacities that maximize the expected net profit of on-time jobs when the due dates are uncertain. The stochastic model decomposes the problem into two stages: The first (FS) determines the optimal capacities of the machines whereas the second (SS) computes an estimate of the expected profit of the on-time jobs for given machines' capacities. For a given sample of due dates, SS reduces to the deterministic parallel weighted number of on-time jobs problem which can be solved using the efficient branch and bound of M’Hallah and Bulfin [16]. FS is tackled using a sample average approximation (SAA) sampling approach which iteratively solves the problem for a number of random samples of due dates. SAA converges to the optimum in the expected sense as the sample size increases. In this implementation, SAA applies a ranking and selection procedure to obtain a good estimate of the expected profit with a reduced number of random samples. Extensive computational experiments show the efficacy of the stochastic model.     

Model order reduction methods for coupled systems in the time domain using Laguerre polynomials

In this paper, based on Laguerre polynomials, we present new methods for model reduction of coupled systems in the time domain. By appropriately selected projection matrices, a reduced order system is produced to retain the topology structure of the original system. Meanwhile, it preserves a desired number of Laguerre coefficients of the system’s output, thereby providing good approximation accuracy. We also study the two-sided projection method in the time domain, as well as the stability of reduced order systems. Two numerical examples are used to illustrate the efficiency of the proposed methods.     

Stochastic approximation learning for mixtures of multivariate elliptical distributions

Most of the current approaches to mixture modeling consider mixture components from a few families of probability distributions, in particular from the Gaussian family. The reasons of these preferences can be traced to their training algorithms, typically versions of the Expectation-Maximization (EM) method. The re-estimation equations needed by this method become very complex as the mixture components depart from the simplest cases. Here we propose to use a stochastic approximation method for probabilistic mixture learning. Under this method it is straightforward to train mixtures composed by a wide range of mixture components from different families. Hence, it is a flexible alternative for mixture learning. Experimental results are presented to show the probability density and missing value estimation capabilities of our proposal.     

A numerical modelling for the extraction of decay regions from color images of monuments

An innovative application focused on the segmentation of decay zones from images of stone materials is presented. The adopted numerical approach to extract decay regions from the color images of monuments provides a tool that helps experts analyze degraded regions by contouring them. In this way even if the results of the proposed procedure depend on the evaluation of experts, the approach can be a contribution to improving the efficiency of the boundary detection process. The segmentation is a process that allows an image to be divided into disjoint zones so that partitioned zones contain homogeneous characteristics. The numerical method, used to segment color images, is based on the theory of interface evolution, which is described by the eikonal equation. We adopted the fast marching technique to solve the upwind finite difference approximation of the eikonal equation. The fast marching starts from a seed point in the region of interest and generates a front which evolves according to a specific speed function until the boundary of the region is identified. We describe the segmentation results obtained with two speed functions, attained by the image gradient computation and color information about the object of interest. Moreover, we present the extension of the working modality of the method by introducing the possibility to extract the regions not only in a local way but also in a global way on the entire image. In this case, in order to improve the segmentation efficiency the application of the fast marching technique starts with more seed points defined as seed regions. The study case concerns the impressive remains of the Roman Theatre in the city of Aosta (Italy). In the image segmentation process the color space L^∗a^∗b^∗$L^{\ast }{a}^{\ast }{b}^{\ast }$ is utilized.     

Medial axis computation for planar free-form shapes

We present a simple, efficient, and stable method for computing—with any desired precision—the medial axis of simply connected planar domains. The domain boundaries are assumed to be given as polynomial spline curves. Our approach combines known results from the field of geometric approximation theory with a new algorithm from the field of computational geometry. Challenging steps are (1) the approximation of the boundary spline such that the medial axis is geometrically stable, and (2) the efficient decomposition of the domain into base cases where the medial axis can be computed directly and exactly. We solve these problems via spiral biarc approximation and a randomized divide & conquer algorithm.     

Combining feature spaces for classification

In this paper we offer a variational Bayes approximation to the multinomial probit model for basis expansion and kernel combination. Our model is well-founded within a hierarchical Bayesian framework and is able to instructively combine available sources of information for multinomial classification. The proposed framework enables informative integration of possibly heterogeneous sources in a multitude of ways, from the simple summation of feature expansions to weighted product of kernels, and it is shown to match and in certain cases outperform the well-known ensemble learning approaches of combining individual classifiers. At the same time the approximation reduces considerably the CPU time and resources required with respect to both the ensemble learning methods and the full Markov chain Monte Carlo, Metropolis-Hastings within Gibbs solution of our model. We present our proposed framework together with extensive experimental studies on synthetic and benchmark datasets and also for the first time report a comparison between summation and product of individual kernels as possible different methods for constructing the composite kernel matrix.     

Numerical approximation of incompressible flows with net flux defective boundary conditions by means of penalty techniques

We consider incompressible flow problems with defective boundary conditions prescribing only the net flux on some inflow and outflow sections of the boundary. As a paradigm for such problems, we simply refer to Stokes flow. After a brief review of the problem and of its well posedness, we discretize the corresponding variational formulation by means of finite elements and looking at the boundary conditions as constraints, we exploit a penalty method to account for them. We perform the analysis of the method in terms of consistency, boundedness and stability of the discrete bilinear form and we show that the application of the penalty method does not affect the optimal convergence properties of the finite element discretization. Since the additional terms introduced to account for the defective boundary conditions are non-local, we also analyze the spectral properties of the equivalent algebraic formulation and we exploit the analysis to set up an efficient solution strategy. In contrast to alternative discretization methods based on Lagrange multipliers accounting for the constraints on the boundary, the present scheme is particularly effective because it only mildly affects the structure and the computational cost of the numerical approximation. Indeed, it does not require neither multipliers nor sub-iterations or additional adjoint problems with respect to the reference problem at hand.     

Improving the generalization performance of RBF neural networks using a linear regression technique

In this paper we present a method for improving the generalization performance of a radial basis function (RBF) neural network. The method uses a statistical linear regression technique which is based on the orthogonal least squares (OLS) algorithm. We first discuss a modified way to determine the center and width of the hidden layer neurons. Then, substituting a QR algorithm for the traditional Gram–Schmidt algorithm, we find the connected weight of the hidden layer neurons. Cross-validation is utilized to determine the stop training criterion. The generalization performance of the network is further improved using a bootstrap technique. Finally, the solution method is used to solve a simulation and a real problem. The results demonstrate the improved generalization performance of our algorithm over the existing methods.     

有向无环图最小度生成树问题的一种近似算法

计算具有较小度的生成树是算法与复杂性研究的一个基本问题,同时在网络设计等领域具有重要应用.给定具有n个顶点的有向无环图G=(V,E)和根顶点r∈ V,最小度生成树问题欲求一棵以r为根的生成树T,使得在G的所有以r为根的生成树中T的最大度最小.给出该问题的一种迭代的多项式时间近似算法.该算法所求树的度不超过△*+1,其中△*为某一最优树的度.算法的时间复杂度为O(n2logn),其中n为顶点数目.算法没有运用过多的枚举,其实际运行时间要快得多.