Necessary and sufficient conditions for the existence of complementary solutions and characterizations of the matrix classesQ andQ 0

We simplify a result by Mangasarian on the existence of solutions to the linear complementarity problem. The simplified condition gives a new geometric interpretation of the result. When used to characterize the matrix classesQ andQ ₀, our condition suggests a finitely checkable sufficient condition forP andP ₀.This work was supported in part by the Office of Naval Research under Contract No. N00014-86-K-0173, and by general research development funds provided by the Georgia Institute of Technology.     

Exploiting special structure in Karmarkar's linear programming algorithm

We propose methods to take advantage of specially-structured constraints in a variant of Karmarkar's projective algorithm for standard form linear programming problems. We can use these constraints to generate improved bounds on the optimal value of the problem and also to compute the necessary projections more efficiently, while maintaining the theoretical bound on the algorithm's performance. It is shown how various upper-bounding constraints can be handled implicitly in this way. Unfortunately, the situation for network constraints appears less favorable.Research supported in part by National Science Foundation Grant ECS-8602534, ONR Contract N00014-87-K-0212 and the US Army Research Office through the Mathematical Sciences Institute of Cornell University.     

A lower bound on the number of iterations of long-step primal-dual linear programming algorithms

Recently, Todd has analyzed in detail the primal-dual affine-scaling method for linear programming, which is close to what is implemented in practice, and proved that it may take at leastn ^1/3 iterations to improve the initial duality gap by a constant factor. He also showed that this lower bound holds for some polynomial variants of primal-dual interior-point methods, which restrict all iterates to certain neighborhoods of the central path. In this paper, we further extend his result to long-step primal-dual variants that restrict the iterates to a wider neighborhood. This neigh-borhood seems the least restrictive one to guarantee polynomiality for primal-dual path-following methods, and the variants are also even closer to what is implemented in practice.Research supported in part by NSF, AFOSR and ONR through NSF Grant DMS-8920550.This author is supported in part by NSF Grant DDM-9207347. Part of thiw work was done while the author was on a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University, Ithaca, NY 14853, supported in part by the Cornell Center for Applied Mathematics and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.     

A polynomial-time algorithm,based on Newton's method,for linear programming

A new interior method for linear programming is presented and a polynomial time bound for it is proven. The proof is substantially different from those given for the ellipsoid algorithm and for Karmarkar's algorithm. Also, the algorithm is conceptually simpler than either of those algorithms.This research was supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship and by NSF Grant 8120790. The research was performed at the Mathematical Sciences Research Institute in Berkeley, California.     

Due dates in a manufacturing shop: An unweighted case

A dispatching rule is proposed for job shop operations where the performance criteria are due date related. The dispatching rule is constructed by combining the characteristics of the shortest process time rule and a dynamically determined earliest due date rule. The performance of the proposed rule is compared to currently well known rules across various shop environments using discrete simulation.This work was partially supported by: The National Science Foundation, Grant No. CDR-8300965; member companies of the Material Handling Research Center, the Georgia Institute of Technology and Texas A&M University.     

A supervisory control paradigm for real-time control of flexible manufacturing systems

Most of the current academic flexible manufacturing system (FMS) scheduling research has focused on the derivation of algorithms or knowledge-based techniques for efficient FMS real-time control. Here, the limitations of this view are outlined with respect to effective control of actual real-time FMS operation. A more realistic paradigm for real-time FMS control is presented, based on explicit engineering of human and automated control functions and system interfaces. To illustrate design principles within the conceptual model, an example of algorithmic and operator function models for a specific real-time FMS control problem are developed.Portions of this paper have appeared in: Proc. 2nd ORSA/TIMS Conf. on Flexible Manufacturing Systems: Operations Research Models and Applications, Ann Arbor, Michigan, August 12–15, 1986, and Proc. 1986 Int. Conf. on Systems, Man, and Cybernetics, Atlanta, Georgia, October 14–17, 1986.This research was supported in part by the New Faculty Research Program of the Georgia Institute of Technology.     

Low order polynomial bounds on the expected performance of local improvement algorithms

We present a general abstract model of local improvement, applicable to such diverse cases as principal pivoting methods for the linear complementarity problem and hill climbing in artificial intelligence. The model accurately predicts the behavior of the algorithms, and allows for a variety of probabilistic assumptions that permit degeneracy. Simulation indicates an approximately linear average number of iterations under a variety of probability assumptions. We derive theoretical bounds of 2en logn and en ² for different distributions, respectively, as well as polynomial bounds for a broad class of probability distributions. We conclude with a discussion of the applications of the model to LCP and linear programming.The author was supported by the New Faculty Research Development Program of the Georgia Institute of Technology. This work is based on the author's Ph.D. thesis, performed under George Dantzig at Stanford 1978–81, at the Systems Optimization Laboratory. While at Stanford, research was supported in part by Department of Energy Contract AM03-76SF00326, PA #DE-AT03-76ER72018; Office of Naval Research Contract N00014-75-C-0267; National Science Foundation Grants MCS76-81259, MCS-7926009 and ECS-8012974; and Army Research Office Contract DAA29-79-C-0110. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

