bluuebunny/crossref_metadata_2025 huggingface dataset:
Technical Note—Stronger Inequalities for 0-1 Integer Programming: Computational Refinements
Authors: Kianfar Ferydoon
Published: November 2008

This paper presents computational refinements to minimize the number of iterations involved in finding stronger cuts and constraints for 0-1 integer programming by the method presented in an earlier paper, “Stronger Inequalities for 0, 1 integer Programming Using Knapsack Functions.” We show that the savings in number of iterations between an optimally-sequenced cut-strengthening procedure and the procedure of the author's earlier paper can be very substantial. For example, for strengthening a cut with 200 0-1 variables this reduction can be 17,250 iterations.
Technical Note—Probability of Kill and Expected Destroyed Value if the Underlying Distributions Are Rotationally Symmetric
Authors: Schroeter Gerhard
Published: November 2008

We derive formulas for the probability of killing a point target and for the expected destroyed value of an area target when the value density function of the area target, the damage function, and the distribution of the center of damage function around the target center are rotationally symmetric. The result generalizes several well-known formulas.
Technical Note—The Shirt Allocation Problem
Authors: Gray Paul
Published: November 2008

A shirt manufacturer is given a total order by a multistore retailer and an allocation of shirts among stores. His problem is to determine how to distribute shirts to each store according to collar and sleeve size. The problem is formulated as an absolute value programming problem and practical methods for making allocations are presented.
Analytic Framework and Measurement Strategy for Investigating Optimal Staffing in Medical Practice
Authors: Smith Kenneth R. , Over A. Mead , Hansen Marc F. , Golladay Frederick L. , Davenport Esther J.
Published: November 2008

This paper presents the application of a mixed integer linear programming model to the choice of an optimal staff for an ambulatory medical care practice. Instead of adding further institutional and financial constraints to earlier models, this paper describes a strategy for the measurement of the key empirical constructs on which such analysis must rest. The analysis illustrates the use of the model for selecting the optimal staff and shows the relationships of this staff to the types of problems presented to the practice and the scale of activity. The effect of scale and patient mix on average cost per encounter are examined and the dual solution is used to determine the relative costs of producing encounters in the various groups. Finally, the allocation of responsibilities for different types of patient problems among the various members of the medical team is presented as part of the optimal solution.
Scheduling Nursing Personnel According to Nursing Preference: A Mathematical Programming Approach
Authors: Warner D. Michael
Published: November 2008

This paper describes a nurse scheduling system, the heart of which poses the scheduling decision as a large multiple-choice programming problem whose objective function quantifies preferences of individual nursing personnel concerning length of work stretch, rotation patterns, and requests for days off. The constraints provide for minimum numbers of nursing personnel of each skill class to be assigned to each day and shift of a four- or six-week scheduling period. The problem is solved by a modification of Balintfy and Blackburn's algorithm for multiple-choice programming problems. We include a description of the implementation of the scheduling system on nursing units of several hospitals.
A Two-Stage Optimization Model for In-Patient Transfers
Authors: Rabinowitz Manus , Dumas M. Barry , Valinsky David
Published: November 2008

A major problem in large urban hospitals is patient misplacement—the daily necessity of placing newly admitted patients in inappropriate beds because of varying demands, discharge patterns, and medical requirements. It is highly desirable to relocate as many misplaced patients as possible. Usually, transfers are arranged by comparing bed-vacancy lists with misplaced patient lists, a procedure that misses many transfer possibilities.

Initially, we formulated this problem as a linear program. However, because of problem size, solution on a daily basis is economically infeasible. We resolved this by reformulating the problem as a two-stage model. Aggregation is used for the first stage, taking advantage of the special structure of this linear program to form one of substantially reduced size. The second stage is a computerized search algorithm that disaggregates the first-stage optimal solution into the form required for its implementation by the hospital. A test run using actual hospital data demonstrates the model's effectiveness. Finally, we discuss plans for implementation.
Selecting Optimal Training Programs in a Hospital for the Mentally Retarded
Authors: Meredith Jack
Published: November 2008

This paper describes the development and application of a quantitative model to aid in selecting optimal training programs for mentally retarded children in a California state hospital. The model is a constrained version of R.A. Howard's Markov decision model. In this application five training programs are compared on a benefit-less-cost measure of performance. Tradeoffs between programs are found in terms of net benefit and annual cost to the hospital. The model is found to be additionally useful in evaluating contemplated new programs or modifications to existing programs where only their expected effects may be known.
Sequential Bounding of the Reliability of a Stochastic Network
Authors: Shogan Andrew W.
Published: November 2008

