AE1: An extension matrix approximate method for the general covering problem

A new approach, the extension matrix approach, is introduced and used to show that some optimization problems in general covering problem areNP-hard. Approximate solutions for these problems are given. Combining these approximate solutions, this paper presents an approximately optimal covering algorithm,AE1. Implementation shows thatAE1 is efficient and gives optimal or near optimal results.This research was supported in part by the National Science Foundation under Grant DCR 84-06801, Office of Naval Research under Grant N00014-82-K-0186, Defense Advanced Research Project Agency under Grant N00014-K-85-0878, and Education Ministry of the People's Republic of China.On leave from Harbin Institute of Technology, Harbin, China.     

An iterative algorithm for a least squares solution of a matrix equation

In this article, we propose an iterative algorithm to compute the minimum norm least-squares solution of AXB+CYD=E, based on a matrix form of the algorithm LSQR for solving the least squares problem. We then apply this algorithm to compute the minimum norm least-squares centrosymmetric solution of min _X ‖AXB?E‖ _F . Numerical results are provided to verify the efficiency of the proposed method.     

An iterative algorithm for approximate orthogonalisation of symmetric matrices

In a previous article, one of the authors presented an extension of an iterative approximate orthogonalisation algorithm, due to Z. Kovarik, for arbitrary rectangular matrices. In the present article, we propose a modified version of this extension for the class of arbitrary symmetric matrices. For this new algorithm, the computational effort per iteration is much smaller than for the initial one. We prove its convergence and also derive an error reduction factor per iteration. In the second part of the article, we show that we can eliminate the matrix inversion required by the previous algorithm in each iteration, by replacing it with a polynomial matrix expression. Some numerical experiments are also presented for a collocation discretisation of a first kind integral equation.     

An approximate solution to a jit-based ordering system

In this paper we consider a multi-stage multi-product production, inventory and transportation system including lot production processes and develop a goal programming model for a pull type ordering system based on the concept of a Just-In-Time(JIT) production system. We also present a pragmatic approach which reduces the required computational time for the formulated mixed integer goal programming problem using a mathematical programming modeling language. The proposed solution procedure is realized utilizing the post-optimal analysis which can be performed by the modeling language.     

Least-squares symmetric solution to the matrix equation AXB = C with the norm inequality constraint

In this paper, an iterative method to compute symmetric least-squares solution of the matrix equation AXB = C with the norm inequality constraint is proposed. For this method, without the error of calculation, a desired solution can be obtained with finitely iterate steps. Numerical experiments are performed to illustrate the efficiency and application of the algorithm.     

Conformal mapping for the efficient MFS solution of Dirichlet boundary value problems

In this work, we use conformal mapping to transform harmonic Dirichlet problems of Laplace’s equation which are defined in simply-connected domains into harmonic Dirichlet problems that are defined in the unit disk. We then solve the resulting harmonic Dirichlet problems efficiently using the method of fundamental solutions (MFS) in conjunction with fast fourier transforms (FFTs). This technique is extended to harmonic Dirichlet problems in doubly-connected domains which are now mapped onto annular domains. The solution of the resulting harmonic Dirichlet problems can be carried out equally efficiently using the MFS with FFTs. Several numerical examples are presented.      

The approximate solution of the Euclidean traveling salesman problem on a CRAY X-MP

The efficient use of MIMD computers calls for a careful choice of adequate algorithms as for an implementation taking into account the particular architecture. To demonstrate these facts, a parallel algorithm to find an approximate solution to the Euclidean Traveling Salesman Problem (ETSP) is presented. The algorithm is a parallelization of Karp's partitioning algorithm. It is a divide-and-conquer method for solving the ETSP approximately. Since the successor vertex to any vertex in the tour is usually a nearby vertex, the problem can be ‘geographically’ partitioned into subproblems which then can be solved independently. The resulting subtours can be combined into a single tour which is an approximate solution to the ETSP. The algorithm is implemented on a CRAY X-MP with two and four processors, and results using macrotasking and microtasking are presented.     

