The relax codes for linear minimum cost network flow problems

We describe a relaxation algorithm [1,2] for solving the classical minimum cost network flow problem. Our implementation is compared with mature state-of-the-art primal simplex and primal-dual codes and is found to be several times faster on all types of randomly generated network flow problems. Furthermore, the speed-up factor increases with problem dimension. The codes, called RELAX-II and RELAXT-II, have a facility for efficient reoptimization and sensitivity analysis, and are in the public domain.This work has been supported by the National Science Foundation under Grant NSF-ECS-8217668.     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

A computational comparison of the dinic and network simplex methods for maximum flow

We study the implementation of two fundamentally different algorithms for solving the maximum flow problem: Dinic's method and the network simplex method. For the former, we present the design of a storage-efficient implementation. For the latter, we develop a "steepest-edge" pivot selection criterion that is easy to include in an existing network simplex implementation. We compare the computational efficiency of these two methods on a personal computer with a set of generated problems of up to 4 600 nodes and 27 000 arcs.This research was supported in part by the National Science Foundation under Grant Nos. MCS-8113503 and DMS-8512277.     

An algorithm for optimizing network flow capacity under economies of scale

The problem of optimally allocating a fixed budget to the various arcs of a single-source, single-sink network for the purpose of maximizing network flow capacity is considered. The initial vector of arc capacities is given, and the cost function, associated with each arc, for incrementing capacity is concave; therefore, the feasible region is nonconvex. The problem is approached by Benders' decomposition procedure, and a finite algorithm is developed for solving the nonconvex relaxed master problems. A numerical example of optimizing network flow capacity, under economies of scale, is included.This research was supported by the National Science Foundation, Grant No. GK-32791.     

Affine minorants minimizing the sum of convex functions

It is often possible to replace a convex minimization problem by an equivalent one, in which each of the original convex functions is replaced by a suitably chosen affine minorant. In this paper we identify essentially the minimal conditions permitting this replacement, and also shed light on the close and complete link between such optimal affine minorants and certain optimal dual vectors. An application to the ordinary convex programming problem is included.This research was supported in part by the National Science Foundation, Grant No. MPS75-08025, at the University of Illinois at Urbana-Champaign.     

An Additive Problem with Primes in Arithmetic Progressions

In this paper, we extend a classical result of Hua to arithmetic progressions with large moduli. The result implies the Linnik Theorem on the least prime in an arithmetic progression.     

The Existence of a Positive Solution of D α[x(t) − x(0)] = x(t)f(t,x t )

This paper is devoted to the problem of existence of positive solution for a delay differential equation with fractional order. Some sufficient conditions for its existence of positive solution are given. This work was supported in part by the Key Project of the National Nature Science Foundation of China (No. 60534020), the National Nature Science Foundation of China (No. 60474037), and Program for New Century Excellent Talents in University (No. NCET-04-415).     

A unified framework for primal-dual methods in minimum cost network flow problems

We introduce a broad class of algorithms for finding a minimum cost flow in a capacitated network. The algorithms are of the primal-dual type. They maintain primal feasibility with respect to capacity constraints, while trying to satisfy the conservation of flow equation at each node by means of a wide variety of procedures based on flow augmentation, price adjustment, and ascent of a dual functional. The manner in which these procedures are combined is flexible thereby allowing the construction of algorithms that can be tailored to the problem at hand for maximum effectiveness. Particular attention is given to methods that incorporate features from classical relaxation procedures. Experimental codes based on these methods outperform by a substantial margin the fastest available primal-dual and primal simplex codes on standard benchmark problems.This work was supported by the National Science Foundation under Contract NSF/ECS 8217668.     

Convergence of one-leg methods for nonlinear neutral delay integro-differential equations