Given a directed source-sink network whose arcs either function or fail with known probabilities, we define the reliability of a node as the probability that there exists a path from the network's source to the node that consists only of functioning arcs. The concept of the strongly connected components of a network and the theory of associated random variables enable us to develop an algorithm that sequentially computes upper bounds on the reliabilities of nodes of the network until we finally obtain an upper bound on the reliability of the network's sink. The construction of a dual of the stochastic network permits the calculation of a lower bound on the reliability of the sink. These bounds are shown analytically to be tighter than the existing Esary-Proschan bounds.
Technical Note—Shortest-Path Algorithms: A Comparison
Authors: Golden Bruce
Published: November 2008

In this note we present some computational evidence to suggest that a version of Bellman's shortest-path algorithm outperforms Treesort-Dijkstra's for a certain class of networks.
Mathematical Models for Economic and Political Advertising Campaigns
Authors: Shane Harold D.
Published: November 2008

We propose a basic model for a two-competitor advertising campaign. Game-theoretic saddle-point solutions are found for the following four problems. How large should the total advertising budget be to maximize profits? How should the budget be distributed in a differentiated market, and how much is saved by this distribution? How should one distribute advertising dollars in order to maximize one's expected total number of votes on a political campaign? How should one allocate expenditures over time in order to maximize one's expected number of votes at election day? Finally, the model is tested against empirical data from actual election campaigns and is found to yield a very high correlation between actual and predicted behavior.
Two Queues in Tandem Attended by a Single Server
Authors: Taube-Netto Miguel
Published: November 2008

This paper considers two service stages in tandem with infinite queue capacity in front of each stage. There is a single server who performs the service in both stages by switching from one stage to the other when the number of customers in the active stage reaches the value zero. The arrival process is assumed to be Poisson and the service processes are independent renewal processes. The state probabilities are obtained in the steady-state case. In addition (for the steady-state case), the Laplace-Stieltjes transform is obtained for the time a customer waits until the beginning of service in each stage, for the busy period of the server, and for the busy period of each stage.
Technical Note—Column Dropping in the Dantzig-Wolfe Convex Programming Algorithm: Computational Experience
Authors: O'Neill Richard P.
Published: November 2008

This paper presents some computational experience on column dropping using the Dantzig-Wolfe convex programming algorithm. Computational results show virtually no difference in the measures of computational efficiency when all columns are retained and when only basic columns are retained.
Technical Note—On Sensitivity Analysis in Geometric Programming
Authors: Dinkel John J. , Kochenberger Gary A.
Published: November 2008

This note develops efficient sensitivity procedures for posynomial geometric programs. These procedures provide ranging information for the primal coefficients, means for dealing with problems with loose primal constraints, and an incremental procedure for improving the estimated solutions. These sensitivity procedures are independent of the method of solution of the geometric program.
Technical Note—Comparison between Two Dynamic Perishable Inventory Models
Authors: Nahmias Steven
Published: November 2008

Two apparently different inventory models for describing optimal ordering policies for a fixed life commodity have been developed by Fries and Nahmias. This note considers the relationship between these models. Our main result is that the optimal policies for Fries' model and a discounted version of Nahmias' are identical when the remaining number of periods in the horizon exceeds the product lifetime in periods. We also discuss the relevance of these results to the computation of an approximate critical number policy developed elsewhere.
A Condensation Algorithm for a Class of Algebraic Programs
Authors: Avriel Mordecai , Gurovich Victoria
Published: November 2008

We present a class of algebraic programs, illustrated by examples in optimal location-allocation problems, discrete approximations, and multiplier methods. This class can be characterized by objective and constraint functions consisting of absolute values of rational functions of posynomials raised to positive powers. Next, we derive an algorithm consisting of monomial condensations and cutting planes, extending the Avriel-Williams complementary geometric programming method.
Optimal Control of Discrete and Continuous Time Maintenance Systems with Variable Service Rates
Authors: Winston Wayne
Published: November 2008

A maintenance system consists of o finite number of machines and a single-server repair facility that may be operated at several rates. Machines are subject to failure and machines that fail are sent to the repair facility. Under the assumption that costs depend on the repair rate and lost production, we derive conditions that ensure that, for a discrete time maintenance system, the optimal repair rate is a non-increasing function of the number of machines in good condition. By considering a continuous time maintenance system as a limit of a sequence of discrete time maintenance systems, we derive analogous conditions that ensure that the optimal repair rate for the continuous time maintenance system is a non-increasing function of the number of machines in good condition.
Analysis and Design of Loop Service Systems via a Diffusion Approximation
Authors: Fischer M. J.
Published: November 2008

In a loop service system the server cyclically serves a fixed number of peripheral stations. In this paper we consider an operating rule where the server is allowed to service a particular station for a fixed length of time each cycle. Using a diffusion approximation, we obtain expressions for the distribution of the steady state load as well as the expected waiting time at a particular peripheral station. These results are then used to determine the optimal design for the system under a linear cost structure.
Conservation Equations and Their Application to Queuing Simulations
Authors: Law Averill M.
Published: November 2008