A guided genetic algorithm for diagonalization of symmetric and Hermitian matrices

The eigenvalues and eigenvectors of a matrix have many applications in engineering and science, such us studying and solving structural problems in both the treatment of signal or image processing, and the study of quantum mechanics. One of the most important aspects of an algorithm is the speed of execution, especially when it is used in large arrays. For this reason, in this paper the authors propose a new methodology using a genetic algorithm to compute all the eigenvectors and eigenvalues in real symmetric and Hermitian matrices. The algorithm uses a general-purpose library developed by the authors for genetic algorithms (GALGA). The speed of execution and the influence of population size have been studied. Moreover, the algorithm has been tested in different matrices and population sizes by comparing the speed of execution to the number of the eigenvectors. This new methodology is faster than the previous algorithm developed by the authors and all eigenvectors can be obtained with it. In addition, the performance using the Coope matrix has been tested contrasting the results with another technique published in the scientific literature.     

A subprogram for direct solution of Poisson equation in cylindrically symmetric geometry

A program for a direct solution of the Poisson equation in cylindrically symmetric geometry is described. It is based on the use of fast Fourier transforms for the axial solution, and an expansion in cubic B-splines for the radial solution.     

一类离散时间代数Riccati矩阵方程对称解的双迭代算法

利用逆矩阵的Neumann级数形式,将在线性二次优化问题中遇到的含未知矩阵之逆的离散时间代数Riccati矩阵方程(DTARME)转化为高次多项式矩阵方程,然后采用牛顿算法求高次多项式矩阵方程的对称解,并采用修正共轭梯度法求由牛顿算法每一步迭代计算导出的线性矩阵方程的对称解或者对称最小二乘解,建立求DTARME的对称解的双迭代算法。双迭代算法仅要求DTARME有对称解,不要求它的对称解唯一,也不对它的系数矩阵做附加限定。数值算例表明双迭代算法是有效的。     

On the solution of a nonlinear matrix equation for MIMO symmetric realizations

A result concerning a particular solution of a nonlinear solution matrix equation reported in a previous paper [2] and interesting for studying SISO systems, is extended to MIMO symmetric realizations. For such a class of systems other important SISO results can be generalized.     

A novel operational matrix method for solving singularly perturbed boundary value problems of fractional multi-order

In this paper, we will consider a wide class of singularly perturbed problems described by the differential equation of fractional multi-order with small parameter multiplying the highest derivative and the appropriate boundary conditions. We construct the linear B-spline operational matrix of fractional derivative in the Caputo sense and introduce a new operational method to solve the mentioned problems. The main characteristic behind this method is that it converts such problems to a system of algebraic equations and overcomes the difficulty and computational complexity induced by the problem. Some illustrative examples are included to demonstrate the validity and applicability of the method.     

An improved parallel Jacobi method for diagonalizing a symmetric matrix

We compare five implementations of the Jacobi method for diagonalizing a symmetric matrix. Two of these, the classical Jacobi and sequential sweep Jacobi, have been used on sequential processors. The third method, the parallel sweep Jacobi, has been proposed as the method of choice for parallel processors. The fourth and fifth methods are believed to be new. They are similar to the parallel sweep method but use different schemes for selecting the rotations.

The classical Jacobi method is known to take O(n⁴) time to diagonalize a matrix of order n. We find that the parallel sweep Jacobi run on one processor is about as fast as the sequential sweep Jacobi. Both of these methods take O(n³ log₂n) time. One of our new methods also takes O(n³ log₂n) time, but the other one takes only O(n³) time. The choice among the methods for parallel processors depends on the degree of parallelism possible in the hardware. The time required to diagonalize a matrix on a variety of architectures is modeled.

Unfortunately for proponents of the Jacobi method, we find that the sequential QR method is always faster than the Jacobi method. The QR method is faster even for matrices that are nearly diagonal. If we perform the reduction to tridiagonal form in parallel, the QR method will be faster even on highly parallel systems.     

Efficient approximate solution methods for the multi-commodity capacitated multi-facility Weber problem