Some convergence results of one-leg methods for nonlinear neutral delay integro-differential equations (NDIDEs) are obtained. It is proved that a one-leg method is E (or EB) -convergent of order p for nonlinear NDIDEs if and only if it is A-stable and consistent of order p in classical sense for ODEs, where p = 1, 2. A numerical example that confirms the theoretical results is given in the end of this paper. This work was supported by National Natural Science Foundation of China (Grant No. 10871164), the Natural Science Foundation of Hunan Province (Grant No. 08JJ6002), and the Scientific Research Fund of Changsha University of Science and Technology (Grant No. 1004259)     

A level set method to reconstruct the discontinuity of the conductivity in EIT

In this paper, one level set method is applied to finding the interface of discontinuity of the conductivity in EIT(electrical impedance tomography) problem. By choosing one suitable velocity function, a level set reconstruction algorithm is proposed. The theoretical results for EIT problem and regularization are given. Finally the numerical examples demonstrate that the reconstruction algorithm is efficient and stable. The work was supported by the National Natural Science Foundation of China (Grant Nos. 10431030, 10771138), the Shanghai Natural Science Foundation (Grant No. 07JC14001), the National Basic Research Program (Grant No. 2005CB321701) and Ministry of Education of China and State Administration of Foreign Experts Affairs of China under an 111 project (Grant No. B08018).     

Scheduling in a multi-class series of queues with deterministic service times

We consider a problem of scheduling in a multi-class network of single-server queues in series, in which service times at the nodes are constant and equal. Such a model has potential application to automated manufacturing systems or packet-switched communication networks, where a message is divided into packets (or cells) of fixed lengths. The network is a series-type assembly or transfer line, with the exception that there is an additional class of jobs that requires processing only at the first node (class 0). There is a holding cost per unit time that is proportional to the total number of customers in the system. The objective is to minimize the (expected) total discounted holding cost over a finite or an infinite horizon. We show that an optimal policy gives priority to class-0 jobs at node 1 when at least one of a set ofm–1 inequalities on partial sums of the components of the state vector is satisfied. We solve the problem by two methods. The first involves formulating the problem as a (discrete-time) Markov decision process and using induction on the horizon length. The second is a sample-path approach using an interchange argument to establish optimality.The research of this author was supported by the National Science Foundation under Grant No. DDM-8719825. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.     

Exact self-similar solutions of the magnetohydrodynamic boundary layer system for power-law fluids

In a particular self-similar case, the magnetohydrodynamic boundary layer system for an electrically conducting power-law fluid together with certain boundary conditions can be transformed into a boundary value problem for a third-order nonlinear ordinary differential equation, only whose (generalized) normal solutions possess the physical meaning of the original problem. Uniqueness, existence and nonexistence results are established for the problem. Representations are also given for all (generalized) normal solutions. The project was supported by the Natural Science Foundation of Fujian Province of China (No. Z0511005) and NNSF of china(No. 10501037).     

On Singular Sets of Local Solutions to p-Laplace Equations

The author proves that the on the singular set of a local solution to existence of an optimal control problem. right-hand term of a p-Laplace equation is zero the equation. Such a result is used to study the     

A specialized network simplex algorithm for the constrained maximum flow problem

The constrained maximum flow problem is to send the maximum flow from a source to a sink in a directed capacitated network where each arc has a cost and the total cost of the flow cannot exceed a budget. This problem is similar to some variants of classical problems such as the constrained shortest path problem, constrained transportation problem, or constrained assignment problem, all of which have important applications in practice. The constrained maximum flow problem itself has important applications, such as in logistics, telecommunications and computer networks. In this research, we present an efficient specialized network simplex algorithm that significantly outperforms the two widely used LP solvers: CPLEX and lp_solve. We report CPU times of an average of 27 times faster than CPLEX (with its dual simplex algorithm), the closest competitor of our algorithm.     

Global Error Bound for the Generalized Linear Complementarity Problem over a Polyhedral Cone