In this paper we continue our study of efficient estimators for simulated queuing systems. We previously showed that it is more efficient to estimate the first moments of all the usual measures of performance from an estimate of mean wait in queue than to estimate them directly. Here we derive some new conservation equations that are then used to obtain efficient estimators of the variances of the usual measures of performance. We also introduce an estimator that is more efficient than the usual estimator for the probability that an arriving customer is blocked.
On a Linear Programming Technique for the Steady-State Behavior of Some Queuing Systems
Authors: Kotiah T. C. T.
Published: November 2008

We consider the class of stationary queuing processes whose behavior can be described by a system of difference equations that are linear in the probabilities of the states. We describe a linear programming technique that will provide bounds of any prescribed degree of accuracy for any steady-state quantity expressible linearly in terms of the probabilities. For some queues a standard technique such as the use of generating functions may require a lengthy analysis and may not provide a check on the results. In contrast, the proposed technique is always easy to implement on a computer and, in a certain sense, is self-checking. Illustrative examples are given. The technique is implemented through an algorithm that, as shown by the examples, may give useful results after only a few iterations. We prove that the probability of zero delay for the M/D/2 queue is larger than that for an M/M/2 queue with the same traffic intensity. For a large class of parameter values of the multi-server mixed queue we obtain, with very little computing time, sharp bounds for the average queue size.
Technical Note—Minimizing Cost to Maintain a Steady-State Growth Rate in a Population
Authors: Parker Rodger
Published: November 2008

An approach for estimating the minimum cost of holding a specified steady-state growth rate for a population is given. The behavior of the population is described by a constant “population matrix.” The components of the state vector are the number of women in various age intervals. All age intervals are of equal length and equal to the length of the fundamental time period. Within each age bracket we assume that the fraction of women using birth-control devices is the controllable variable and that the cost depends linearly on the number of women using the devices.
Error Bounds and the Applicability of the Greedy Solution to the Coin-Changing Problem
Authors: Tien B. N. , Hu T. C.
Published: November 2008

Necessary and sufficient conditions have been given that characterize the data for which a greedy algorithm solves the coin-changing problem. In this paper we study the problem of maximum percentage error when the greedy solution does not work. We also generalize a result of Johnson and Kernighan to the case for which each coin is of different weight.
A Characterization of Stability in Linear Programming
Authors: Robinson Stephen M.
Published: November 2008

We prove that a necessary and sufficient condition for the primal and dual solution sets of a solvable, finite-dimensional linear programming problem to be stable under small but arbitrary perturbations in the data of the problem is that both of these sets be bounded. The distance from any pair of solutions of the perturbed problem to the solution sets of the original problem is then bounded by a constant multiple of the norm of the perturbations. These results extend earlier work of Williams.
The Use of Decomposition in the Optimal Design of Reliable Systems
Authors: Butler David A.
Published: November 2008

The optimal design problem is to minimize the cost of a system of independent components subject to a lower bound constraint on the system reliability, and upper and lower bounds on the component reliabilities. This problem can be extremely difficult to solve for an arbitrary system, but for the rather general class of S-P systems, the optimal design problem can often be solved via a decomposition of the system structure. From this decomposition there arises a sequence of parallel and series optimal design subproblems that are parametric in the lower bound on the subsystem reliability. Given appropriate assumptions about the input data, these parallel and series subproblems can be easily solved. However, since the parametric solution of one subproblem is typically used as part of the data for a higher-level subproblem, the behavior of these parametric solutions must be investigated. We give conditions that ensure that the overall optimal design problem can be solved.
Determining the Class of Payoffs That Yield Force-Level-Independent Optimal Fire-Support Strategies
Authors: Taylor James G.
Published: November 2008

By considering a specific problem, this paper examines the dependence of the structure of optimal time-sequential combat strategies on the quantification of military objectives. The paper determines the class of terminal payoffs that yield force-level-independent (i.e., state-variable-independent) optimal strategies to the fire-support differential game of Kawara. The functional form of payoffs that yield state-variable-independent optimal strategies to this Lanchester-type differential game is shown to be determined by a linear first-order partial differential equation. Kawara's main result was that the time at which an optimal strategy tells one to switch from concentrating all supporting fires on enemy artillery to all on enemy infantry does not depend on the force levels (provided that neither side's supporting units can be all destroyed before a certain time). This paper shows that Kawara chose essentially the only type of payoff that yields his main result. Furthermore, the structure of the optimal time-sequential fire-support strategies is shown to depend on the quantification of infantry force superiority in the model, with seemingly equivalent measures of force superiority yielding different structures for the optimal strategies.
Technical Note—A Special Case of the Transportation Problem
Authors: Chandrasekaran R. , Rao S. Subba
Published: November 2008

