A network simplex method

Simple combinatorial modifications are given which ensure finiteness in the primal simplex method for the transshipment problem and the upper-bounded primal simplex method for the minimum cost flow problem. The modifications involve keeping strongly feasible bases. An efficient algorithm is given for converting any feasible basis into a strongly feasible basis. Strong feasibility is preserved by a rule for choosing the leaving basic variable at each simplex iteration. The method presented is closely related to a new perturbation technique and to previously known degeneracy modifications for shortest path problems and maximum flow problems.The author holds a National Research Council of Canada Post-Doctorate Fellowship.     

On the number of iterations of Karmarkar's algorithm for linear programming

Karmarkar's algorithm for linear programming was published in 1984, and it is highly important to both theory and practice. On the practical side some of its variants have been found to be far more efficient than the simplex method on a wide range of very large calculations, while its polynomial time properties are fundamental to research on complexity. These properties depend on the fact that each iteration reduces a potential function by an amount that is bounded away from zero, the bound being independent of all the coefficients that occur. It follows that, under mild conditions on the initial vector of variables, the number of iterations that are needed to achieve a prescribed accuracy in the final value of the linear objective function is at most a multiple ofn, wheren is the number of inequality constraints. By considering a simple example that allowsn to be arbitrarily large, we deduce analytically that the magnitude of this complexity bound is correct. Specifically, we prove that the solution of the example by Karmarkar's original algorithm can require aboutn/20 iterations. Further, we find that the algorithm makes changes to the variables that are closely related to the steps of the simplex method.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

The alternating basis algorithm for assignment problems

The purpose of this paper is to present a new primal extreme point algorithm for solving assignment problems which both circumvents and exploits degeneracy. The algorithm is based on the observation that the degeneracy difficulties of the simplex method result from the unnecessary inspection of alternative basis representations of the extreme points. This paper characterizes a subsetQ of all bases that are capable of leading to an optimal solution to the problem if one exists. Using this characterization, an extreme point algorithm is developed which considers only those bases inQ. Computational results disclose that the new algorithm is substantially more efficient than previously developed primal and primal-dual extreme point (simplex) methods for assignment problems.     

On the solution of highly degenerate linear programmes

The solution of scheduling problems often gives rise to highly degenerate linear programmes which cause significant computational difficulties for the revised simplex method. Wolfe's highly effective ad hoc method for overcoming the cycling or stalling problems associated with degeneracy is described. Here it is given a geometric interpretation in terms of finding a direction of recession for a reduced problem which is fundamental to a full understanding of the procedure. An example of an aircrew scheduling problem is used to illustrate the effectiveness of the method.     

A practical anti-cycling procedure for linearly constrained optimization

A procedure is described for preventing cycling in active-set methods for linearly constrained optimization, including the simplex method. The key ideas are a limited acceptance of infeasibilities in all variables, and maintenance of a working feasibility tolerance that increases over a long sequence of iterations. The additional work per iteration is nominal, and stalling cannot occur with exact arithmetic. The method appears to be reliable, based on computational results for the first 53 linear programming problems in theNetlib set.The material contained in this report is based upon research supported by the Air Force Office of Scientific Research Grant 87-01962; the U.S. Department of Energy Grant DE-FG03-87ER25030; National Science Foundation Grants CCR-8413211 and ECS-8715153; and the Office of Naval Research Contract N00014-87-K-0142.     

Solving shortest length least-squares problems via dynamic programming

If the matrixA is not of full rank, there may be many solutions to the problem of minimizing Ax–b overx. Among such vectorsx, the unique one for which x is minimum is of importance in applications. This vector may be represented asx=A ⁺ b. In this paper, the functional equation technique of dynamic programming is used to find the shortest solution to the least-squares problem in a sequential fashion. The algorithm is illustrated with an example.Our debt to the late Professor Richard Bellman is clear, and we wish to thank Professor Harriet Kagiwada for many stimulating conversations concerning least-squares problems over a long period of years.     

