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.     

A network isolation algorithm

A set of edges D called an isolation set, is said to isolate a set of nodes R from an undirected network if every chain between the nodes in R contains at least one edge from the set D. Associated with each edge of the network is a positive cost. The isolation problem is concerned with finding an isolation set such that the sum of its edge costs is a minimum. This paper formulates the problem of determining the minimal cost isolation as a 0–1 integer linear programming problem. An algorithm is presented which applies a branch and bound enumerative scheme to a decomposed linear program whose dual subproblems are minimal cost network flow problems. Computational results are given. The problem is also formulated as a special quadratic assignment problem and an algorithm is presented that finds a local optimal solution. This local solution is used for an initial bound.     

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.     

Assembly of systems having maximum reliability

The first problem considered in this paper is concerned with the assembly of independent components into parallel systems so as to maximize the expected number of systems that perform satisfactorily. Associated with each component is a probability of it performing successfully. It is shown that an optimal assembly is obtained if the reliability of each assembled system can be made equal. If such equality is not attainable, then bounds are given so that the maximum expected number of systems that perform satisfactorily will lie within these stated bounds; the bounds being a function of an arbitrarily chosen assembly. An improvement algorithm is also presented. A second problem treated is concerned with the optimal design of a system. Instead of assembling given units, there is an opportunity to “control” their quality, i.e., the manufacturer is able to fix the probability, p, of a unit performing successfully. However, his resources, are limited so that a constraint is imposed on these probabilities. For (1) series systems, (2) parallel systems, and (3) k out of n systems, results are obtained for finding the optimal p's which maximize the reliability of a single system, and which maximize the expected number of systems that perform satisfactorily out of a total assembly of J systems.     

Efficient computational devices for the capacitated transportation problem

This paper presents the details for applying and specializing the work of Ellis Johnson [10] and [11] to develop a primal code for the well-known capacitated transportation problem. The code was developed directly from the work of Johnson, but is similar to codes developed by Glover, Karney, Klingman, and Napier [6] and Srinivasan and Thompson [14]. The emphasis in the presentation is the use of the graphical representation of the basis to carry out the revised simplex operations. This is a means of exploiting the special structure and sparseness of the constraint matrix to minimize computational effort and storage requirements. We also present the results of solving several large problems with the code developed.     

On the set of (perfect) equilibria of a bimatrix game

This article provides a new approach to the set of (perfect) equilibria. With the help of an equivalence relation on the strategy space of each player. Nash sets and Selten sets are introduced. The number of these sets is finite and each of these sets is a polytope. As a consequence the set of (perfect) equilibria is a finite union of polytopes. © 1994 John Wiley & Sons. Inc.     

On the timing of adoption of multiproduct technologies

This article examines a game of multiproduct technology adoption. We consider a duopoly model in which firms choose when to switch from a traditional single-product technology to a more flexible and more expensive multiproduct technology. The multiproduct technology allows a firm to invade the other firm's market, creating a more competitive environment and reducing profits. We analyze this investment decision as a game of timing using two different equilibrium concepts. First, we utilize the “silent” equilibrium concept, where firms commit at time zero to a switching time. This concept would be applicable to situations where firms cannot observe each other's actions, or when the implementation of the technology requires long lead times and the investment decision is private information. Using this notion we find that both firms adopt the multiproduct technology simultaneously within a certain time interval. We then characterize this time interval in terms of cost and demand conditions. We also derive conditions under which sequential adoption of the multiproduct technology occurs. The second concept used is that of noisy equilibrium, where firms cannot precommit themselves to an adoption time. This concept is appropriate when investment decisions are common knowledge. In this case a firm can credibly threaten to immediately follow suit if the other firm decides to adopt. This threat is sufficient to ensure the collusive outcome where neither firm adopts the flexible technology. © 1994 John Wiley & Sons, Inc.