We consider a special case of the transportation problem with 3 supply points and n demand points. An efficient algorithm is provided and the problem is illustrated with an example concerning financial aid to students.
Higher-Order Approximations for the Perishable-Inventory Problem
Authors: Nahmias Steven
Published: November 2008

Computation of an optimal policy for ordering a perishable commodity with a fixed lifetime of m periods requires the solution of a dynamic program whose state variable has dimension m − 1. Unless m is small, the computations quickly become unreasonable. By bounding the expected outdating function and using an approximate transfer function, we obtain an approximation of the original problem that can be computed as if the lifetime were r < m periods. When r = 2, it is demonstrated under reasonable assumptions that the appropriate function to be minimized each period is quasi-convex. We include computations that compare this approximation to both the optimal policy and a critical number approximation.
Technical Note—Some Examples Concerning Linear Continuity of Solutions to Programming Problems
Authors: Hazewinkel Michiel
Published: November 2008

In this note we construct some counterexamples concerning upper semicontinuity and linear upper and lower semicontinuity of the solution sets and ϵ-solution sets of nonlinear programming programs: max f(x), subject to g(x) ≦ b. These examples answer some of the questions in a recent paper by Stern and Topkis.
Technical Note—Using a Monte Carlo Method for Optimizing Smoothed Functional
Authors: Rubinstein Y.
Published: November 2008

This note deals with optimization problems involving insufficient a priori information on the controlled object. We consider a parametric statistical gradient algorithm that uses an increasing number of observations and gives convergence conditions for optimizing a smoothed functional.
A General Algorithm for One-Dimensional Knapsack Problems
Authors: Ingargiola Giorgio P. , Korsh James F.
Published: November 2008

This paper presents a reduction algorithm and a branch-search algorithm that, in sequence, allow the solution of sizeable problems of the form: maximize ∑i=1Ncixi, subject to ∑i=1Nlixi ≦ s and 0 ≦ xi ≦ bi and integer, 1 ≦ i ≦ N. The reduction algorithm is proportional to N in space and proportional to N ∑i=1Nbi in time. The branch-search algorithm's space requirement is linear in N. Computational experience with these algorithms is presented.
A Simplex-Like Algorithm for the Continuous Modular Design Problem
Authors: Shaftel Timothy L. , Thompson Gerald L.
Published: November 2008

This paper derives an efficient solution procedure for solving the continuous version of the Evans modular design problem. The Kuhn-Tucker conditions are used to derive a dual problem that can be solved easily and whose dual variables indicate which equations should be tight. The technique retains a free-basic solution throughout so that fast solution routines can be employed that are quite similar to those for transportation problems. Computational experience shows that this technique works well on very large problems. We therefore have provided a solution technique for solving a nonlinear problem that has applications to various aspects of the design process.
Technical Note—An Inequality for the Variance of Waiting Time under a General Queuing Discipline
Authors: Vasicek Oldrich A.
Published: November 2008

We show that the expected value of any convex function of the waiting time (such as the variance) in a general queuing system under any queuing discipline independent of the service times does not exceed that under the last-come-first-served discipline, and is not less than that under the first-come-first-served discipline.
Coalitional and Chance-Constrained Solutions to n-Person Games, II: Two-Stage Solutions
Authors: Charnes A. , Granot Daniel
Published: November 2008

We extend the theory of n-person cooperative games in characteristic function form to games with stochastic characteristic functions. We propose a payoff process to the players in these games that is composed of two parts. In the first part the players are promised some prior payoffs. In the second part we use the two-stage solution concepts to modify the prior payoffs in a manner acceptable to the players. We verify the existence of these solution concepts and explore some of their properties.
Structure of Optimal Policies in Complex Queuing Systems
Authors: Albright S. Christian
Published: November 2008

This paper examines a class of M/G/S queuing reward systems with heterogeneous servers and heterogeneous customers. With the help of two simple results, we show that the policy that maximizes average reward per unit time over an infinite horizon possesses a certain structured form, which for several examples is quite intuitive and for others is not so intuitive. We also show that when the policy improvement method is used to find the optimal policy, only policies with the structured form need be considered, an obvious computational simplification. Computational results are discussed briefly.
Errata
Authors: Ziemba W. T.
Published: November 2008

Erratum to Huang, C. C., W. T. Ziemba, A. Ben-Tal. 1977. Bounds on the expectation of a convex function of a random variable: with applications to stochastic programming. Opns. Res. 25 315–325.
On a Real-Time Scheduling Problem
Authors: Dhall Sudarshan K. , Liu C. L.
Published: November 2008

