An algorithm to solve the proportional network flow problem

The proportional network flow problem is a generalization of the equal flow problem on a generalized network in which the flow on arcs in given sets must all be proportional. This problem appears in several natural contexts, including processing networks and manufacturing networks. This paper describes a transformation on the underlying network that reduces the problem to the equal flow problem; this transformation is used to show that algorithms that solve the equal flow problem can be directly applied to the proportional network flow problem as well, with no increase in asymptotic running time. Additionally, computational results are presented for the proportional network flow problem demonstrating equivalent performance to the same algorithm for the equal flow problem.     

三维种群生态动力系统的参数识别

研究具有反应一扩散现象的三维种群生态动力系统的参数识别问题，依该系统正问题解的性质，建立了参数识别的数学模型；论证了系统正问题解关于待识别参数的连续依赖性与参数识别问题最优解的存在性。     

The delivery man problem on a tree network

This note considers a variant of the traveling salesman problem in which we seek a route that minimizes the total of the vertex arrival times. This problem is called the deliverly man problem. The traveling salesman problem is NP-complete on a general network and trivial on a tree network. The delivery man problem is also NP-complete on a general network but far from trivial on a tree network. Various characteristics of the delivery man problem for tree networks are explored and a pseudo-polynomial time solution algorithm is proposed.This research was sponsored by NSF Grant #ECS-8104647.     

Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

The multilevel generalized assignment problem is a problem of assigning agents to tasks where the agents can perform tasks at more than one efficiency level. A profit is associated with each assignment and the objective of the problem is profit maximization. Two heuristic solution methods are presented for the problem. The heuristics are developed from solution methods for the generalized assignment problem. One method uses a regret minimization approach whilst the other method uses a repair approach on a relaxation of the problem. The heuristics are able to solve moderately large instances of the problem rapidly and effectively. Procedures for deriving an upper bound on the solution of the problem are also described. On larger and harder instances of the problem one heuristic is particularly effective.     

On the role of creative thinking in problem posing

This paper addresses the relationship between creative thinking and problem posing as well as problem posing tasks in mathematics domains. Empirical studies were conducted to investigate on relationships and on tasks. Results of a study on arithmetic problem posing and its replication suggested that fluency is general in verbal creativity and problem posing, but flexibility is specific in problem posing. Further investigations into general mathematical problem posing were also carried out, having each of ninety-six elementary school children of Taiwan completing 18 problem posing test items in the Test on General Problem Posing. Results suggested that a general, rather than specific, problem posing competence exists in children and can be measured by the test.     

Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems

Whether or not the general asymmetric variational inequality problem can be formulated as a differentiable optimization problem has been an open question. This paper gives an affirmative answer to this question. We provide a new optimization problem formulation of the variational inequality problem, and show that its objective function is continuously differentiable whenever the mapping involved in the latter problem is continuously differentiable. We also show that under appropriate assumptions on the latter mapping, any stationary point of the optimization problem is a global optimal solution, and hence solves the variational inequality problem. We discuss descent methods for solving the equivalent optimization problem and comment on systems of nonlinear equations and nonlinear complementarity problems.     

Two-grid finite volume element method for linear and nonlinear elliptic problems

Two-grid finite volume element discretization techniques, based on two linear conforming finite element spaces on one coarse and one fine grid, are presented for the two-dimensional second-order non-selfadjoint and indefinite linear elliptic problems and the two-dimensional second-order nonlinear elliptic problems. With the proposed techniques, solving the non-selfadjoint and indefinite elliptic problem on the fine space is reduced into solving a symmetric and positive definite elliptic problem on the fine space and solving the non-selfadjoint and indefinite elliptic problem on a much smaller space; solving a nonlinear elliptic problem on the fine space is reduced into solving a linear problem on the fine space and solving the nonlinear elliptic problem on a much smaller space. Convergence estimates are derived to justify the efficiency of the proposed two-grid algorithms. A set of numerical examples are presented to confirm the estimates. The work is supported by the National Natural Science Foundation of China (Grant No: 10601045).     

