Improved Labeling of L.P. Bases in Networks. (2002)
New labeling techniques are provided for accelerating the basis exchange step of specialized linear programming methods for network problems. These techniques substantially reduce the amount of...
Modelling and solving large scale networks are crucial to many practical military applications. The purpose of this note is to identify important elements of successful models and methods based on...
Solving Singularly Constrained Generalized Network Problems. (2002)
The singularly constrained generalized network problem represents a large class of capacitated linear programming (LP) problems. This class includes any LP problem whose coefficient matrix, ignoring...
Solving Constrained Generalized Network Problems. (2002)
A constrained generalized network problem is a linear programming problem in which the coefficient matrix contains m + q rows which are ordered such that each column has at most two non-zero entries...
The Alternating Basis Algorithm for Assignment Problems. (2002)
Barr,Richard S., Glover,Fred, Klingman,Darwin
The purpose of this paper is to present a new primal extreme point algorithm for solving assignment problems. The new algorithm both circumvents and exploits degeneracy. Degeneracy difficulties of...
A New Alternating Basis Algorithm for Semi-Assignment Networks. (2002)
Barr,Richard S., Glover,Fred, Klingman,Darwin
During the early 1970's, highly efficient special purpose computer codes were developed for solving capacitated transshipment problems based on primal extreme point algorithms. Computational...
Some Recent Practical Misconceptions about the State of the Art of Network Algorithms. (2002)
The purpose of this technical note is to correct several errors and misconceptions in a recent article appearing in Operations Research Concerning the state of the art in network solution methods and...
Enhancements of Spanning Tree Labeling Procedures for Network Optimization. (2002)
Barr,Richard, Glover,Fred, Klingman,Darwin
New labeling techniques are provided for accelerating the basis exchange step of specialized linear programming methods for network problems. Computational results are presented which show that these...
Glover,Fred, Klingman,Darwin, McMillan,Claude
This paper presents modeling techniques which are mathematically and symbolically linked to network and augmented network structures. These modeling techniques are called the NETFORM (network...
Glover,Fred, Karney,David, Klingman,Darwin
This study develops a prototype Computer-Assisted Policy Evaluation (CAPE) system for solving Naval personnel assignment problems. The CAPE system utilizes a new mathematical formulation for...
A Network Augmenting Path Basis Algorithm for Transshipment Problems. (2002)
Barr,Richard, Elam,Joyce, Glover,Fred, Klingman,Darwin
The purpose of this paper is to present a new simplex algorithm for solving capacitated transshipment network problems which both circumvents and exploits the pervasive degeneracy in such problems....
An 0(n(log n + log m)) Algorithm for LP Knapsacks with GUB Constraints. (2002)
A specialization of the dual simplex method is developed for solving the linear programming (LP) knapsack problem subject to generalized upper bound (GUB) constraints. The LP/GUB knapsack problem is...
The purpose of this note is to describe a modified version of the computer program NETGEN, which can be used to generate network flow problems for testing and validation purposes. The paper also...
Improved Computer-Based Planning Techniques. (2002)
Glover,Fred, Hultz,John, Klingman,Darwin
Management Science has responded recently to the needs of practitioners by contributing two new technologies. These are network computer implementation technology and NETFORM (network formulation)...
A Strongly Convergent Primal Algorithm for Generalized Networks. (2002)
Elam,Joyce, Glover,Fred, Klingman,Darwin
A major computational problem that arises in the attempt to solve generalized network and network-related problems is degeneracy. In fact, using primal extreme point solution techniques, the number...
Dial,Robert, Glover,Fred, Karney,David, Klingman,Darwin
This paper examines different algorithms for calculating the shortest path from one node to all other nodes in a network. More specifically, we seek to advance the state-of-the-art of computer...
Network Versus Linear Programming Algorithms and Implementations. (2002)
Glover,Fred, Hultz,John, Klingman,Darwin
Over the years modelers and practitioners have become so adept at designing large scale linear programming problems that in some cases the complexity is staggering. This has led to a demand for...
A Study of Alternative Relaxation Approaches for a Manpower Planning Problem. (2002)
Glover,Fred, Karney,David, Klingman,Darwin
This paper examines a variety of relaxation strategies for zero-one integer programming problems, containing from 54 to 2, 683 variables, that arise in manpower planning applications. These...
An Evaluation of Mathematical Programming and Minicomputers. (2002)
Elam,Joyce, Klingman,Darwin, Mulvey,John
The purpose of this paper is to explore the viability of implementing mathematical programming algorithms on minicomputers. We feel that the minicomputer explosion presents many exciting research...
Armstrong,Ronald D., Klingman,Darwin, Whitman,David
This paper presents a variant of the dual simplex method for the capacitated pure network problem and a computational analysis of this algorithm. This work includes the considerations of different...
The Simplex SON Algorithm for LP/Embedded Network Problems. (2002)
This paper develops a special partitioning method for solving LP problems with embedded network structure. These problems include many of the large-scale LP problems of practical importance,...
An Integrated Production, Distribution, and Inventory Planning System. (2002)
Glover, Fred, Jones, Gene, Karney, David, Klingman, Darwin, Mote, John
The critical importance of integrating production, distribution, and inventory (PDI) operations has long been recognized by the top management of many companies. Now, using the latest advances in...
Comprehensive Computer Evaluation and Enhancement of Maximum Flow Algorithms. (2002)
Glover,Fred, Klingman,Darwin, Mote,John, Whitman,David
The primary purpose of this study was to refine and streamline all major classes of maximum flow algorithms using the recent developments in network labeling and data organization techniques. To...
A Primal Simplex Variant for the Maximum Flow Problem, (2002)
Glover,Fred, Klingman,Darwin, Mote,John, Whitman,David
This paper presents a number of specialized implementations of the primal simplex algorithm for the maximum flow problem. Computational results indicate that some of these variants are both faster...
Solution Approaches for Network Flow Problems with Multiple Criteria, (2002)
A network variant of the multicriteria linear programming problem is presented. The primal simplex multicriteria algorithm first developed by Yu and Zeleny is specialized to handle the simple basis...
This paper studies two classes of bivariate regression analysis problems that can be formulated and solved quite efficiently as generalized network flow problems.
A Multi-Period Production, Distribution, and Inventory Planning Model, (2002)
Increasingly, today's manufacturing companies--both large and small--are finding it necessary to adopt computer-based planning systems to monitor their production, distribution, and inventory (PDI)...
Recent Developments in Computer Implementation Technology for Network Flow Algorithms, (2002)
The application of computer implementation technology to network optimization has brought about unprecedented advances in solution efficiency. The remarkable gains of the early to mid 1970's for...
Mathematical Optimization--A Successful Tool for Logistics Problems. (2002)
Recent developments in mathematical optimization are substantially enhancing the scope and power of logistics planning systems. Based on these advances, successful applications of sophisticated...
The increased importance of designing and implementing algorithms to solve particular management problems has created the need for more robust test problem generators that can match the overall...
A Note on Specialized Versus Unspecialized Methods for Maximum Flow Problems, (2002)
Glover,Fred, Klingman,Darwin, Mead,Melissa
A study developing highly efficient versions of both primal simplex and labeling methods for maximum flow problems has disclosed the surprising superiority of specialized primal methods. These...
A Note on Admissible Exchanges in Spanning Trees. (1999)
A constructive result is given for identifying a complete 'pairing' (one-one matching) of edges from two spanning trees such that each pair gives rise to an admissible exchange relative to the first...
The Generalized Lattice Point Problem. (1998)
The generalized lattice point problem, posed by Charnes and studied by M. J. L. Kirby, H. Love and others, is a linear program whose solutions are constrained to be extreme points of a specified...
Klingman,Darwin, Napier,A., Stutz,J.
One purpose of the paper is to describe the development, implementation, and availability of a computer program for generating a variety of feasible network problems. In particular the code can...
Equivalence of Boolean Constrained Transportation Problems to Transportation Problems. (1998)
Glover,Fred, Klingman,Darwin, Ross,G. Terry
The paper characterizes a class of constrained transportation problems (linear programming problems which are composed of a transportation problem with additional constraints) which can be...
Finding the Equivalent Transportation Formulations for Constrained Transportation Problems. (1998)
The paper describes a procedure for determining if constrained transportation problems (i.e., transportation problems with additional linear constraints) can be transformed into equivalent pure...
The Singularly Constrained Generalized Network Problem. (1998)
The paper presents a computationally efficient method for solving generalized network problems with an additional linear constraint. The method is basically the primal simplex method specialized to...
Extensions of the Augmented Predecessor Index Method to Generalized Network Problems. (1998)
Glover,Fred, Klingman,Darwin, Stutz,J.
The augmented predecessor indexing method is a procedure for efficiently updating the basis representation, flows and node potentials in an adjacent extreme point (or 'simplex' type) method for...
Improved Convexity Cuts for Lattice Point Problems. (1998)
The generalized lattice point (GLP) problem provides a formulation that accommodates a variety of discrete alternative problems. In the paper the authors show how to substantially strengthen the...
A Note on Computational Studies for Solving Transportation Problems. (1998)
Glover,Fred, Karney,David, Klingman,Darwin
The note provides a mathematical explanation for the superiority of certain pivot criterion heuristics when using the row-column sum method to solve transportation problems. In addition, new pivot...
Finding Equivalent Network Formulations for Constrained Network Problems. (1998)
The paper describes a procedure for determining if constrained network problems (i.e., network problems with additional linear constraints) can be transformed into equivalent pure network problems by...
Finding Minimum Spanning Trees with a Fixed Number of Links at a Node. (1998)
The paper addresses a variant of the minimum spanning tree problem in which a given node is required to have a fixed number of incident edges. It is shown that this problem, which is combinatorially...
An Advanced Dual Basic Feasible Solution for a Class of Capacitated Generalized Networks. (1998)
Hultz,John, Klingman,Darwin, Russell,Robert
The paper presents a one pass algorithm that determines an advanced dual basic feasible solution for a class of capacitated generalized network problems. Special cases in this class of problems...
A Cottonpickin' Cotton Ginning Problem. (1998)
Klingman,Darwin, Randolph,Paul H., Fuller,Stephen W.
In the Mesilla Valley of New Mexico there are 150 cotton farmers and 20 cotton gins. The weekly cotton picking and the weekly gin capacities are known, as well as the transportation and ginning...
The Computer Can Differentiate Too. (1998)
For mathematical problems whose solution requires the evaluation of first or second partial derivatives of user-defined functions, symbolic differentiation is offered as a viable alternative to...
A Note on Exchanges in Matroid Bases. (1998)
Gabow,Harold, Glover,Fred, Klingman,Darwin
Many network and linear programming problems are solved by repeatedly exchanging elements of a base. The pivot step in linear programming is a general example. The existence of such exchanges can be...
Capsule View of Future Developments on Large Scale Network and Network-Related Problems. (1998)
The primary purpose of this paper is to identify recent major accomplishments and prophesy (suggest) future trends in the solution, modeling, and human engineering aspects of network and...
Network Application in Industry and Government. (1998)
The primary purpose of this paper is to provide the practicioner with a short, but informative handbook of tools to use in modeling decision making situations as network flow problems. These tools...
Shortest path forest with topological ordering: An algorithm description in SDL
Dial, Robert, Glover, Fred, Karney, David, Klingman, Darwin
This short note presents a formal description of a fast and robust shortest path algorithm. Modeled on an algorithm of Pape (1974), it requires less memory store than most algorithms and at the same...