We study the problem of scheduling periodic-time-critical tasks on multiprocessor computing systems. A periodic-time-critical task consists of an infinite number of requests, each of which has a prescribed deadline. The scheduling problem is to specify an order in which the requests of a set of tasks are to be executed and the processor to be used, with the goal of meeting all the deadlines with a minimum number of processors. Since the problem of determining the minimum number of processors is difficult, we consider two heuristic algorithms. These are easy to implement and yield a number of processors that is reasonably close to the minimum number. We also analyze the worst-case behavior of these heuristics.
The Single-Plant Mold Allocation Problem with Capacity and Changeover Restrictions
Authors: Love Robert R. , Vemuganti R. R.
Published: November 2008

This paper presents a formulation and a solution technique for a class of production scheduling problems. Plant capacity limitations and changeover restrictions characterize the problems in this class. A member of this class, called the single-plant mold allocation problem, is formulated as a linear integer programming problem. We develop a transformation that permits the reduction of this problem to a minimum cost flow problem.
Technical Note—Three-Stage Flow-Shops with Recessive Second Stage
Authors: Burns Fennell , Rooker John
Published: November 2008

Several papers have described special structural properties for which the minimum makespan flow-shop problem can be efficiently solved. We describe a new special case of the 3 × n problem with small second-stage processing times relative to the first and third stages for which Johnson's algorithm gives an optimal schedule.
A General Bounding Scheme for the Permutation Flow-Shop Problem
Authors: Lageweg B. J. , Lenstra J. K. , Rinnooy Kan A. H. G.
Published: November 2008

Branch-and-bound methods are commonly used to find a permutation schedule that minimizes maximum completion time in an m-machine flow-shop. In this paper we describe a classification scheme for lower bounds that generates most previously known bounds and leads to a number of promising new ones as well. After a discussion of dominance relations within this scheme and of the implementation of each bound, we report on computational experience that indicates the superiority of one of the new bounds.
Using Simulation to Develop and Validate Analytic Models: Some Case Studies
Authors: Ignall Edward J. , Kolesar Peter , Walker Warren E.
Published: November 2008

Simulation models are generally costly tools to use in systems analyses. Whenever applicable, a simple analytic model is preferable. However, in many cases the conditions assumed by solvable analytic models do not hold in the real world; hence an analyst would hesitate to use them. A simulation can be used to suggest an appropriate approximate model and to determine how good an approximation a given analytic model is. We show how simulations of New York City's fire and police operations have been used to develop and validate simple analytic models that are now being used to analyze the deployment of resources in these two services.
Approximate Transient Analysis of Some Queuing Systems
Authors: Kotiah T. C. T.
Published: November 2008

We propose approximations for the time-dependent queue size distribution Pn(t) and the mean queue size E[X(t)] of an M/M/1 queue. With a Laplace transform-generating function technique, the exact analysis involves the complex root u* inside the unit circle of a certain quadratic. The exact value of u* leads to transforms that, when inverted, yield rather complicated expressions for Pn(t) and E[X(t)]. We discuss three iterative procedures that give successive rational approximations for u*. These approximations yield, for the queue size distribution and the mean queue size, approximate transforms that are rational and easier to invert. We obtain sharp bounds for Pn(t) and E[X(t)] for a wide range of parameter values by performing the second iteration and combining the approximate results given by the iterative procedures.

The methods can be applied to approximate the behavior of more complicated queues. Applications to the M/M/2 queue and the M/Ep/1 queue are discussed briefly.
Technical Note—On the Expected Performance of Branch-and-Bound Algorithms
Authors: Lenstra J. K. , Rinnooy Kan A. H. G.
Published: November 2008

For many combinatorial optimization problems, the use of enumerative solution methods exhibiting a superpolynomial worst-case behavior seems unavoidable. It is therefore of interest to investigate the expected behavior of such methods. Polynomial-bounded expected performance has been claimed by Bellmore and Malone for their traveling salesman algorithm. The purpose of this brief note is to point out some inadequacies of their proof.
Technical Note—Accelerated Computation of the Expected Discounted Return in a Markov Chain
Authors: Porteus Evan L. , Totten John C.
Published: November 2008

This note investigates the use of extrapolations with certain iterative methods to accelerate the computation of the expected discounted return in a finite Markov chain. An easily administered algorithm for reordering the equations allows an attractive stopping rule to be used with Gauss-Seidel iteration. Lower bound and norm reducing extrapolations are introduced. Certain of these extrapolations that are optimal are easily computed. From the results of a small numerical example, it appears that the effects of reordering can be dramatic. Some form of extrapolation with Gauss-Seidel iteration after reordering may turn out to be more efficient in practice than successive over-relaxation.
Technical Note—An Implementation of Surrogate Constraint Duality
Authors: Dinkel John J. , Kochenberger Gary A.
Published: November 2008

