Algorithms for flows with parametric capacities

We consider the problem of finding maximal flows with respect to capacities which are linear functions of a parametert [0,T]. Since this problem is a special case of a parametric linear program the classichorizontal approach can be applied in which optimal solutions are computed for successive subintervals of [0,T]. We discuss an alternative algorithm which approximates in each iteration the optimal solution for allt [0,T]. Thisvertical algorithm is a labeling type algorithm where the flow variables are piecewise linear functions. Flow augmentations are done alongconditional flow augmenting paths which can be found by modified path algorithms. The vertical algorithm can be used to solve the parametric flow problem optimally as well as to compute a good approximation for allt if the computation of the optimal solution turns out to be too time consuming.Partially supported by NSF Grants ECS-8412926 and INT-8521433, and NATO Grant RG 85/0240.     

Linear independence of root equations forM/G/1 type Markov chains

There is a classical technique for determining the equilibrium probabilities ofM/G/1 type Markov chains. After transforming the equilibrium balance equations of the chain, one obtains an equivalent system of equations in analytic functions to be solved. This method requires finding all singularities of a given matrix function in the unit disk and then using them to obtain a set of linear equations in the finite number of unknown boundary probabilities. The remaining probabilities and other measures of interest are then computed from the boundary probabilities. Under certain technical assumptions, the linear independence of the resulting equations is established by a direct argument involving only elementary results from matrix theory and complex analysis. Simple conditions for the ergodicity and nonergodicity of the chain are also given.     

An Effective Decomposition Procedure for Computing Equilibrium Single Commodity Trade Flows

The objective is to compute equilibrium interregional trade flows in relation to approximately linear supply and demand curves for a single commodity. There are n regions on a network characterized by approximately linear interregional transportation costs. Quadratic programming approaches can be greatly simplified by exploiting the special structure of the problem. This paper shows how the reduced quadratic program can then be partitioned using Benders decomposition. The computation then involves solving relatively small transportation problems and quadratic programming problems. Numerical experiments show the method to be effective in reducing computational requirements.     

Spatial price equilibrium,distribution center location and successive over-relaxation

A spatial price equilibrium problem is modeled which allows piecewise linear convex flow costs, and a capacity limit on the trade flow between each supply/demand pair of regions. Alternatively, the model determines the locations of intermediate distribution centers in a market economy composed of separate regions, each with approximately linear supply and demand functions. Equilibrium prices, regional supply and demand quantities, and commodity flows are determined endogenously. The model has a quadratic programming formulation which is then reduced by exploiting the structure. The reduced model is particularly well suited to solution using successive over-relaxation.     

Algorithms for multiplayer multicommodity flow problems

We investigate the multiplayer multicommodity flow problem: several players have different networks and commodities over a common node set. Pairs of players have contracts where one of them agrees to route the flow of the other player (up to a given capacity) between two specified nodes. In return, the second player pays an amount proportional to the flow value. We show that the social optimum can be computed by linear programming, and we propose algorithms based on column generation and Lagrangian relaxation. In contrast, we prove that it is hard to decide if an equilibrium solution exists, although some natural conditions guarantee its existence.     

Generalized Dirichlet‐to‐Neumann Map in Time‐Dependent Domains

We study the heat, linear Schrödinger (LS), and linear KdV equations in the domain l(t) < x < ∞ , 0 < t < T , with prescribed initial and boundary conditions and with l(t) a given differentiable function. For the first two equations, we show that the unknown Neumann or Dirichlet boundary value can be computed as the solution of a linear Volterra integral equation with an explicit weakly singular kernel. This integral equation can be derived from the formal Fourier integral representation of the solution. For the linear KdV equation we show that the two unknown boundary values can be computed as the solution of a system of linear Volterra integral equations with explicit weakly singular kernels. The derivation in this case makes crucial use of analyticity and certain invariance properties in the complex spectral plane. The above Volterra equations are shown to admit a unique solution.     

Exchange rate uncertainty and trade growth—a comparison of linear and non‐linear (forecasting) models

