Multiobjective routing problems

Summary Many network routing problems, particularly where the transportation of hazardous materials is involved, are multiobjective in nature; that is, it is desired to optimise not only physical path length but other features as well. Several such problems are defined here and a general framework for multiobjective routing problems is proposed. The notion of “efficient solution” is defined and it is demonstrated, by means of an example, that a problem may have very many solutions which are efficient. Next, potentially useful solution methods for multiobjective routing problems are discussed with emphasis being placed on the use of shortest/k-shortest path techniques. Finally, some directions for possible further research are indicated. Invited by B. Pelegrin     

A look at a problem in heat transfer

Consideration and careful investigation of a simple physical problem in heat transfer shows that even such a problem may not always have solutions and meaningful solutions exist only under restricted conditions. In other words, not all physical problems are well posed. The analysis given here shows that in many practical problems in fluid mechanics and heat transfer the question ‘how well posed is it?’ is non-trivial.     

Slowly Varying Phase Planes and Boundary-Layer Theory

A method is presented that combines phase-plane techniques with the ideas of multiple scale and matched asymptotic expansions to explain the behavior of solutions to second-order, nonlinear, nonautonomous, singular boundary-value problems. It is shown that if one is willing to give up the detailed information provided by a procedure such as matched asymptotic expansions, then complete qualitative information can be obtained by the much simpler method given here. (“Complete” here means that the method provides a way of categorizing all possible solutions of such problems.) In addition, the similarities and differences between the present method and that of Melnikov, which has been useful in the study of dynamical systems, are noted.     

The Numerical Solution of Two-parameter Eigenvalue Problems in Ordinary Differential Equations with an Application to the Problem of Diffraction by a Plane Angular Sector

In this paper we are concerned with the numerical solution ofSturm–Liouville eigenvalue problems associated with asystem of two second order linear ordinary differential equationscontaining two spectral parameters. Such problems are of importancein applied mathematics and frequently arise in solving boundaryvalue problems for the Helmholtz equation or Laplace's equationby the method of separation of variables. The numerical methodproposed here is a departure from the usual techniques of solvingeigenvalue problems associated with ordinary differential equationsand appears capable of considerable generalization. Briefly,the idea is to replace the given problem by a related initialboundary value problem and then to use the powerful numericaltechniques currently available for such problems. The techniquedeveloped is illustrated in application to the important problemof diffraction by a plane angular sector. It appears that, intheory, the method described here is capable of generalizationto systems of ordinary differential equations containing morethan two spectral parameters.     

The Sinc-Galerkin method for parameter-dependent self-adjoint problems

The Sinc-Galerkin method is being applied to a growing number of diverse problems in ordinary and partial differential equations including both forward and inverse (parameter recovery) problems. As a result of these continuing extensions, the treatment of parameter-dependent problems needs to be thoroughly investigated. Two specific questions considered here are the incorporation of various nonhomogeneous boundary conditions and the treatment of a variable parameter. The latter topic is particularly important for inverse problems that arise when numerically estimating physical parameters. The point of view taken emphasizes the maintenance of the classical exponential convergence rate. The techniques described are suitable both for the direct problem and for the parameter estimation problem. Numerical results are presented to substantiate the accuracy of the method.     

An analytical contour integration method for handling body forces in elasticity

In the boundary element and superposition methods for two-dimensional elasticity problems, the presence of body forces requires the integration of the basic point load solution against the body force field over a specified area. For polynomial body forces, x^myⁿ, these area integrals may be transformed into contour integrals which have closed form analytic representations when the area is a polygon. This paper shows that commonly used numerical integration techniques developed for area integrals are unsuitable for handling body forces using the above named methods. Not only are these techniques inaccurate but expensive in terms of execution time in comparison to the analytical algorithm developed here. A computer program and four example problems are included.     

Warfield rings

Of concern here are rings over which every finitely presented right module is isomorphic to a direct summand of a direct sum of cyclic, finitely presented, right modules (right Warfield rings). Using model-theoretic techniques, we obtain several simple characterizations, thus answering the well-known question of Warfield. Some ways of applying the results obtained to category problems are indicated.Translated fromAlgebra i Logika, Vol. 33, No. 3, pp. 264–285, May–June, 1994.Supported by the Soros Foundation.     

Series solution of nonlinear eigenvalue problems by means of the homotopy analysis method

A general analytic approach for nonlinear eigenvalue problems is described. Two physical problems are used as examples to show the validity of this approach for eigenvalue problems with either periodic or non-periodic eigenfunctions. Unlike perturbation techniques, this approach is independent of any small physical parameters. Besides, different from all other analytic techniques, it provides a simple way to ensure the convergence of series of eigenvalues and eigenfunctions so that one can always get accurate enough approximations. Finally, unlike all other analytic techniques, this approach provides great freedom to choose an auxiliary linear operator so as to approximate the eigenfunction more effectively by means of better base functions. This approach provides us a new way to investigate eigenvalue problems with strong nonlinearity.     

Difference and differential equations in the mathematics of finance