This paper presents an implementation of surrogate constraint duality in mathematical programming. Motivated by the use of linear programming duality for surrogate constraints in integer linear programs, this implementation is based on geometric programming duality. As a result of this formulation we are able to present an algorithm for surrogate constraint duality and discuss several important properties of the algorithm.
Testing the Accuracy, Usefulness, and Significance of Probabilistic Choice Models: An Information-Theoretic Approach
Authors: Hauser John R.
Published: November 2008

Disaggregate demand models predict the choice behavior of individual consumers. But while such models predict choice probabilities (0 < p < 1), they must be tested against (0, 1) choice behavior. This paper uses information theory to derive three complementary tests that help analysts select a “best” disaggregate model. “Usefulness” measures the percentage of uncertainty (entropy) explained by the information the model provides. It provides theoretic rigor and intuitive appeal to the commonly used likelihood ratio index and leads to important practical extensions. “Accuracy” is a new two-tailed normal test that determines whether the (0, 1) observations are reasonable under the hypothesis that the model is valid. “Significance” is the standard chi-squared test to determine whether a null model can be rejected. This paper also extends the information test to examine the relationships among successively more powerful null hypotheses. For example, in a logit model one can quantify (1) the contribution due to knowing aggregate market shares, (2) the incremental contribution due to knowing choice set restrictions, and (3) the final incremental contribution due to the explanatory variables. Further extensions provide “explanable uncertainty” measures applicable if choice frequencies are observed. Market research and transportation analysis empirical examples are given.
Some Examples of Difficult Traveling Salesman Problems
Authors: Papadimitriou C. H. , Steiglitz K.
Published: November 2008

We construct instances of the symmetric traveling salesman problem with n = 8k cities that have the following property: There is exactly one optimal tour with cost n, and there are 2k−1(k − 1)! tours that are next-best, have arbitrarily large cost, and cannot be improved by changing fewer than 3k edges. Thus, there are many local optima with arbitrarily high cost. It appears that local search algorithms are ineffective when applied to these problems. Even more catastrophic examples are available in the non-symmetric case.
Protective Planning-Horizon Procedures for a Deterministic Cash Balance Problem
Authors: Mensching J. , Garstka S. , Morton T.
Published: November 2008

The simple cash balance problem is to determine the timing, direction, and magnitude of transfers between a firm's earning asset (e.g., bonds) and cash balance. Recently, Blackburn and Eppen developed a forward algorithm and limited planning horizon results for a dynamic, deterministic, discrete-time version of this problem. They were able to obtain planning horizons only if an optimal plan for some subproblem included conversion of bonds to cash in the final period and a certain condition on demand was fulfilled. We derive much more general planning horizon results—the transaction is allowed to be conversion of cash to bonds, it need not be in the final period, and the special condition on demand need not be fulfilled. The methodology used is an extension of that developed by Lundin and Morton for the ordinary dynamic lot-size model. Under mild restrictions the planning-horizon procedures derived here can also be shown to be “protective”; that is, any occurring planning horizon will eventually be detected.
Data Structures and Computer Science Techniques in Operations Research
Authors: Fox B. L.
Published: November 2008

We discuss some important data structures and computer science techniques, and their applications to operations research problems. The purpose of our discussion of applications, some of which are novel, is to stimulate further reading, for which adequate references are given. The techniques that we discuss are among the most important, but many valuable ones had to be omitted.
Bin Packing with Geometric Constraints in Computer Network Design
Authors: Chandra A. K. , Hirschberg D. S. , Wong C. K.
Published: November 2008

We consider the bin-packing problem with the constraint that the elements are in the plane, and only elements within an oriented unit square can be placed within a single bin. The elements are of given weights, and the bins have unit capacities. The problem is to minimize the number of bins used. Since the problem is obviously NP-hard, no algorithm is likely to solve the problem optimally in better than exponential time. We consider an obvious suboptimal algorithm and analyze its worst-case behavior. It is shown that the algorithm guarantees a solution requiring no more than 3.8 times the minimal number of bins. We can show, however, a lower bound of 3.75 in the worst case. We then generalize the problem to arbitrary convex figures and analyze a class of algorithms in this case. We also consider a generalization to multidimensional “bins,” i.e., the weights of points in the plane are vectors, and the capacities of bins are unit vectors.
Automatic Categorization of Optimization Problems: An Application of Computer Symbolic Mathematics
Authors: Stoutemyer David R.
Published: November 2008

This paper describes a computer program that accepts as input a symbolic mathematical statement of an arbitrary mathematical programming problem, placing the problem into none or at least one of the categories: linear, quadratic, separable, posynomial, signomial, or convex. This categorization program is intended to reveal properties that can be exploited by special-purpose numerical computer programs—properties that might easily be overlooked because of the size of the problem, the complexity of the problem, or the limited knowledge of a novice who wishes to solve an optimization problem. The paper includes a brief demonstration of the program, a discussion of the underlying techniques, and a summary of the performance for some large problems.
A Performance Model for Computer Data-Base Reorganization Performed Concurrently with Usage
Authors: Sockut Gary H.
Published: November 2008