An Algorithm for Solving the Minimum-Norm Point Problem over the Intersection of a Polytope and an Affine Set

In this paper, we propose an efficient algorithm for finding the minimum-norm point in the intersection of a polytope and an affine set in an n-dimensional Euclidean space, where the polytope is expressed as the convex hull of finitely many points and the affine set is expressed as the intersection of k hyperplanes, k1. Our algorithm solves the problem by using directly the original points and the hyperplanes, rather than treating the problem as a special case of the general quadratic programming problem. One of the advantages of our approach is that our algorithm works as well for a class of problems with a large number (possibly exponential or factorial in n) of given points if every linear optimization problem over the convex hull of the given points is solved efficiently. The problem considered here is highly degenerate, and we take care of the degeneracy by solving a subproblem that is a conical version of the minimum-norm point problem, where points are replaced by rays. When the number k of hyperplanes expressing the affine set is equal to one, we can easily avoid degeneracy, but this is not the case for k2. We give a subprocedure for treating the degenerate case. The subprocedure is interesting in its own right. We also show the practical efficiency of our algorithm by computational experiments.     

Modified proximal point algorithm for extended linear-quadratic programming

Extended linear-quadratic programming arises as a flexible modeling scheme in dynamic and stochastic optimization, which allows for penalty terms and facilitates the use of duality. Computationally it raises new challenges as well as new possibilities in large-scale applications. Recent efforts have been focused on the fully quadratic case ([15] and [23]), while relying on the fundamental proximal point algorithm (PPA) as a shell of outer iterations when the problem is not fully quadratic. In this paper, we focus on the nonfully quadratic cases by proposing some new variants of the fundamental PPA. We first construct a continuously differentiable saddle function S(u, v) through infimal convolution in such a way that the optimal primal-dual pairs of the original problem are just the saddle points of S(u, v) on the whole space. Then the original extended linear-quadratic-programming problem reduces to solving the nonlinear equation S(u, v)=0. We then embed the fundamental PPA and some of its previous variants in the framework of a Newton-like iteration for this equation. After revealing the local quadratic structure of S near the solution, we derive new extensions of the fundamental PPA. In numerical tests, the modified iteration scheme based on the quasi-Newton update formula outperforms the fundamental PPA considerably.     

Analysis of a class of fractional programming problems

We propose a solution strategy for fractional programming problems of the form max _xx g(x)/ (u(x)), where the function satisfies certain convexity conditions. It is shown that subject to these conditions optimal solutions to this problem can be obtained from the solution of the problem max _xx g(x) + u(x), where is an exogenous parameter. The proposed strategy combines fractional programming andc-programming techniques. A maximal mean-standard deviation ratio problem is solved to illustrate the strategy in action.     

A simplicial approximation of a solution for the nonlinear complementarity problem

For a given map f from the n-dimensional Euclidean space En into itself, we consider the complementary problem of finding a nonnegative vector x in En whose imagef(x) is also nonnegative and such that the two vectors are orthogonal. It is the unifying mathematical form for several problems arising in different fields such as mathematical programming, game theory and economics.In this paper a new algorithm is developed based on the adjacent simplex technique , which was used by Garcia, Lemke and Lüthi for approximating an equilibrium point of a noncooperative n-person game. An almost-complementary path leads to a complementary simplex, which approximates a stationary point. Because most of the existence proofs for the nonlinear complementarity use the relationship between stationary points and complementarity, the algorithm gives constructive proofs for many existence theorems. If a better approximation is desired, the algorithm may be restarted from any point. The dimension of the simplices on the path is varying, which computationally should result in some savings.     

On the stability of the transport equation

We consider boundary value problems associated with the equation T=–A in a Hilbert Space, where T and A are bounded, self adjoint, injective, and A has a bounded inverse. We discuss the stability of the solution when A is perturbed by a self adjoint operator.     

A Constant-Potential Infeasible-Start Interior-Point Algorithm with Computational Experiments and Applications