Many problems arising in the mathematics of finance involve identical money flows at regular time intervals and are typically solved by appropriate valuation at a focal date or by setting up an equation of value. It is shown here that such problems can be viewed as special cases of a certain class of first‐order difference equations. Problems relating to continuous money flows can be viewed analogously as special cases of a certain class of ordinary first‐order differential equations. Students should thus be encouraged to view the concepts and techniques of the mathematics of finance as not being inherently different from those prevalent in more traditional applied mathematics.     

The efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results

First, this paper presents the results of experiments with algorithmic techniques for efficiently solving medium and large scale linear and mixed integer programming problems. The techniques presented here are either original or recent.The solution of a great number of problems has shown that efficient problem solving requires automatic adaptation of algorithmic techniques upon problem characteristics. We show when a given technique should be used for a particular problem.The last part of this paper describes an attempt to provide a powerful mathematical programming language, allowing an easy programming of specific studies on medium-size models such as the recursive use of LP or the build-up of algorithms based on the simplex method.All these features have been implemented in the IBM Mathematical Programming System, MPSX/370, and its feature MIP/370. Extensive numerical results and comparisons on real-life problems are provided and commented upon.Presented at the IXth International Symposium on Mathematical Programming in Budapest (1976).     

ABS methods for continuous and integer linear equations and optimization

ABS methods are a large class of algorithms for solving continuous and integer linear algebraic equations, and nonlinear continuous algebraic equations, with applications to optimization. Recent work by Chinese researchers led by Zunquan Xia has extended these methods also to stochastic, fuzzy and infinite systems, extensions not considered here. The work on ABS methods began almost thirty years. It involved an international collaboration of mathematicians especially from Hungary, England, China and Iran, coordinated by the university of Bergamo. The ABS method are based on the rank reducing matrix update due to Egerváry and can be considered as the most fruitful extension of such technique. They have led to unification of classes of methods for several problems. Moreover they have produced some special algorithms with better complexity than the standard methods. For the linear integer case they have provided the most general polynomial time class of algorithms so far known; such algorithms have been extended to other integer problems, as linear inequalities and LP problems, in over a dozen papers written by Iranian mathematicians led by Nezam Mahdavi-Amiri. ABS methods can be implemented generally in a stable way, techniques existing to enhance their accuracy. Extensive numerical experiments have shown that they can outperform standard methods in several problems. Here we provide a review of their main properties, for linear systems and optimization. We also give the results of numerical experiments on some linear systems. This paper is dedicated to Professor Egerváry, developer of the rank reducing matrix update, that led to ABS methods.     

Multivariate Gaussians,semidefinite matrix completion,and convex algebraic geometry

We study multivariate normal models that are described by linear constraints on the inverse of the covariance matrix. Maximum likelihood estimation for such models leads to the problem of maximizing the determinant function over a spectrahedron, and to the problem of characterizing the image of the positive definite cone under an arbitrary linear projection. These problems at the interface of statistics and optimization are here examined from the perspective of convex algebraic geometry.     

Maximal flow network modelling of production bottleneck problems

This paper considers the analysis of process networks with bottlenecks and shows how they may be regarded as simple multi-source maximal flow linear programming problems. We surveyed over 30 Production/Operations Management and management science/OR textbooks, finding that only iterative trial-and-error procedures are now being suggested for this kind of analysis. The maximal flow network approach is easier for complex problems and also allows several advantages not available in the trial-and-error approaches. This paper also discusses the use of a simple linear programming sensitivity result called radial change. The modelling approach suggested here can provide new ideas for improving system capacity following the application of Theory of Constraints techniques.     

A Formulation for Water Waves over Topography

Many interesting free-surface flow problems involve a varying bottom. Examples of such flows include ocean waves propagating over topography, the breaking of waves on a beach, and the free surface of a uniform flow over a localized bump. We present here a formulation for such flows that is general and, from the outset, demonstrates the wave character of the free-surface evolution. The evolution of the free surface is governed by a system of equations consisting of a nonlinear wave-like partial differential equation coupled to a time-independent linear integral equation. We assume that the free-surface deformation is weakly nonlinear, but make no a priori assumption about the scale or amplitude of the topography. We also extend the formulation to include the effect of mean flows and surface tension. We show how this formulation gives some of the well-known limits for such problems once assumptions about the amplitude and scale of the topography are made.     

Structure evaluation of materials by electrical methods

