Tsuchiya and Muramatsu recently proved that the affine-scaling algorithm for linear programming generates convergent sequences of primal and dual variables whose limits are optimal for the corresponding primal and dua...
详细信息
Tsuchiya and Muramatsu recently proved that the affine-scaling algorithm for linear programming generates convergent sequences of primal and dual variables whose limits are optimal for the corresponding primal and dual problems as long as the step size is no more than two-thirds of the distance to the nearest face of the polytope. An important feature of this result is that it does not require any nondegeneracy assumptions. In this paper we show that Tsuchiya and Muramatsu's result is sharp by providing a simple linear programming problem for which the sequence of dual variables fails to converge for every step size greater than two-thirds.
We present a unified framework for solving linear and convex quadratic programs via interior point methods. At each iteration, this method solves an indefinite system whose matrix is {Mathematical expression} instead ...
详细信息
A new method for obtaining an initial feasible interior-point solution to a linear program is presented. This method avoids the use of a "big-M", and is shown to work well on a standard set of test problems....
详细信息
A new method for obtaining an initial feasible interior-point solution to a linear program is presented. This method avoids the use of a "big-M", and is shown to work well on a standard set of test problems. Conditions are developed for obtaining a near-optimal solution that is feasible for an associated problem, and details of the computational testing are presented. Other issues related to obtaining and maintaining accurate feasible solutions to linear programs with an interior-point method are discussed. These issues are important to consider when solving problems that have no primal or dual interior-point feasible solutions.
The problem of estimating the transition probabilities for the Markov chain associated to a Markov renewal process is considered. The estimators are to be based on censored observations of the Markov renewal process. ...
详细信息
The problem of estimating the transition probabilities for the Markov chain associated to a Markov renewal process is considered. The estimators are to be based on censored observations of the Markov renewal process. For a class of Markov renewal processes whose transition distributions factor, nonparametric estimators are defined. They are shown to be consistent and to converge weakly go Gaussian random variables. The result builds upon those in Gill (1980) for nonparametric estimation in this setting.
Version 5.1 of MINOS was used to analyze a set of linear programming test problems, which were run with different sets of options for scaling and partial pricing to illustrate the effects of these options on the perfo...
详细信息
Version 5.1 of MINOS was used to analyze a set of linear programming test problems, which were run with different sets of options for scaling and partial pricing to illustrate the effects of these options on the performance of the simplex method. Testing was performed on a DEC VAXstation II with 13 megabytes of main memory. The solution time was measured by timing the MINOS subroutine M5SOLV. The results demonstrate that the different options can significantly improve or degrade the performance of the simplex method. Scaling and partial pricing can improve the performance of the simplex method in most cases. However, options must be carefully chosen - a difficult task - in order not to degrade the performance of the simplex method.
作者：
STEELE, JMPrinceton University
Program in Statistics and Operations Research School of Engineering and Applied Science Princeton NJ 08544 USA
A bound is given for the cost of the spanning tree produced by the sequential minimal insertion procedure as applied to n points in the unit d -cube. The technique developed is reasonably general and can be applied to...
详细信息
A bound is given for the cost of the spanning tree produced by the sequential minimal insertion procedure as applied to n points in the unit d -cube. The technique developed is reasonably general and can be applied to several other problems of computational geometry, including the nearest neighbour heuristic for the traveling salesman problem. Attention is also given to bounding the sum of the powers of the edge lengths of sequentially constructed trees and paths. Examples illustrate that the bounds obtained are of best possible order as a function of the number of points.
This note sharpens and generalizes an inequality of Platzman and Bartholdi on the ratio of the cost of the path provided by the spacefilling heuristic to the cost of the optimal path through n points in R d .
This note sharpens and generalizes an inequality of Platzman and Bartholdi on the ratio of the cost of the path provided by the spacefilling heuristic to the cost of the optimal path through n points in R d .
Several problems that deal with smoothness of discrete functions and that are motivated by the task of deciding whether an N × N array of distances is a feasible laser radar (LADAR) image are investigated. The ma...
A theory of generalized gradients is presented for a class of Lipschitz vector-valued mappings from a Banach space to a locally convex order complete vector lattice. Necessary optimality conditions are obtained for no...
作者：
CHICKERING, JEQUALLS, WBJohn E. Chickering:is a systems analyst with American Management Systems
Inc. in Arlington Virginia. Mr. Chickering received his BS degree in marine engineering from the U.S. Merchant Marine Academy in Kings Point New York in 1981 and his MBA degree in operations research and statistics from the University of Maryland in 1985. He is a licensed third assistant engineer of steam and motor vessels and a member of the Naval Reserve. Mr. Chickering's work includes the design and specification of several management information systems for the U.S. Navy including one that will automate the Navy's engineering drawing management system. Most recently Mr. Chickering has helped develop a workstation for the Navy's Paperless Ship Initiative. William B. Quails:is a management consultant with American Management Systems
Inc. in Arlington Virginia. Mr. Quails received his BA degree in English from the Tulane University in New Orleans Louisiana in 1977 and his MPA degree in management science from the University of Georgia in 1982. Mr. Quails participated in the design and development of the U.S. Navy's Shipboard Non-tactical ADP Program II (SNAP II). Recently Mr. Quails has participated in the design and development of several knowledge-based computer systems using artificial intelligence programming technologies. Mr. Quails is a member of Pi Alpha Alpha an honorary public affairs and administration society.
The U.S. Navy relies heavily on advanced technology to carry out its missions. As a consequence, today's sailors are spending increasing amounts of time maintaining and repairing complex systems and equipment. In ...
详细信息
The U.S. Navy relies heavily on advanced technology to carry out its missions. As a consequence, today's sailors are spending increasing amounts of time maintaining and repairing complex systems and equipment. In performing these duties, sailors depend on supporting technical documentation. As the complexity of systems and equipment grow, the volume and complexity of this technical documentation also increases. As a result, technical information, one of the Navy's critical resources, is simultaneously becoming more vital and more difficult to use. The Navy is meeting this challenge by exploring innovative approaches to the management of technical documentation. One example is the Paperless Ship Initiative, which employs optical disk technology as the primary means for document storage. Optical disks can store large volumes of technical information in a small space. One way to take advantage of this auto mated access is to make technical information more readily accessible and easier to use. As an example, a technical manual can be organized on an optical disk into discrete segments of text and indexed for fast retrieval by section, subsection, or paragraph. Furthermore, mechanisms can be developed which allow computer-supported links between logically related segments of the text. This style of interface allows a user to interact directly with the textual passages and to establish new organizational and referential links between them. This style of interface falls under the general category of hypertext (also known as linked text ). The combination of optical disk storage and hypertext offers new possibilities for improving access to large volumes of technical documentation while maintaining all of the advantages of traditional paper-based documentation. This paper begins with a discussion of the need for better technical documentation support. Alternatives that can fulfill this need are reviewed and the role of hypertext is described. The paper illustrates a sample
暂无评论