Characteristics of data bases, reorganization, concurrent reorganization, and data-storage devices are described briefly. We present a two-priority queuing model for concurrent reorganization and usage and derive and solve equations for steady-state expectations of user response time and the time required to perform reorganization. Numerical results are obtained, and performance characteristics of such a system are predicted quantitatively. We discuss the effect of parameter values on performance and predict that for typical values of the model's parameters, system performance will be at an acceptable level.
Toward an Optimal Design of a Network Database from Relational Descriptions
Authors: De Prabuddha , Haseman William D. , Kriebel Charles H.
Published: November 2008

This paper suggests a method for building up a network database starting from relational descriptions. The network generated is optimal in terms of data item appearances and, given that, it is also optimal in terms of the number of records. Moreover, it preserves third normality, in case we start with third-normal relations. We develop a model for implementing the network that guarantees the minimality of the sum of storage and access costs. We show that the model can be solved efficiently.
A Combinatorial Approach to Dynamic Scheduling Problems
Authors: Su Zaw-Sing , Sevcik Kenneth C.
Published: November 2008

We introduce a combinatorial approach for studying multiple-processor scheduling problems that involve the preemptive scheduling of independent jobs. Unlike most combinatorial models used for studying scheduling problems, ours assumes that jobs arrive over time but that scheduling decisions must be made without knowledge of what jobs will arrive in the future. We seek dynamic algorithms that make scheduling decisions based on changing information. An algorithm is considered to be “optimal” only if it consistently produces schedules no worse than those produced by any omniscient algorithm that has exact knowledge of attributes of all jobs in advance. Measures of performance examined include the maxima and means of completion time, flow time, and lateness. “Optimal” algorithms are established in a few cases, while it is determined in other cases that such “optimal” algorithms require more information than the model provides.
A Probabilistic Model of Winners' Outs versus Losers' Outs Rules in Basketball
Authors: Albright S. Christian , Winston Wayne
Published: November 2008

We examine what happens to the game of basketball when one of the principal rules is changed. When a team scores a basket, we assume this team receives the ball on the next possession, a rule we call “winners' out.” This is, of course, the opposite of the usual “losers' outs” rule, where the opposite team receives the next possession. The implications of this rule are studied in the game where the first team to score a certain number of points wins and also in the game where the team that is ahead at the buzzer wins. In both games the main result, surprisingly, is that the probability that a given team wins remains essentially constant under the two sets of rules. That is, neither team should really care which set of rules is in effect.
Technical Note—Some Simpler Bounds on the Mean Queuing Time
Authors: Marchal William G.
Published: November 2008

This note presents a general lower bound for the mean queuing time in a stationary GI/G/c queue. It also discusses the application of the bound to an M/G/c system and the general areas of usefulness.
A Mathematical Model Used to Analyze Breast Cancer Screening Strategies
Authors: Shwartz Michael
Published: November 2008

A mathematical model of breast cancer is developed and used to evaluate the benefits of screening for breast cancer. This model consists of hypotheses concerning the age-specific incidence of the disease, the rate of disease progression, the tendency of the disease to be detected without benefit of scheduled screening examinations, and prognosis related to the extent of disease progression at treatment. We formulate these hypotheses quantitatively and estimate parameters by fitting the model statistically to published data on breast cancer. Model predictions are independently validated by comparison with data from breast cancer screening programs. On the basis of the model, we calculate the benefits of screening under alternative assumptions about the woman screened, the number of screens given, the ages at which the screens are given, the reliability of the screening technique, and the rate of disease progression. These calculations are then used to consider questions concerning the design of breast cancer screening strategies.
Internal Telephone Billing Rates—A Novel Application of Non-Atomic Game Theory
Authors: Billera Louis J. , Heath David C. , Raanan Joseph
Published: November 2008

We consider the problem of determining rates for a situation in which services are purchased in bulk but have to be paid for by a large number of small users. The desired rates must be “fair” and they must cover all costs. The problem is formulated as a non-atomic game and solved by using the value of the game. In addition to the general problem, we present a detailed actual case, together with computational methods and results.
Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
Authors: Denardo Eric V. , Fox Bennett L.
Published: November 2008

We present a new family of shortest-route methods, which reduce an upper bound on running time, and make empirical comparisons for a certain class of networks. These methods also allow for exploitation of structure by pruning arcs and/or nodes.
Technical Note—The Busy Probability in M/G/N Loss Systems
Authors: Kaufman J. S.
Published: November 2008