A theoretical and practical framework of different problems has been discussed to explain advantages and limitations of techniques based on electrical sensing methods which are consistent to implement structure evaluation of materials. The term structure evaluation is generally used here to mean extracting the quantitative information of interest of a material or an object to be examined from a physical measurement, or more typically from a set of physical measurements, that themselves may be only indirectly related to the quantitative information desired. The paper emphasizes the point that the structure evaluation is a typical inverse problem and as such is made more difficult, since inverse problems are characteristically illconditioned, that is, small errors in the measurement typically lead to large errors in the solution. Use of physically motivated a priori information to diminishing such ill-conditioning is discussed. Features of updated electrical sensing methods, particularly those used for nondestructive testing (NDT) are considered. Potential advantages of the electrical methods compared to other NDT techniques are that they offer inexpensive, safe, nonharmful, and fast testing. Some novel achievements including excitation with a number of complex electric field excitation patterns on the object together with computer-assisted information acquisition have considerably extended both the potential and the scope of the electrical methods which will still be recognized. In order to present an up-to-date perspective, some conceptual and methodologic aspects have been considered for two structure evaluation problems, i.e., for generating a) algorithms for determining structural parameters of materials, such as density, moisture content, polymerization degree, etc., from dielectric spectra; b) tomographic cross-sectional maps of electrical parameters of the object to be examined.Presented at the Ninth International Conference on the Mechanics of Composite Materials, Riga, October, 1995.Institute of Polymer Mechanics, Riga, Latvia. Published in Mekhanika Kompozitnykh Materialov, No. 1, pp. 124–134, January–February, 1996.     

美式期权定价中非局部问题的有限元方法

在本文中 ,我们关心的是美式期权的有限元方法 .首先 ,根据 [4 ]我们对所讨论的问题引进一个新奇的实用的方法 ,它涉及到对原问题重新形成准确的数学公式 ,使得数值解的计算可以在非常小的区域上进行 ,从而该算法计算速度快精度高 .进而 ,我们利用超逼近分析技术得到了有限元解关于 L2 -模的最优估计 .     

On Tensor Completion via Nuclear Norm Minimization

Many problems can be formulated as recovering a low-rank tensor. Although an increasingly common task, tensor recovery remains a challenging problem because of the delicacy associated with the decomposition of higher-order tensors. To overcome these difficulties, existing approaches often proceed by unfolding tensors into matrices and then apply techniques for matrix completion. We show here that such matricization fails to exploit the tensor structure and may lead to suboptimal procedure. More specifically, we investigate a convex optimization approach to tensor completion by directly minimizing a tensor nuclear norm and prove that this leads to an improved sample size requirement. To establish our results, we develop a series of algebraic and probabilistic techniques such as characterization of subdifferential for tensor nuclear norm and concentration inequalities for tensor martingales, which may be of independent interests and could be useful in other tensor-related problems.     

Determination of a control parameter in a one-dimensional parabolic equation using the method of radial basis functions

In this work, the method of radial basis functions is used for finding the solution of an inverse problem with source control parameter. Because a much wider range of physical phenomena are modelled by nonclassical parabolic initial-boundary value problems, theoretical behavior and numerical approximation of these problems have been active areas of research. The radial basis functions (RBF) method is an efficient mesh free technique for the numerical solution of partial differential equations. The main advantage of numerical methods which use radial basis functions over traditional techniques is the meshless property of these methods. In a meshless method, a set of scattered nodes are used instead of meshing the domain of the problem. The results of numerical experiments are presented and some comparisons are made with several well-known finite difference schemes.     

Discrete Variational Calculus for B-Spline Curves

In this work, we study discrete variational problems, for B-spline curves, which are invariant under translation and rotation. We show this approach has advantages over studying smooth variational problems whose solutions are approximated by B-spline curves. The latter method has been well studied in the literature but leads to high order approximation problems. We are particularly interested in Lagrangians that are invariant under the special Euclidean group for which B-spline approximated curves are well suited. The main application we present here is the curve completion problem in 2D and 3D. Here, the aim is to find various aesthetically pleasing solutions as opposed to a solution of a physical problem. Smooth Lagrangians with special Euclidean symmetries involve curvature, torsion, and arc length. Expressions of these, in the original coordinates, are highly complex. We show that, by contrast, relatively simple discrete Lagrangians offer excellent results for the curve completion problem. The novel methods we develop for the discrete curve completion problem are general, and can be used to solve other discrete variational problems for B-spline curves. Our method completely avoids the difficulties of high order smooth differential invariants.     

On the solution of an initial‐boundary value problem that combines Neumann and integral condition for the wave equation

Numerical solution of hyperbolic partial differential equation with an integral condition continues to be a major research area with widespread applications in modern physics and technology. Many physical phenomena are modeled by nonclassical hyperbolic boundary value problems with nonlocal boundary conditions. In place of the classical specification of boundary data, we impose a nonlocal boundary condition. Partial differential equations with nonlocal boundary specifications have received much attention in last 20 years. However, most of the articles were directed to the second‐order parabolic equation, particularly to heat conduction equation. We will deal here with new type of nonlocal boundary value problem that is the solution of hyperbolic partial differential equations with nonlocal boundary specifications. These nonlocal conditions arise mainly when the data on the boundary can not be measured directly. Several finite difference methods have been proposed for the numerical solution of this one‐dimensional nonclassic boundary value problem. These computational techniques are compared using the largest error terms in the resulting modified equivalent partial differential equation. Numerical results supporting theoretical expectations are given. Restrictions on using higher order computational techniques for the studied problem are discussed. Suitable references on various physical applications and the theoretical aspects of solutions are introduced at the end of this article. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005