The capacitated multi-facility Weber problem is concerned with locating I capacitated facilities in the plane to satisfy the demand of J customers with the minimum total transportation cost of a single commodity. This is a nonconvex optimization problem and difficult to solve. In this work, we focus on a multi-commodity extension and consider the situation where K distinct commodities are shipped subject to capacity constraints between each customer and facility pair. Customer locations, demands and capacities for each commodity, and bundle restrictions are known a priori. The transportation costs, which are proportional to the distance between customers and facilities, depend on the commodity type. We address several location-allocation and discrete approximation heuristics using different strategies. Based on the obtained computational results we can say that the alternate solution of location and allocation problems is a very efficient strategy; but the discrete approximation has excellent accuracy.     

A method for the numerical solution of some elliptic boundary value problems for a strip

A boundary integral equation for the numerical solution of a class of elliptic boundary value problems for a strip is derived. The equation should be particularly useful for the solution of an important class of problems governed by Laplace's equation and also for the solution of relevant problems in anisotropic thermostatics and elastostatics     

An evolutionary algorithm for multi-criteria inverse optimal value problems using a bilevel optimization model

Given a linear program, a desired optimal objective value, and a set of feasible cost vectors, one needs to determine a cost vector of the linear program such that the corresponding optimal objective value is closest to the desired value. The problem is always known as a standard inverse optimal value problem. When multiple criteria are adopted to determine cost vectors, a multi-criteria inverse optimal value problem arises, which is more general than the standard case. This paper focuses on the algorithmic approach for this class of problems, and develops an evolutionary algorithm based on a dynamic weighted aggregation method. First, the original problem is converted into a bilevel program with multiple upper level objectives, in which the lower level problem is a linear program for each fixed cost vector. In addition, the potential bases of the lower level program are encoded as chromosomes, and the weighted sum of the upper level objectives is taken as a new optimization function, by which some potential nondominated solutions can be generated. In the design of the evolutionary algorithm some specified characteristics of the problem are well utilized, such as the optimality conditions. Some preliminary computational experiments are reported, which demonstrates that the proposed algorithm is efficient and robust.     

A method for numerical solution of a multidimensional convection-diffusion problem

We propose a modification of the additive splitting algorithm to solve the convection-diffusion problem using an efficient finite-difference scheme. The modification decreases the number of data exchanges and their amount during the numerical solution of a system of multidimensional equations. Approximation, stability, and convergence are considered. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 100–107, January–February 2009.     

A multi-dimensional shooting algorithm for the two-facility location–allocation problem with dense demand

We develop an efficient allocation-based solution framework for a class of two-facility location–allocation problems with dense demand data. By formulating the problem as a multi-dimensional boundary value problem, we show that previous results for the discrete demand case can be extended to problems with highly dense demand data. Further, this approach can be generalized to non-convex allocation decisions. This formulation is illustrated for the Euclidean metric case by representing the affine bisector with two points. A specialized multi-dimensional shooting algorithm is presented and illustrated on an example. Comparisons with two alternative methods through a computational study confirm the efficiency of the proposed methodology.     

Developing a multi-objective,multi-item inventory model and three algorithms for its solution

We develop a multi-objective model in a multi-product inventory system.The proposed model is a joint replenishment problem(JRP) that has two objective functions.The first one is minimization of total ordering and inventory holding costs,which is the same objective function as the classic JRP.To increase the applicability of the proposed model,we suppose that transportation cost is independent of time,is not a part of holding cost,and is calculated based on the maximum of stored inventory,as is the case in many real inventory problems.Thus,the second objective function is minimization of total transportation cost.To solve this problem three efficient algorithms are proposed.First,the RAND algorithm,called the best heuristic algorithm for solving the JRP,is modified to be applicable for the proposed problem.A multi-objective genetic algorithm(MOGA) is developed as the second algorithm to solve the problem.Finally,the model is solved by a new algorithm that is a combination of the RAND algorithm and MOGA.The performances of these algorithms are then compared with those of the previous approaches and with each other,and the findings imply their ability in finding Pareto optimal solutions to 3200 randomly produced problems.