If K + 1 servers in an equilibrium M/G/N-loss system are chosen randomly without replacement and the first K servers chosen are busy, the conditional probability that the (K + 1)st server chosen is busy is shown to be equal to the a priori probability that a randomly chosen server in an equilibrium M/G/(N − K)-loss system (with the same offered load) is busy.
The Sharing Problem
Authors: Brown J. Randall
Published: November 2008

Many important problems are concerned with the equitable distribution of resources. A new approach to resource distribution problems is presented as a network flow problem with a maximum objective function. The value of the smallest linear tradeoff function at the terminal points in a capacitated network is maximized. We develop a polynomially bounded algorithm and give computational experience. We illustrate the importance and usefulness of the sharing-problem model by considering the equitable distribution of coal during a prolonged coal strike.
Technical Note—On the Estimation of Convex Functions
Authors: Holloway Charles A.
Published: November 2008

We consider the estimation of a convex or concave relationship from a set of limited observations without prior specification of a functional form. A concave programming problem is shown to provide a “best” estimate for an arbitrary norm and n independent variables. The problem is shown to be well suited to a solution using the computational strategy of relaxation (a variant of generalized programming). An example illustrates the procedure and demonstrates the relationship to a procedure for n = 1 suggested by Dent.
Technical Note—Bibliography of Operations Research in Health-Care Systems: An Update
Authors: Fries Brant E.
Published: November 2008

This bibliography augments that published in Operations Research in September 1976 and brings it current to January 1978. We present a total of 154 new references, all concerning health applications of operations research.
Solving Nonlinear Programs Without Using Analytic Derivatives
Authors: May Jerrold H.
Published: November 2008

A new algorithm for the minimization of a nonlinear function subject to linear inequality constraints is presented. It is an extension of Mifflin's local variations-approximate Newton nonderivative method for unconstrained minimization. At each iteration, the algorithm approximates first and second partial derivatives by differencing function values at feasible points along directions that are determined from a factorization of the currently active constraint matrix. Accumulation points of the algorithm satisfy the Karush-Kuhn-Tucker first order necessary optimality conditions if the objective function is continuously differentiable and appropriately bounded. Under stronger assumptions, every accumulation point of the algorithm also satisfies second-order-necessary optimality conditions. The rate of convergence of the algorithm is super-linear when the function is twice continuously differentiable and there is a unique accumulation point satisfying second order sufficiency conditions. A computer code for the algorithm is described and computational results on a substantial set of test problems included.
On the Storage and Handling of Binary Data Using FORTRAN with Applications to Integer Programming
Authors: Graves Joseph S.
Published: November 2008

Most integer programming algorithms involve at least some binary data handling, e.g., set membership, intersection, and union. This paper presents some of the important concerns involved in implementation. When the algorithms are coded for the computer an effort is sometimes made to take advantage of the basic binary configuration of the digital computer to aid in the storage and handling of such data. In the past this has meant the use of assembly language subroutines. This paper demonstrates a procedure for achieving the same objectives in the main program using FORTRAN. The obvious advantage of the procedure is the elimination of the several storage and retrieval operations for register values as the program shifts control from the main routine to the subroutine and back again. Of particular interest are (1) the use of the computer arithmetic to achieve the relative complement operation and (2) the importance of additional savings due to overhead reduction when bit storage is used. Computational results are presented comparing various regimes for storing and handling binary data. In addition, an analytic procedure for comparing the storage requirements and execution times of different data structures is demonstrated for a particular integer programming application. This paper should serve as a useful tutorial for anyone developing and/or implementing integer programming algorithms.
Shortest-Route Methods: 2. Group Knapsacks, Expanded Networks, and Branch-and-Bound
Authors: Denardo Eric V. , Fox Bennett L.
Published: November 2008

This paper contains new, fast methods for handling two types of group knapsack networks—those having only unbounded variables and those having some bounded variables. The latter are embedded in a new branch-and-bound scheme for pure integer programs. This implicit enumeration scheme is nonredundant, which distinguishes it from the literature.
A Heuristic Branch-and-Bound Algorithm for Telephone Feeder Capacity Expansion
Authors: Freidenfelds John , McLaughlin C. D.
Published: November 2008

We present an adaptation of a branch-and-bound solution approach for the problem of expanding the capacity of a telephone feeder cable network to meet growing demand. We drastically trim the search by generating “heuristic” bounds, based on “analytic” solutions of simpler capacity expansion problems. Although we have thus sacrificed a guarantee of exact optimality, we obtain very good solutions with far less computation than would otherwise be possible. Computational efficiency is important because the algorithm is implemented in a computer program that is used routinely, both in “batch” and “time-share” versions, by telephone company planners and engineers. We believe that this approach of using the flexibility of a branch-and-bound formulation, along with specialized heuristics to limit the search, can provide a practical compromise between a “pure” search for an exact optimum and a “no search” use of a heuristic alone