Heuristic Rejection in Interval Global Optimization

Based on the investigation carried out in Ref. 1, this paper incorporates new studies about the properties of inclusion functions on subintervals while a branch-and-bound algorithm is solving global optimization problems. It is found that the relative place of the global minimum value within the inclusion function value of the objective function at the current interval indicates mostly whether the given interval is close to a minimizer point. This information is used in a heuristic interval rejection rule that can save a considerable amount of computation. Illustrative examples are discussed and an extended numerical study shows the advantages of the new approach.     

一种改进的数字散斑相关方法用于检测人的口型变化

提出了一种基于数字散斑相关测量技术的口型变化检测技术,该技术以白光数字散斑相关测量方法为基础,根据实际应用的需要,引入重心算法并进行了改进,可以实时地检测人说话时的口型变化。通过实验表明,提出的方法是一种实用的、快速、高精度的口型变化测试方法,可为今后的唇语识别技术奠定基础。     

New Branch-and-Cut Algorithm for Bilevel Linear Programming

Linear mixed 0–1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0–1 Gomory cuts to BLP. The first phase of our new algorithm generates Gomory-like cuts. The second phase consists of a branch-and-bound procedure to ensure finite termination with a global optimal solution. Different features of the algorithm, in particular, the cut selection and branching criteria are studied in details. We propose also a set of algorithmic tests and procedures to improve the method. Finally, we illustrate the performance through numerical experiments. Our algorithm outperforms pure branch-and-bound when tested on a series of randomly generated problems. Work of the authors was partially supported by FCAR, MITACS and NSERC grants.     

How to assess and report the performance of a stochastic algorithm on a benchmark problem: mean or best result on a number of runs?

Some authors claim that reporting the best result obtained by a stochastic algorithm in a number of runs is more meaningful than reporting some central statistic. In this short note, we analyze and refute the main argument brought in favor of this statement.     

A numerically stable algorithm for two server queue models

In this paper, we consider a queueing system in which there are two exponential servers, each having his own queue, and arriving customers will join the shorter queue. Based on the results given in Flatto and McKean, we rewrite the formula for the probability that there are exactlyk customers in each queue, wherek = 0, 1,…. This enables us to present an algorithm for computing these probabilities and then to find the joint distribution of the queue lengths in the system. A program and numerical examples are given.     

Probabilistic Analysis of Condition Numbers for Linear Programming

In this paper, we provide bounds for the expected value of the log of the condition number C(A) of a linear feasibility problem given by a n × m matrix A (Ref. 1). We show that this expected value is O(min{n, m log n}) if n > m and is O(log n) otherwise. A similar bound applies for the log of the condition number C _R(A) introduced by Renegar (Ref. 2).     

A parallel inexact newton method for stochastic programs with recourse

A parallel inexact Newton method with a line search is proposed for two-stage quadratic stochastic programs with recourse. A lattice rule is used for the numerical evaluation of multi-dimensional integrals, and a parallel iterative method is used to solve the quadratic programming subproblems. Although the objective only has a locally Lipschitz gradient, global convergence and local superlinear convergence of the method are established. Furthermore, the method provides an error estimate which does not require much extra computation. The performance of the method is illustrated on a CM5 parallel computer.This work was supported by the Australian Research Council and the numerical experiments were done on the Sydney Regional Centre for Parallel Computing CM5.     

Numerical solution of eigenvalue problems for Hamiltonian systems

This paper discusses the numerical solution of eigenvalue problems for Hamiltonian systems of ordinary differential equations. Two new codes are presented which incorporate the algorithms described here; to the best of the author’s knowledge, these are the first codes capable of solving numerically such general eigenvalue problems. One of these implements a new new method of solving a differential equation whose solution is a unitary matrix. Both codes are fully documented and are written inPfort-verifiedFortran 77, and will be available in netlib/aicm/sl11f and netlib/aicm/sl12f.     

A comparison of two algorithms for the assignment problem

State-of-the-art computational results have shown that the shortest augmenting path (SAP) methods are more efficient than other primal-dual and primal-simplex based methods for solving the linear assignment problem on uniprocessor computers. There is, however, some controversy concerning their merits when compared with Bertsekas' auction algorithm on multiprocessor computers. In this study we investigate the performance of these competing methods on the Alliant FX/8. For each method, theoretical motivation, sources of parallelism and computational results are presented.     

Manufacturing cell formation using similarity coefficients and a parallel genetic TSP algorithm: Formulation and comparison

Many algorithms have been proposed to form manufacturing cells from component routings. However, many of these do not have the capability of solving large problems. We propose a procedure using similarity coefficients and a parallel genetic implementation of a TSP algorithm that is capable of solving large problems of up to 1000 parts and 1000 machines. In addition, we also compare our procedure with many existing procedures using nine well-known problems from the literature.

The results show that the proposed procedure compares well with the existing procedures and should be useful to practitioners and researchers.