The Steiner Problem on Surfaces of Revolution

While the Steiner problem has been extensively studied in the Euclidean plane, it remains an open problem to solve the Steiner problem on arbitrary non-planar (piecewise smooth) surfaces. We suggest an algorithm for solving the n-point Steiner problem on surfaces of revolution which have a non-decreasing generating function by constructing an isometric framework on a plane endowed with a weighted distance metric, thus propelling a new analytical avenue for studying the Steiner problem on surfaces with non-constant curvature.     

A regularization method for stationary maxwell equations in an inhomogeneous conducting medium

We consider the problem of defining a vector potential of a magnetic field with a nonstandard calibration in an inhomogeneous conducting medium. The problem in question is one with constraints on the right-hand side and on the solution itself. A generalized and regularized statement of this problem without constraints is proposed and substantiated. Such a problem statement is equivalent to the original generalized problem with constraints.     

Recovery of the unknown coefficients in a two-dimensional hyperbolic equation

In this paper, an inverse boundary value problem for a two-dimensional hyperbolic equation with overdetermination conditions is studied. To investigate the solvability of the original problem, we first consider an auxiliary inverse boundary value problem and prove its equivalence to the original problem in a certain sense. We then use the Fourier method to reduce such an equivalent problem to a system of integral equations. Furthermore, we prove the existence and uniqueness theorem for the auxiliary problem by the contraction mappings principle. Based on the equivalency of these problems, the existence and uniqueness theorem for the classical solution of the original inverse problem is proved. Some discussions on the numerical solutions for this inverse problem are presented including some numerical examples.     

Sloshing frequencies

The sloshing problem is a linear eigenvalue problem for a partial differential operator that describes the small lateral oscillations of the free surface of an ideal fluid on a container subject to gravity. We consider two-dimensional problems on regions representing the cross-section of a cylindrical tank or canal. A conformal mapping transforms the sloshing problem on the given region to a weighted eigenvalue problem on a simple region such as a rectangle. The weighted problem can be treated very effectively by the powerful methods of intermediate problems. The strength and versatility of the method is illustrated with a variety of examples.     

Cauchy–Goursat Problem for One-Dimensional Semilinear Wave Equations

We consider the initial-characteristic problem for nonlinear wave equations with positive power nonlinearity source term. Depending on the power of nonlinearity, we investigate the problem on a global existence and blow-up of solutions of initial-characteristic problem. The question on local solvability of the problem is also considered.     

A fuzzy shortest path with the highest reliability

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.     

Boundary conditions of the second-order differential equation and the Riccati equation

The conversion of a second-order linear ordinary differential equation with variable coefficients into a Riccati equation depends on whether the second-order problem is an initial-value or two-point boundary-value problem. The distinction is critical in determining the initial condition for the Riccati equation. If the second-order problem is an initial-value problem, the choice of the Riccati transformation depends on whether a zero initial condition for the function or its derivative is specified. If the problem is a two-point boundary-value problem, special methods must be introduced as described in the paper.     

A Lagrangian relaxation-based heuristic for the vehicle routing with full container load

We address a problem of vehicle routing that arises in picking up and delivering full container load from/to an intermodal terminal. The substantial cost and time savings are expected by efficient linkage between pickup and delivery tasks, if the time of tasks and the suitability of containers for cargo allow. As this problem is NP-hard, we develop a subgradient heuristic based on a Lagrangian relaxation which enables us to identify a near optimal solution. The heuristic consists of two sub-problems: the classical assignment problem and the generalized assignment problem. As generalized assignment problem is also NP-hard, we employ an efficient solution procedure for a bin packing based problem, which replaces the generalized assignment problem. The heuristic procedure is tested on a wide variety of problem examples. The test results demonstrate that the procedure developed here can efficiently solve large instances of the problem.     

The Vehicle Routing-Allocation Problem: A unifying framework