A huge body of empirical and theoretical literature has emerged on the relationship between foreign exchange (FX) uncertainty and international trade. Empirical findings about the impact of FX uncertainty on trade figures are at best weak and often ambiguous with respect to its direction. Almost all empirical contributions assume and estimate a linear relationship. Possible nonlinearity or state dependence of causal links between FX uncertainty and trade has been mostly ignored yet. In addition, widely used regression models have not been evaluated in terms of ex‐ante forecasting. In this paper we analyse the impact of FX uncertainty on sectoral categories of multilateral exports and imports for 15 industrialized economies. We particularly provide a comparison of linear and non‐linear models with respect to ex‐ante forecasting. In terms of average ranks of absolute forecast errors non‐linear models outperform both, a common linear model and some specification building on the assumption that FX uncertainty and trade growth are uncorrelated. Our results support the view that the relationship of interest might be non‐linear and, moreover, lacks of homogeneity across countries, economic sectors and when contrasting imports vs exports. Copyright © 2005 John Wiley & Sons, Ltd.     

An algorithm based on a sequence of linear complementarity problems applied to a walrasian equilibrium model: An example

The Walrasian equilibrium problem is cast as a complementarity problem, and its solution is computed by solving a sequence of linear complementarity problems (SLCP). Earlier numerical experiments have demonstrated the computational efficiency of this approach. So far, however, there exist few relevant theoretical results that characterize the performance of this algorithm. In the context of a simple example of a Walrasian equilibrium model, we study the iterates of the SLCP algorithm. We show that a particular LCP of this process may have no, one or more complementary solutions. Other LCPs may have both homogeneous and complementary solutions. These features complicate the proof of convergence for the general case. For this particular example, however, we are able to show that Lemke's algorithm computes a solution to an LCP if one exists,and that the iterative process converges globally.     

Global behavior and permanence of SIRS epidemic model with time delay

In this paper an autonomous SIRS epidemic model with time delay is studied. The basic reproductive number R₀ is obtained which determines whether the disease is extinct or not. When the basic reproductive number is greater than 1, it is proved that the disease is permanent in the population, and explicit formula are obtained by which the eventual lower bound of the fraction of infectious individuals can be computed. Throughout the total paper, we mainly use the technique of Lyapunov functional to establish the global stability of the infection-free equilibrium and the local stability of the endemic equilibrium but need another sufficient condition.     

Simulation of shallow water flows with shoaling areas and bottom discontinuities

A numerical method based on a second-order accurate Godunov-type scheme is described for solving the shallow water equations on unstructured triangular-quadrilateral meshes. The bottom surface is represented by a piecewise linear approximation with discontinuities, and a new approximate Riemann solver is used to treat the bottom jump. Flows with a dry sloping bottom are computed using a simplified method that admits negative depths and preserves the liquid mass and the equilibrium state. The accuracy and performance of the approach proposed for shallow water flow simulation are illustrated by computing one- and two-dimensional problems.     

Self-adaptive projection-based prediction-correction method for constrained variational inequalities

The problems studied in this paper are a class of monotone constrained variational inequalities VI (S, f) in which S is a convex set with some linear constraints. By introducing Lagrangian multipliers to the linear constraints, such problems can be solved by some projection type prediction-correction methods. We focus on the mapping f that does not have an explicit form. Therefore, only its function values can be employed in the numerical methods. The number of iterations is significantly dependent on a parameter that balances the primal and dual variables. To overcome potential difficulties, we present a self-adaptive prediction-correction method that adjusts the scalar parameter automatically. Convergence of the proposed method is proved under mild conditions. Preliminary numerical experiments including some traffic equilibrium problems indicate the effectiveness of the proposed methods.     

Optimal design of a manpower system

An equilibrium model of a manpower system is developed based on the notion of a career flow. Institutional constraints and measures of system performance are linear functions of the career flow. A typical optimal design problem is formulated and a solution procedure is developed. The optimization problem is a generalized linear program in which columns are generated by solving a shortest path problem. Upper and lower bounds on the optimal value function can be developed at each stage of the calculations.This research was supported by ONR grant N00014-75-C-0619.     

Obtaining a banded system of equations in complete spline interpolation problem via B-spline basis