We present a constant-potential infeasible-start interior-point (INFCP) algorithm for linear programming (LP) problems with a worst-case iteration complexity analysis as well as some computational results.The performance of the INFCP algorithm is compared to those of practical interior-point algorithms. New features of the algorithm include a heuristic method for computing a good starting point and a procedure for solving the augmented system arising from stochastic programming with simple recourse. We also present an application to large scale planning problems under uncertainty.     

Convex Separable Minimization Subject to Bounded Variables

A minimization problem with convex and separable objective function subject to a separable convex inequality constraint and bounded variables is considered. A necessary and sufficient condition is proved for a feasible solution to be an optimal solution to this problem. Convex minimization problems subject to linear equality/linear inequality constraint, and bounds on the variables are also considered. A necessary and sufficient condition and a sufficient condition, respectively, are proved for a feasible solution to be an optimal solution to these two problems. Algorithms of polynomial complexity for solving the three problems are suggested and their convergence is proved. Some important forms of convex functions and computational results are given in the Appendix.     

Estimate of the modulus of continuity of the generalized solutions of certain singular parabolic equations

One considers singular parabolic equations of the form (u)/t–u0,where sign u is a multivalued function, equal to -I for u<0, to 1 for u>0, and to the segment [-I,I] for u=0. Such a class of equations contains, in particular, the model for the two-phase Stefan problem, the porous medium equation, and the plasma equation. For the bounded generalized solutions u(x,t) of the indicated equations (without the assumption u/L²one has established a qualified local estimate of the modulus of continuity.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Ins'tituta im. V. A. Steklova AN SSSR, Vol. 147, pp. 49–71, 1985.     

Finding Postal Carrier Walk Paths in Mixed Graphs

The postman problem requires finding a lowest cost tour in a connected graph that traverses each edge at least once. In this paper we first give a brief survey of the literature on postman problems including, the original Chinese postman problem on undirected graphs, the windy Chinese postman problem on graphs where the cost of an arc depends on the direction the arc is transversed, the directed postman problem on graphs with directed edges, and the mixed postman problem on graphs in which there are some directed and some undirected arcs.We show how the mixed postman problem can be solved as an integer program, using the formulation of Gendreau, Laporte and Zhao, by a new row addition branch and bound algorithm, which is a modification of the column subtraction algorithm for set partitioning problems of Harche and Thompson. Computational experience shows that a slack variable heuristic is very effective in finding good solutions that are frequently optimal for these problems.     

A chance-constrained programming algorithm

This paper describes a new algorithm solving the deterministic equivalents of chance-constrained problems where the random variables are normally distributed and independent of each other. In this method nonlinear chance-constraints are first replaced by uniformly tighter linear constraints. The resulting linear programming problem is solved by a standard simplex method. The linear programming problem is then revised using the solution data and solved again until the stopping rule of the algorithm terminates the process. It is proved that the algorithm converges and that the solution found is the -optimal solution of the chance-constrained programming problem.The computational experience of the algorithm is reported. The algorithm is efficient if the random variables are distributed independently of each other and if they number less than two hundred. The computing system is called CHAPS, i.e. Chance-ConstrainedProgrammingSystem.     

Use of the augmented penalty function in mathematical programming problems,part 1

In this paper, the problem of minimizing a functionf(x) subject to a constraint (x)=0 is considered. Here,f is a scalar,x ann-vector, and aq-vector, withq<n. The use of the augmented penalty function is explored in connection with theordinary gradient algorithm. The augmented penalty functionW(x, ,k) is defined to be the linear combination of the augmented functionF(x, ) and the constraint errorP(x), where theq-vector is the Lagrange multiplier and the scalark is the penalty constant.The ordinary gradient algorithm is constructed in such a way that the following properties are satisfied in toto or in part: (a) descent property on the augmented penalty function, (b) descent property on the augmented function, (c) descent property on the constraint error, (d) constraint satisfaction on the average, or (e) individual constraint satisfaction. Properties (d) and (e) are employed to first order only.With the above considerations in mind, two classes of algorithms are developed. For algorithms of Class I, the multiplier is determined so that the error in the optimum condition is minimized for givenx; for algorithms of Class II, the multiplier is determined so that the constraint is satisfied to first order.Algorithms of Class I have properties (a), (b), (c) and include Algorithms (I-) and (I-). In the former algorithm, the penalty constant is held unchanged for all iterations; in the latter, the penalty constant is updated at each iteration so as to ensure satisfaction of property (d).Algorithms of Class II have properties (a), (c), (e) and include Algorithms (II-) and (II-). In the former algorithm, the penalty constant is held unchanged for all iterations; in the latter, the penalty constant is updated at each iteration so as to ensure satisfaction of property (b).Four numerical examples are presented. They show that algorithms of Class II exhibit faster convergence than algorithms of Class I and that algorithms of type () exhibit faster convergence than algorithms of type (). Therefore, Algorithm (II-) is the best among those analyzed. This is due to the fact that, in Algorithm (II-), individual constraint satisfaction is enforced and that descent properties hold for the augmented penalty function, the augmented function, and the constraint error.This research was supported by the National Science Foundation, Grant No. GP-27271. The authors are indebted to Dr. J. N. Damoulakis for analytical and numerical assistance. Discussions with Professor H. Y. Huang are acknowledged.     

Method of Propagating Waves for a One-Dimensional Inhomogeneous Medium

The aim of this work is to develop a method of propagating waves based on the idea of a wave as a changing state of a medium. This method allows us to represent a solution of the one-dimensional wave equation in an inhomogeneous medium as the sum of two constantly deformed waves, the right wave and the left wave, transported from point to point with coefficients depending on the points and the transport time. By the propagating-wave method we obtain explicit (as far as possible) formulas for solutions of the mixed problem with homogeneous and inhomogeneous boundary conditions and solutions of the Goursat problem. The derivation of these formulas is based on special convolution formulas for the transport coefficients that are similar to the addition identities for trigonometric functions.__________Translated from Trudy Seminara imeni I. G. Petrovskogo, No. 24, pp. 3–43, 2004.     

Global convergence of the affine scaling methods for degenerate linear programming problems

In this paper we show the global convergence of the affine scaling methods without assuming any condition on degeneracy. The behavior of the method near degenerate faces is analyzed in detail on the basis of the equivalence between the affine scaling methods for homogeneous LP problems and Karmarkar's method. It is shown that the step-size 1/8, where the displacement vector is normalized with respect to the distance in the scaled space, is sufficient to guarantee the global convergence of the affine scaling methods.This paper was presented at the International Symposium Interior Point Methods for Linear Programming: Theory and Practice, held on January 18–19, 1990, at the Europa Hotel, Scheveningen, the Netherlands.     

A little theorem of the bigℳ in interior point algorithms

When we apply interior point algorithms to various problems including linear programs, convex quadratic programs, convex programs and complementarity problems, we often embed an original problem to be solved in an artificial problem having a known interior feasible solution from which we start the algorithm. The artificial problem involves a constant (or constants) which we need to choose large enough to ensure the equivalence between the artificial problem and the original problem. Theoretically, we can always assign a positive number of the order O(2 ^L ) to in linear cases, whereL denotes the input size of the problem. Practically, however, such a large number is impossible to implement on computers. If we choose too large, we may have numerical instability and/or computational inefficiency, while the artificial problem with not large enough will never lead to any solution of the original problem. To solve this difficulty, this paper presents a little theorem of the big, which will enable us to find whether is not large enough, and to update during the iterations of the algorithm even if we start with a smaller. Applications of the theorem are given to a polynomial-time potential reduction algorithm for positive semi-definite linear complementarity problems, and to an artificial self-dual linear program which has a close relation with the primal—dual interior point algorithm using Lustig's limiting feasible direction vector.