A note on integer linear fractional programming

This note consists of developing a method for enforcing additional constraints to linear fractional programs and showing its usefulness in solving integer linear fractional programs.     

On the equivalence between the Node-ARC and ARC-Chain formulations for the multi-commodity maximal flow problem

The purpose of this article is to formulate the multi-commodity maximal flow problem into a node-arc form and to show that when decomposition is applied to this form the resulting master and subproblems become precisely those described by Ford & Fulkerson [3] using the arc-chain formulation. A generalization to the problem is then considered which can potentially speed its convergence.     

Uniformly minimum variance unbiased estimates of operational readiness and reliability in a two-state system

This paper obtains the uniformly minimum variance unbiased estimates of two indices of performance of a system which alternates between two states “up” or “down” in accordance with a Markov process. The two indices are (1) operational readiness, which measures the probability that the system will be up when needed; and (2) operational reliability, which measures the probability that the system will be up during the entire time of need. For the purpose of obtaining these estimates, two types of observations are considered: (a) those which reveal only the state of system at isolated time-points, and (b) those which continuously record the duration of the “up” and “down” times of the system.     

Optimal interdiction policy for a flow network

This paper analyzes the problem faced by a field commander who, confronted by an enemy on N battlefields, must determine an interdiction policy for the enemy's logistics system which minimizes the amount of war material flowing through this system per unit time. The resource utilized to achieve this interdiction is subject to constraint. It can be shown that this problem is equivalent to determining the set of arcs Z* to remove subject to constraint from a directed graph G such that the resulting maximal flow is minimized. A branch and bound algorithm for the solution to this problem is described, and a numerical example is provided.     

Application of the GLM technique to a production planning problem

Generalized Lagrange Multipliers (GLM) are used to develop an algorithm for a type of multiproduct single period production planning problem which involves discontinuities of the fixed charge variety. Several properties of the GLM technique are developed for this class of problems and from these properties an algorithm is obtained. The problem of resolving the gaps which are exposed by the GLM procedure is considered, and an example involving a quadratic cost function is explored in detail.     

On queues with state-dependent Erlang service

Some general results are derived for single-channel queues with Poisson input and state-dependent Erlang service times in view of the possible use of this model to approximate arbitrary M/G/1-like state-dependent queues in a manner similar to that suggested by Rosenshine, and by Kendall, and Kotiah, Thompson, and Waugh for the M/G/1. Numerical procedures are indicated for the evaluation of stationary state probabilities, expected system sizes and waiting times, and parameter estimation.     

Optimal control of multi-channel service systems

D. P. Heyman, M. Sobel, and M. J. Magazine among others have shown existence of an optimal policy for control of single server queuing systems. For queues under periodic review existence of an analogous rule is established for multi-server systems. Formulation as a dynamic programming problem is given and proofs for existence are presented for finite horizon, infinite horizon and average cost criteria.     

Statistical concepts in computational mathematics

For a young science and even for most old ones, the intensity and variety of activities involved in computer science are unsurpassed. In an effort to provide the extremely varied training needed in the field, curriculum planners have tended to slight probability and statistics. Rarely has it been a requisite and only occasionally a desired elective However, not only is an adequate foundation in probability and statistics necessary for such external computer applications as tracking and other data reduction, Monte Carlo techniques, gaming, operations research, traffic analyses, etc., but it also plays an important role in internal applications to computer science and technology This effort in Rand's continuing study of computational mathematics and its applications offers a number of examples in various areas of computational mathematics and computing machine arithmetic-to say nothing of computer design, time sharing, and the like-to support the thesis that probability and statistics should be a requisite, not simply an elective or, even worse, ignored, at any institution offering a program in computer science. Further more, a potentially profitable source of research problems can be found in the interface between probability and statistics and computer science.     

A note on adaptive boiler tube pulling

This paper develops an adaptive algorithm for determining boiler tube pulling strategies by postulating a Beta prior on the probability that an individual tube is defective. This prior is updated according to Bayes' Rule as a result of the sample obtained during the tube pulling process.     

Optimum quantiles for the linear estimation of the parameters of the extreme value distribution in complete and censored samples

The present study is concerned with the determination of a few observations from a sufficiently large complete or censored sample from the extreme value distribution with location and scale parameters μ and σ, respectively, such that the asymptotically best linear unbiased estimators (ABLUE) of the parameters in Ref. [24] yield high efficiencies among other choices of the same number of observations. (All efficiencies considered are relative to the Cramér-Rao lower bounds for regular unbiased estimators.) The study is on the asymptotic theory and under Type II censoring scheme. For the estimation of μ when σ is known, it has been proved that there exists a unique optimum spacing whether the sample is complete, right censored, left censored, or doubly censored. Several tables are prepared to aid in the numerical computation of the estimates as well as to furnish their efficiencies. For the estimation of σ when μ is known, it has been observed that there does not exist a unique optimum spacing. Accordingly we have obtained a spacing based on a complete sample which yields high efficiency. A similar table as above is prepared. When both μ and σ are unknown, we have considered four different spacings based on a complete sample and chosen the one yielding highest efficiency. A table of the efficiencies is also prepared. Finally we apply the above results for the estimation of the scale and/or shape parameters of the Weibull distribution.