Summary In this paper the Vehicle Routing-Allocation Problem (VRAP) is presented. In VRAP not all customers need be visited by the vehicles. However customers not visited either have to be allocated to some customer on one of the vehicle tours or left isolated. We concentrate our discussion on the Single Vehicle Routing-Allocation Problem (SVRAP). An integer linear programming formulation of SVRAP is presented and we show how SVRAP provides a unifying framework for understanding a number of the papers and problems presented in the literature. Specifically the covering tour problem, the covering salesman problem, the median tour problem, the maximal covering tour problem, the travelling salesman problem, the generalised travelling salesman problem, the selective travelling salesman problem, the prize collecting travelling salesman problem, the maximum covering/shortest path problem, the maximum population/shortest path problem, the shortest covering path problem, the median shortest path problem, the minimum covering/shortest path problem and the hierarchical network design problem are special cases/variants of SVRAP.     

An algorithm for linear least squares problems with equality and nonnegativity constraints

We present a new algorithm for solving a linear least squares problem with linear constraints. These are equality constraint equations and nonnegativity constraints on selected variables. This problem, while appearing to be quite special, is the core problem arising in the solution of the general linearly constrained linear least squares problem. The reduction process of the general problem to the core problem can be done in many ways. We discuss three such techniques.The method employed for solving the core problem is based on combining the equality constraints with differentially weighted least squares equations to form an augmented least squares system. This weighted least squares system, which is equivalent to a penalty function method, is solved with nonnegativity constraints on selected variables.Three types of examples are presented that illustrate applications of the algorithm. The first is rank deficient, constrained least squares curve fitting. The second is concerned with solving linear systems of algebraic equations with Hilbert matrices and bounds on the variables. The third illustrates a constrained curve fitting problem with inconsistent inequality constraints.     

A note on the m-center problem with rectilinear distances

Given n demand points on a plane, the problem we consider is to locate a given number, m, of facilities on the plane so that the maximum of the set of rectilinear distances of each demand point to its nearest facility is minimized. This problem is known as the m-center problem on the plane. A related problem seeks to determine, for a given r, the minimum number of facilities and their locations so as to ensure that every point is within r units of rectilinear distance from its nearest facility. We formulate the latter problem as a problem of covering nodes by cliques of an intersection graph. Certain bounds are established on the size of the problem. An efficient algorithm is provided to generate this set-covering problem. Computational results with this approach are summarized.     

Existence and approximation results for shape optimization problems in rotordynamics

We consider a shape optimization problem in rotordynamics where the mass of a rotor is minimized subject to constraints on the natural frequencies. Our analysis is based on a class of rotors described by a Rayleigh beam model including effects of rotary inertia and gyroscopic moments. The solution of the equation of motion leads to a generalized eigenvalue problem. The governing operators are non-symmetric due to the gyroscopic terms. We prove the existence of solutions for the optimization problem by using the theory of compact operators. For the numerical treatment of the problem a finite element discretization based on a variational formulation is considered. Applying results on spectral approximation of linear operators we prove that the solution of the discretized optimization problem converges towards the solution of the continuous problem if the discretization parameter tends to zero. Finally, a priori estimates for the convergence order of the eigenvalues are presented and illustrated by a numerical example.     

Solving maximum fuzzy clique problem with neural networks and its applications

The maximum clique problem is an important problem in graph theory. Many real-life problems are still being mapped into this problem for their effective solutions. A natural extension of this problem that has emerged very recently in many real-life networks, is its fuzzification. The problem of finding the maximum fuzzy clique has been formalized on fuzzy graphs and subsequently addressed in this paper. It has been shown here that the problem reduces to an unconstrained quadratic 0–1 programming problem. Using a maximum neural network, along with mutation capability of genetic adaptive systems, the reduced problem has been solved. Empirical studies have been done by applying the method on stock flow graphs to identify the collusion set, which contains a group of traders performing unfair trading among themselves. Additionally, it has been applied on a gene co-expression network to find out significant gene modules and on some benchmark graphs.