We study the problem of interpolation by a complete spline of 2n − 1 degree given in B-spline representation. Explicit formulas for the first nand the last ncoefficients of B-spline decomposition are found. It is shown that other B-spline coefficients can be computed as a solution of a banded system of an equitype linear equations.     

Component-wise perturbation analysis and error bounds for linear least squares solutions

Perturbation bounds for the linear least squares problem min _x Ax –b₂ corresponding tocomponent-wise perturbations in the data are derived. These bounds can be computed using a method of Hager and are often much better than the bounds derived from the standard perturbation analysis. In particular this is true for problems where the rows ofA are of widely different magnitudes. Generalizing a result by Oettli and Prager, we can use the bounds to compute a posteriori error bounds for computed least squares solutions.     

A note on the efficiency of the conjugate gradient method for a class of time‐dependent problems

We discuss the efficiency of the conjugate gradient (CG) method for solving a sequence of linear systems; Auⁿ⁺¹ = uⁿ, where A is assumed to be sparse, symmetric, and positive definite. We show that under certain conditions the Krylov subspace, which is generated when solving the first linear system Au¹ = u⁰, contains the solutions {uⁿ} for subsequent time steps. The solutions of these equations can therefore be computed by a straightforward projection of the right‐hand side onto the already computed Krylov subspace. Our theoretical considerations are illustrated by numerical experiments that compare this method with the order‐optimal scheme obtained by applying the multigrid method as a preconditioner for the CG‐method at each time step. Copyright © 2007 John Wiley & Sons, Ltd.     

Decomposition and Dynamic Cut Generation in Integer Linear Programming

Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen an initial linear programming relaxation. Recently, a number of authors have proposed methods for integrating dynamic cut generation with various decomposition methods to yield further improvement in computed bounds. In this paper, we describe a framework within which most of these methods can be viewed from a common theoretical perspective. We then discuss how the framework can be extended to obtain a decomposition-based separation technique we call decompose and cut. As a by-product, we describe how these methods can take advantage of the fact that solutions with known structure, such as those to a given relaxation, can frequently be separated much more easily than arbitrary real vectors.     

Convergence of Solutions of Nonhomogeneous Linear Difference Systems with Delays

Sufficient conditions are given for the asymptotic constancy of the solutions of a linear system of difference equations with delays. Moreover, it is shown that the limits of the solutions, as t→∞, can be computed in terms of the initial function and a special matrix solution of the corresponding adjoint equation.     

A note onK best network flows

It is shown that the problem of finding theK best solutions of a linear integer network flow problem can be solved by a polynomial time algorithm. This algorithm can be used in order to solve a multiple-criteria network flow problem which minimizes the maximum ofQ objectives.Partially supported by grants of the Deutsche Forschungsgemeinschaft and the HC&M programme of the European Union under ERBCHRXCT 930087.     

High-order Gauss–Lobatto formulae

Currently, the method of choice for computing the (n+2)-point Gauss–Lobatto quadrature rule for any measure of integration is to first generate the Jacobi matrix of order n+2 for the measure at hand, then modify the three elements at the right lower corner of the matrix in a manner proposed in 1973 by Golub, and finally compute the eigenvalues and first components of the respective eigenvectors to produce the nodes and weights of the quadrature rule. In general, this works quite well, but when n becomes large, underflow problems cause the method to fail, at least in the software implementation provided by us in 1994. The reason is the singularity (caused by underflow) of the 2×2 system of linear equations that is used to compute the modified matrix elements. It is shown here that in the case of arbitrary Jacobi measures, these elements can be computed directly, without solving a linear system, thus allowing the method to function for essentially unrestricted values of n. In addition, it is shown that all weights of the quadrature rule can also be computed explicitly, which not only obviates the need to compute eigenvectors, but also provides better accuracy. Numerical comparisons are made to illustrate the effectiveness of this new implementation of the method.     

简单网络流对策的相对N-核

主要研究简单网络流对策中相对N-核的算法.当网络中最大流值等于1时,证明相对N-核与对策的核心相同,不一定是单点集;而当网络中最大流值大于1时,利用Kopelowitz's序列线性规划方法和线性规划对偶理论,证明相对N-核与N-核相同(同为单点集),并且可在局中人个数的多项式时间内得到求解.