Min-cut clustering

We describe a decomposition framework and a column generation scheme for solving a min-cut clustering problem. The subproblem to generate additional columns is itself an NP-hard mixed integer programming problem. We discuss strong valid inequalities for the subproblem and describe some efficient solution strategies. Computational results on compiler construction problems are reported.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.This research was supported by NSF grants DMS-8719128 and DDM-9115768, and by an IBM grant to the Computational Optimization Center, Georgia Institute of Technology.     

Constant potential primal—dual algorithms: A framework

We start with a study of the primal—dual affine-scaling algorithms for linear programs. Using ideas from Kojima et al., Mizuno and Nagasawa, and new potential functions we establish a framework for primal—dual algorithms that keep a potential function value fixed. We show that if the potential function used in the algorithm is compatible with a corresponding neighborhood of the central path then the convergence proofs simplify greatly. Our algorithms have the property that all the iterates can be kept in a neighborhood of the central path without using any centering in the search directions.Research performed while the author was Ph.D. student at Cornell University and was supported in part by the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C-0027, and also by NSF, AFOSR and ONR through NSF Grant DMS-8920550.     

A simplified homogeneous and self-dual linear programming algorithm and its implementation

We present a simplification and generalization of the recent homogeneous and self-dual linear programming (LP) algorithm. The algorithm does not use any Big-M initial point and achieves -iteration complexity, wheren andL are the number of variables and the length of data of the LP problem. It also detects LP infeasibility based on a provable criterion. Its preliminary implementation with a simple predictor and corrector technique results in an efficient computer code in practice. In contrast to other interior-point methods, our code solves NETLIB problems, feasible or infeasible, starting simply fromx=e (primal variables),y=0 (dual variables),z=e (dual slack variables), wheree is the vector of all ones. We describe our computational experience in solving these problems, and compare our results with OB1.60, a state-of-the-art implementation of interior-point algorithms.Research supported in part by NSF Grant DDM-9207347 and by an Iowa College of Business Administration Summer Grant.Part of this work was done while the author was on a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University, Ithaca, NY 14853, USA, supported in part by the Cornell Center for Applied Mathematics and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.     

Coloring even-faced graphs in the torus and the Klein bottle

We prove that a triangle-free graph drawn in the torus with all faces bounded by even walks is 3-colorable if and only if it has no subgraph isomorphic to the Cayley graph C(Z ₁₃; 1,5). We also prove that a non-bipartite quadrangulation of the Klein bottle is 3-colorable if and only if it has no non-contractible separating cycle of length at most four and no odd walk homotopic to a non-contractible two-sided simple closed curve. These results settle a conjecture of Thomassen and two conjectures of Archdeacon, Hutchinson, Nakamoto, Negami and Ota. Institute for Theoretical Computer Science is supported as project 1M0545 by the Ministry of Education of the Czech Republic. The author was visiting Georgia Institute of Technology as a Fulbright scholar in the academic year 2005/06. Partially supported by NSF Grants No. DMS-0200595 and DMS-0354742.     

Interpolation, correlation identities, and inequalities for infinitely divisible variables

We present an interpolation formula for the expectation of functions of infinitely divisible (i.d.) variables. This is then applied to study the association problem for i.d. vectors and to present new covariance expansions and correlation inequalities. Acknowledgements and Notes. The research of C. Houdré was supported in part by an NSF Mathematical Sciences Post-Doctoral Fellowship and by an NSF-NATO Postdoctoral Fellowship and by the NSF grant No. DMS-98032039. This research was completed while V. Pérez-Abreu was visiting the Georgia Institute of Technology.     

Containing and shrinking ellipsoids in the path-following algorithm

We describe a new potential function and a sequence of ellipsoids in the path-following algorithm for convex quadratic programming. Each ellipsoid in the sequence contains all of the optimal primal and dual slack vectors. Furthermore, the volumes of the ellipsoids shrink at the ratio , in comparison to 2^–(1) in Karmarkar's algorithm and 2^–(1/n) in the ellipsoid method. We also show how to use these ellipsoids to identify the optimal basis in the course of the algorithm for linear programming.Research supported by The U.S. Army Research Office through The Mathematical Sciences Institute of Cornell University when the author was visiting at Cornell.Research supported in part by National Science Foundation Grant ECS-8602534 and Office of Naval Research Contract N00014-87-K-0212.     

Energy balance invariance for interacting particle systems