In this paper, the global error bound estimation for the generalized linear complementarity problem over a polyhedral cone (GLCP) is considered. To obtain a global error bound for the GLCP, we first develop some equivalent reformulations of the problem under milder conditions and then characterize the solution set of the GLCP. Based on this, an easily computable global error bound for the GLCP is established. The results obtained in this paper can be taken as an extension of the existing global error bound for the classical linear complementarity problems. This work was supported by the Research Grant Council of Hong Kong, a Chair Professor Fund of The Hong Kong Polytechnic University, the Natural Science Foundation of China (Grant No. 10771120) and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

Consistency and asymptotic normality of profilekernel and backfitting estimators in semiparametric reproductive dispersion nonlinear models

Semiparametric reproductive dispersion nonlinear model (SRDNM) is an extension of nonlinear reproductive dispersion models and semiparametric nonlinear regression models, and includes semiparametric nonlinear model and semiparametric generalized linear model as its special cases. Based on the local kernel estimate of nonparametric component, profile-kernel and backfitting estimators of parameters of interest are proposed in SRDNM, and theoretical comparison of both estimators is also investigated in this paper. Under some regularity conditions, strong consistency and asymptotic normality of two estimators are proved. It is shown that the backfitting method produces a larger asymptotic variance than that for the profile-kernel method. A simulation study and a real example are used to illustrate the proposed methodologies. This work was supported by National Natural Science Foundation of China (Grant Nos. 10561008, 10761011), Natural Science Foundation of Department of Education of Zhejiang Province (Grant No. Y200805073), PhD Special Scientific Research Foundation of Chinese University (Grant No. 20060673002) and Program for New Century Excellent Talents in University (Grant No. NCET-07-0737)     

Necessary conditions for optimality of singular controls in systems governed by partial differential equations

In this paper, we present a method to obtain necessary conditions for optimality of singular controls in systems governed by partial differential equations (distributed-parameter systems). The method is based on the one developed earlier by the author for singular control problems described by ordinary differential equations. As applications, we consider conditions for optimality of singular controls in a Darboux-Goursat system and in control systems that describe chemical processes.This research was supported in part by the National Science Foundation under Grant No. NSF-MCS-80-02337 at the University of Michigan.The author wishes to express his deep gratitude to Professor L. Cesari for his valuable guidance and constant encouragement during the preparation of this paper.     

A note on an open problem about the first Painlevé equation

In this note, we apply numerical analysis to the first equation, find the conditions for it to have oscillating solutions and therefore solve an open problem posed by Peter A. Clarkson.     

A Sequential Quadratically Constrained Quadratic Programming Method of Feasible Directions

In this paper, a sequential quadratically constrained quadratic programming method of feasible directions is proposed for the optimization problems with nonlinear inequality constraints. At each iteration of the proposed algorithm, a feasible direction of descent is obtained by solving only one subproblem which consist of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the functions of the discussed problems, and such a subproblem can be formulated as a second-order cone programming which can be solved by interior point methods. To overcome the Maratos effect, an efficient higher-order correction direction is obtained by only one explicit computation formula. The algorithm is proved to be globally convergent and superlinearly convergent under some mild conditions without the strict complementarity. Finally, some preliminary numerical results are reported. Project supported by the National Natural Science Foundation (No. 10261001), Guangxi Science Foundation (Nos. 0236001, 064001), and Guangxi University Key Program for Science and Technology Research (No. 2005ZD02) of China.     

Global superconvergence of finite element methods for parabolic inverse problems

In this article we transform a large class of parabolic inverse problems into a nonclassical parabolic equation whose coefficients consist of trace type functionals of the solution and its derivatives subject to some initial and boundary conditions. For this nonclassical problem, we study finite element methods and present an immediate analysis for global superconvergence for these problems, on basis of which we obtain a posteriori error estimators. This research was supported in part by the Shahid Beheshti University, the National Basic Research Program of China (2007CB814906), the National Natural Science Foundation of China (10471103 and 10771158), Social Science Foundation of the Ministry of Education of China (Numerical methods for convertible bonds, 06JA630047), Tianjin Natural Science Foundation (07JCYBJC14300).