This paper studies the principle of invariance of balance of energy and its consequences for a system of interacting particles under groups of transformations. Balance of energy and its invariance is first examined in Euclidean space. Unlike the case of continuous media, it is shown that conservation and balance laws do not follow from the assumption of invariance of balance of energy under time-dependent isometries of the ambient space. However, the postulate of invariance of balance of energy under arbitrary diffeomorphisms of the ambient (Euclidean) space, does yield the correct conservation and balance laws. These ideas are then extended to the case when the ambient space is a Riemannian manifold. Pairwise interactions in the case of geodesically complete Riemannian ambient manifolds are defined by assuming that the interaction potential explicitly depends on the pairwise distances of particles. Postulating balance of energy and its invariance under arbitrary time-dependent spatial diffeomorphisms yields balance of linear momentum. It is seen that pairwise forces are directed along tangents to geodesics at their end points. One also obtains a discrete version of the Doyle–Ericksen formula, which relates the magnitude of internal forces to the rate of change of the interatomic energy with respect to a discrete metric that is related to the background metric. Dedicated to the memory of Shahram Kavianpour (1975-2007). Jerrold E. Marsden: Research partially supported by the California Institute of Technology and NSF-ITR Grant ACI-0204932. Arash Yavari: Research supported by the Georgia Institute of Technology.     

Periodic maintenance and repair rate control in stochastic manufacturing systems

In this paper, we consider a periodic preventive maintenance, repair, and production model of a flexible manufacturing system with failure-prone machines, where the control variables are the repair rate and production rate. We use periodic preventive maintenance to reduce the machine failure rates and improve the productivity of the system. One of the distinct features of the model is that the repair rate is adjustable. Our objective is to choose a control process that minimizes the total cost of inventory/shortage, production, repair, and maintenance. Under suitable conditions, we show that the value function is locally Lipschitz and satisfies an Hamilton-Jacobi-Bellman equation. A sufficient condition for optimal control is obtained. Since analytic solutions are rarely available, we design an algorithm to approximate the optimal control problem. To demonstrate the performance of the numerical method, an example is presented.Research of this author was supported by the Natural Sciences and Engineering Research Council of Canada, Grant OGP0036444.Research of this author was supported in part by the University of Georgia.Research of this author was supported in part by the National Science Foundation, Grant DMS-92-24372.     

A set of staircase linear programming test problems

A set of staircase linear programming test problems are made available for computational experiments.Research supported by the U.S. Department of Energy under contract DE-AC02-76CH00016.Research supported by the Belgian National Research Program in Energy, contract E/I/3.     

An O(n 3 L) adaptive path following algorithm for a linear complementarity problem

In this paper we propose an O(n ³ L) algorithm which is a modification of the path following algorithm [8] for a linear complementarity problem. The path following algorithm has to take a short step size in each iteration in order to bound the number of overall arithmetic operations by O(n ³ L). In practical computation, we can determine the step size adaptively. Mizuno, Yoshise, and Kikuchi [11] reported that such an adaptive algorithm required about O(L) iterations for some test problems. Here we show that we can use a rank one update technique in the adaptive algorithm so that the number of overall arithmetic operations is theoretically bounded by O(n ³ L).Research supported in part by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research supported in part by NSF grants ECS-8602534 and DMS-8904406 and ONR contract N-00014-87-K0212.     

Random walks in varying dimensions

We establish recurrence criteria for sums of independent random variables which take values in Euclidean lattices of varying dimension. In particular, we describe transient inhomogeneous random walks in the plane which interlace two symmetric step distributions of bounded support.Research partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research supported in part by National Science Foundation Grant No. DMS 9300191, by a Sloan Foundation Fellowship, and by a Presidential Faculty Fellowship.     

Solving combinatorial optimization problems using Karmarkar's algorithm

We describe a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.Computational facilities provided by the Cornell Computational Optimization Project supported by NSF Grant DMS-8706133 and by the Cornell National Supercomputer Facility. The Cornell National Supercomputer Facility is a resource of the Center for Theory and Simulation in Science and Engineering at Cornell Unversity, which is funded in part by the National Science Foundation, New York State, and the IBM Corporation. The research of both authors was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by ONR Grant N00014-90-J-1714.Research partially supported by NSF Grant ECS-8602534 and by ONR Contract N00014-87-K-0212.     

Modifications and implementation of the ellipsoid algorithm for linear programming

We give some modifications of the ellipsoid algorithm for linear programming and describe a numerically stable implementation. We are concerned with practical problems where user-supplied bounds can usually be provided. Our implementation allows constraint dropping and updates bounds on the optimal value, and should be able to terminate with an indication of infeasibility or with a provably good feasible solution in a moderate number of iterations.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAG29-77-G-0114 and the National Science Foundation under Grant MCS-8006065.The work of this author was supported in part by the National Science Foundation under Grant ECS-7921279.