bluuebunny/crossref_metadata_2025 huggingface dataset:
Intensity Measures of Consumer Preference
Authors: Hauser John R. , Shugan Steven M.
Published: November 2008

To design successful new products and services, managers need to measure consumer preferences relative to product attributes. Many existing methods use ordinal measures. Intensity measures have the potential to provide more information per question, thus allowing more accurate models or fewer consumer questions (lower survey cost, less consumer wearout). To exploit this potential, researchers must be able to identify how consumers react to these questions and must be able to estimate intensity-based preference functions. This paper provides a general structure for using intensity measures for estimating consumer preference functions. Within the structure: (1) alternative measurement theories are reviewed, (2) axioms for developing testable implications of each theory are provided, (3) statistical tests to test these implications and distinguish which theory describes how consumers are using the intensity measures are developed, (4) functional forms appropriate for the preference functions implied by each theory are derived, and (5) procedures to estimate the parameters of these preference functions are provided. Based on these results, a practical procedure, implemented by an interactive computer package, to measure preference functions in a market research environment is developed. An empirical case illustrates how the statistical tests and estimation procedures are used to aid in the design of new telecommunications devices. Empirical results suggest the majority of consumers can provide intensity judgments. The intensity-based estimation procedures do better on several criteria than ordinal estimation.
Experimentation and Budgeting in Advertising: An Adaptive Control Approach
Authors: Pekelman Dov , Tse Edison
Published: November 2008

This paper demonstrates how a general adaptive control scheme combines experimentation in advertising levels, estimation of sales advertising relationships, and the determination of advertising budgets. Various assumptions of current practices in experimentation and estimation are discussed and it is shown how these can be improved. A set of equations describing the sales-advertising system is proposed, its stochastic nature is analyzed, and an algorithm for calculating the adaptive control policies for this system is developed. To test the performance of the adaptive control scheme, the system is simulated under various conditions which include constant parameters, parameters which are varying over time, different initial estimates, and noise levels. Simulations of actual markets are then run and the amount of learning obtained by the adaptive control scheme is analyzed. Various extensions which can be easily incorporated in the general adaptive control scheme are specified.
Waiting Time in an S − 1, S Inventory System with Arbitrarily Distributed Lead Times
Authors: Kruse W. Karl
Published: November 2008

The customer waiting time distribution is derived for an S − 1, S continuous review inventory system experiencing Poisson demands and general independent identically distributed lead times. The analysis uses results from the infinite server Poisson queue. Some comparisons are made with an approximation to the waiting time distribution due to Higa et al.
Optimal Ordering Policies for Continuous Review Perishable Inventory Models
Authors: Weiss Howard J.
Published: November 2008

This paper extends the notions of perishable inventory models to the realm of continuous review inventory systems. The traditional perishable inventory costs of ordering, holding, shortage or penalty, disposal and revenue are incorporated into the continuous review framework. The type of policy that is optimal with respect to long run average expected cost is presented for both the backlogging and lost-sales models. In addition, for the lost-sales model the cost function is presented and analyzed.
Generalized Value Bounds and Column Reduction in Finite Markov Decision Problems
Authors: Vickson R. G.
Published: November 2008

Generalized value-function bounds are developed for a class of value-iteration methods in finite state and action Markov decision problems. The bounds are applicable to either discounted total value problems, or to undiscounted total value problems for absorbed processes which are multistage contracting. Some effects of Porteus' column reduction transformation on value-function bounds are studied. It is shown that column reduction tightens the bounds but does not accelerate their asymptotic rate of convergence. Explicit formulas are given for the value bounds obtained through column reduction, thus eliminating the need for performing the transformation.
The Expected Value of Perfect Information in Facility Location
Authors: Drezner Z. , Wesolowsky G. O.
Published: November 2008

This paper is concerned with finding the expected value of perfect information (EVPI) in a simple facility location problem where the weights, which summarize cost and volume parameters, are random draws from a multivariate probability distribution. A model with rectangular distances and one with squared Euclidean (center of gravity) are used. The analysis is developed for a multivariate normal distribution of weights but simulation is used to show that the expressions derived are reasonably accurate for other distributions (the EVPI for the multivariate lognormal distribution is illustrated).
Feature Article—Research Portfolio for Inventory Management and Production Planning Systems
Authors: Wagner Harvey M.
Published: November 2008

This paper provides a nontechnical survey of the status of inventory management systems. The central theme is an enumeration of practical problems that need research and analytic attention. These problems arise in the diagnostic, design, system performance forecasting, and implementation phases of real-life inventory management improvement projects. The paper describes many of the detailed aspects of such projects, and discusses where operations research has not yet provided sufficient scientific foundation to judge the merit of pragmatic alternatives for dealing with these problems.
Equity and Public Risk
Authors: Keeney Ralph L.
Published: November 2008

Possible fatalities to members of the public are defined in this paper as public risk. Given other things are equal, such as the benefits to individuals in society, there may be a preference for an equitable balancing of individual risks. This concept of equity is defined and it is shown that any utility function over number of fatalities which exhibits this equity condition must be risk prone. Commonly used indicators, such as the average risk per person and the expected number of fatalities, do not promote equity. An attitude of aversion toward catastrophes is defined and shown to conflict with risk equity.
Artificial Inflation of a Delinquency Rate by a Selection Artifact
Authors: Maltz Michael D. , Pollock Stephen M.
Published: November 2008

Cohorts of youths sentenced to a variety of correctional programs show substantial reductions in delinquent activity after leaving the programs compared to before sentencing. This paper develops models of delinquent activity and subsequent sentencing to a correctional program. We show how a population of youths, whose delinquent activity is represented by a stationary stochastic process, can be selected (using reasonable selection rules) to form a cohort which has an inflated rate of delinquent activity prior to selection. When the activity rate returns to its uninflated rate after the youths are released from the program, an apparent reduction results. Based on this analysis we conclude that the reductions noted in delinquent activity may be largely due to the way delinquents are selected for correction rather than to the effect of the programs.
An Approximation Method for Open Restricted Queueing Networks
Authors: Takahashi Yutaka , Miyahara Hideo , Hasegawa Toshiharu
Published: November 2008

This paper presents an approximation method for analyzing open restricted queueing networks with exponential service time and Poisson arrivals. Analysis is made by node-by-node decomposition through the introduction of a pseudo-arrival rate and an effective service rate. The method is applied to example networks and evaluated by comparing the results obtained thereby with those by simulations or exact calculations. We find that this method provides a fairly good approximation procedure for obtaining system performance measures such as blocking probabilities, output rates, etc., in open restricted queueing networks.
Competitive Bidding with Dependent Value Estimates
Authors: Winkler Robert L. , Brooks Daniel G.
Published: November 2008

A bidding situation in which there is uncertainty about the value of the item of interest is modeled. The uncertainty is modeled in probabilistic terms, and the model allows the errors of estimation (the differences between expected values and the actual value) of the bidders to be dependent. The effect of this dependence on the “winner's curse” (the tendency for the highest bidder to be one who has overvalued the item) is studied, and optimal bidding strategies are determined.
Technical Note—A Note on the Multiple Traveling Salesmen Problem
Authors: Rao M. R.
Published: November 2008

The fixed charge symmetric multiple traveling salesmen problem with n cities and m salesmen is transformed to a standard symmetric traveling salesman problem with n + m − 1 cities. The asymmetric problem with m = 2 and a different base city for each salesman is also transformed to a standard asymmetric traveling salesman problem.
An Evaluation of Substitute Methods for Derivatives in Unconstrained Optimization
Authors: Himmelblau D. M. , Lindsay J. W.
Published: November 2008

Under what circumstances can finite difference approximations serve as substitutes for analytical derivatives in unconstrained optimization? Are such techniques as good as using derivative-free methods? We investigated these two questions via both theoretical analysis and the solution of 15 test problems on the computer. It was discovered as expected that the error in the derivative substitutes influences algorithm performance only near termination, and that simple difference formulas are more efficient than more complex ones if the step size is selected properly. Among all the algorithms tested, the Davidon algorithm was the best both for the class using analytical derivatives and for the class with finite difference substitutes. Derivative-free algorithms were not as efficient.
Approximate Traveling Salesman Algorithms
Authors: Golden B. , Bodin L. , Doyle T. , Stewart W.
Published: November 2008

There have been a multitude of heuristic algorithms proposed for the solution of large scale traveling salesman problems. Our intent in this paper is to examine some of these well known heuristics, to introduce some new heuristics, and to compare these approximate techniques on the basis of efficiency and accuracy. We emphasize the strengths and weaknesses of each algorithm tested. One of our major conclusions is that it is not difficult to get within 2–3% of optimality using a composite heuristic which requires on the order of n3 computations where n is the number of nodes in the network.
A New and Efficient Algorithm for a Class of Portfolio Selection Problems
Authors: Pang Jong-Shi
Published: November 2008

This paper proposes a new approach and develops an efficient algorithm for solving a class of (simplified) portfolio selection problems. The approach is based on the technique of parametric principal pivoting. The algorithm is particularly suited for problems with special structure and can handle potentially large problems. When specialized to the multiple index model, the algorithm achieves enormous savings in computer storage and computations.
Identifying Efficient Vectors: Some Theory and Computational Results
Authors: Zionts Stanley , Wallenius Jyrki
Published: November 2008

Five problems of finding efficient vectors as a subset of a finite set of vectors are shown to be related and a common methodology based on the simplex method of linear programming is developed for solving all of them. Randomly generated problems for one of the five types are solved using the method, and the implications regarding computational requirements are discussed.
Technical Note—Generation of Variates from Distribution Tails
Authors: Schmeiser Bruce W.
Published: November 2008

The well known acceptance/rejection algorithm for generating random values on a computer is specialized for distribution tails. Using an exponential majorizing function and a linear minorizing function, the tail algorithm becomes particularly efficient. Specific algorithms are given for the normal, gamma, Weibull and beta distributions. While the algorithms can be used alone, it is anticipated that their major value will be to serve as components of algorithms for complete distributions.
A Solution Method for Multistage Stochastic Programs with Recourse with Application to an Energy Investment Problem
Authors: Louveaux Francois V.
Published: November 2008

We consider a multistage stochastic program with recourse, with discrete distribution, quadratic objective function and linear inequality constraints. We show that under reasonable assumptions, solving such a program is equivalent to solving a nested sequence of piecewise quadratic programs and we extend the algorithm presented in an earlier report to the multistage situation. Finally, we consider the application of the method to an energy investment problem and report on the results of numerical experiments.
Bounds for Row-Aggregation in Linear Programming
Authors: Zipkin Paul H.
Published: November 2008

Most applied linear programs reflect a certain degree of aggregation—either explicit or implicit—of some larger, more detailed problem. This paper develops methods for assessing the loss in accuracy resulting from aggregation. We showed previously that, when columns only are aggregated, a feasible solution to the larger problem can be recovered. This may not be the case under row-aggregation. Several reasonable measures of “accuracy loss” for this case are defined, and the bounds on these quantities derived. These results enable the modeler to compare and evaluate alternative approximate models of the same problem.
Beta Variate Generation via Exponential Majorizing Functions
Authors: Schmeiser Bruce W. , Babu A. J. G.
Published: November 2008

Two acceptance/rejection algorithms for generating random variates from the beta distribution are developed. The algorithms use piece-wise linear and exponential majorizing functions coupled with a piece-wise linear minorizing function. The algorithms are exact to within the accuracy of the computer and are valid for all parameter values greater than one Marginal execution times are relatively insensitive to parameter values and are faster than any previously published algorithms.
Solving the Assignment Problem by Relaxation
Authors: Hung Ming S. , Rom Walter O.
Published: November 2008

This paper presents a new algorithm for solving the assignment problem. The algorithm is based on a scheme of relaxing the given problem into a series of simple network flow (transportation) problems for each of which an optimal solution can be easily obtained. The algorithm is thus seen to be able to take advantage of the nice properties in both the primal and the dual approaches for the assignment problem. The computational bound for the algorithm is shown to be 0(n3) and the average computation time is better than most of the specialized assignment algorithms.
The Relation between Customer and Time Averages in Queues
Authors: Heyman Daniel P. , Stidham Shaler
Published: November 2008

Brumelle has generalized the queueing formula L = λW to H = λG, where λ is the arrival rate and H and G are respectively time and customer averages of some queue statistics which have a certain relationship to each other but are otherwise arbitrary. Stidham has developed a simple proof of L = λW for each sample path, in which the only requirement is that λ and W be finite. In this note it is shown that Stidham's proof applies directly to the more general case of H = λG, provided λ and G are finite and a simple technical assumption is satisfied. The result is used to obtain time average probabilities in the queue GI/M/c/K. Finally, a counterexample is given to demonstrate that the technical assumption is not superfluous, even in the special case where H and G can be interpreted, respectively, as the time average number of units in the system and the average time spent by a unit in the system, as is the case with both L = λW and the application to the queue GI/M/c/K.
Local Search for the Asymmetric Traveling Salesman Problem
Authors: Kanellakis Paris-C. , Papadimitriou Christos H.
Published: November 2008

We present an extension of the Lin-Kernighan local search algorithm for the solution of the asymmetric traveling salesman problem. Computational results suggest that our heuristic is feasible for fairly large instances. We also present some theoretical results which guided our design of the heuristic.
Multiple Objective Mathematical Programming with Respect to Multiple Decision-Makers
Authors: Wendell Richard E.
Published: November 2008

We consider the important problem of obtaining a “majority consensus” among a number of individuals on the solution to a multiple objective optimization problem. When the number of objectives is greater than two, we observe that such a consensus exists-only under strong symmetry conditions. However, in the bi-objective situation, a “consensus” exists in the convex case and we show how to find it via direct and interactive approaches. In the nonconvex bi-objective situation, a “local consensus” always exists under rather weak regularity conditions.
A Dual-Bounded Algorithm for the p-Median Problem
Authors: Galvão Roberto D.
Published: November 2008

The p-median problem consists of locating p facilities on a network, so that the sum of shortest distances from each of the nodes of the network to its nearest facility is minimized. A dual bound, based on the dual of the LP relaxation of the integer programming formulation of the problem, is developed and tested in a branch-and-bound algorithm. Computational results show that the resulting solution procedure has some advantages over existing exact methods for this problem.
The Stochastic Shortest Route Problem
Authors: Sigal C. Elliott , Pritsker A. Alan B. , Solberg James J.
Published: November 2008

The problem addressed in this paper is the selection of the shortest path through a directed, acyclic network where the arc lengths are independent random variables. This problem has received little attention although the deterministic version of the problem has been studied extensively. The concept of a path optimality index is introduced as a performance measure for selecting a path of a stochastic network. A path optimality index is defined as the probability a given path is shorter than all other network paths. This paper presents an analytic derivation of path optimality indices for directed, acyclic networks. A new network concept, Uniformly Directed Cutsets (UDCs), is introduced. UDCs are shown to be important to the efficient implementation of the prescribed analytic procedure. There are strong indications that stochastic shortest route analysis has numerous applications in operations research and management science. Potential application areas include, equipment replacement analysis, reliability modeling, maximal flow problems, stochastic dynamic programming problems, and PERT-type network analysis.
Waiting Time In a Multi-Server Cutoff-Priority Queue, and Its Application to an Urban Ambulance Service
Authors: Taylor I. D. S. , Templeton J. G. C.
Published: November 2008

We consider a priority queue in steady state with N servers, two classes of customers, and a cutoff service discipline. Low priority arrivals are “cut off” (refused immediate service) and placed in a queue whenever N1 or more servers are busy, in order to keep N − N1 servers free for high priority arrivals. A Poisson arrival process for each class, and a common exponential service rate, are assumed. Two models are considered: one where high priority customers queue for service and one where they are lost if all servers are busy at an arrival epoch. Results are obtained for the probability of n servers busy, the expected low priority waiting time, and (in the case where high priority customers do not queue) the complete low priority waiting time distribution. The results are applied to determine the number of ambulances required in an urban fleet which serves both emergency calls and low priority patient transfers.
Optimal Operation of an M/M/2 Queue with Removable Servers
Authors: Bell Colin E.
Published: November 2008

The form of the optimal policy is investigated in an average cost, infinite horizon M/M/2 problem where the number of servers working can be adjusted at arrival or service completion epochs. The costs considered are linear holding costs, linear servers' wages and set-up (shut-down) charges per server turned on (off). It is shown that an optimal policy has a hysteresis form characterized by four parameters, R1, R2, S0, and S1, denoting numbers of customers in the system when the number of working servers should be adjusted upward to 1, 2, and downward to 0, 1, respectively. Allowing for the possibilities that S0 = −1 (or S1 = −1) denoting the fact that the number of working servers are never adjusted downward to 0 (or 1), the following relationships between R1, R2, S0, and S1 are shown: (i) Ri ≥ i, i = 1, 2, (ii) R2 ≥ R1, (iii) −1 ≤ S0 ≤ S1, (iv) R2 > S1, and (v) S0 ≤ 0. Such a policy has the property that it never reacts to the arrival of a customer by immediately reducing the number of working servers and never reacts to a service completion by immediately increasing the number of working servers.
Technical Note—Data-Dependent Bounds for Heuristics to Find a Minimum Weight Hamiltonian Circuit
Authors: Jonker Roy , Kaas Rob , Volgenant Ton
Published: November 2008

We consider the problem of finding a minimum weight Hamiltonian circuit in a weighted undirected graph. If the edge weights are non-negative and satisfy the triangle inequality, there are heuristics for this problem known to have data-independent bounds on their performance. We derive data-dependent bounds for these heuristics for arbitrary edge weight problems. Our approach leads to sharper bounds than the data-independent ones when the data is non-negative and satisfies the triangle inequality.
Technical Note—Further Results on the Minimization of a Nonseparable Objective Function Subject to Disjoint Constraints
Authors: Wendell Richard E. , Rosenblum Daniel M.
Published: November 2008

We consider the class of nonseparable mathematical programs in which the vector variable can be partitioned into a number of subvectors corresponding to independent constraint sets, as opposed to two such subvectors considered in an earlier paper by Wendell and Hurter (W-H). Several optimality conditions previously given by W-H are extended to this more general case.
Technical Note—Location Theory, Dominance, and Convexity: Some Further Results
Authors: Hansen P. , Perreur J. , Thisse J.-F.
Published: November 2008

This note presents some generalizations of results on the single norm-one facility location problem due to Wendell and Hurter. It is first shown that a solution to the multifacility location problem with a single norm can be found in the convex hull of sources and destinations. In the particular case of the rectilinear norm, only intersection points belonging to this convex hull need be considered. When different 1p-norms are envisaged, the octagonal hull contains one solution to the single facility location problem. This result is also extended to the multifacility case.
Technical Note—Searchability of the Composite and Multiple Surrogate Dual Functions
Authors: Karwan Mark H. , Rardin Ronald L.
Published: November 2008

The values of optimal solutions to the various dual relaxations of integer programs can be viewed as functions of their multipliers. Successful search procedures have been developed for optimal lagrangian (piecewise linear concave) and surrogate (quasi-concave) multipliers. This note demonstrates that the composite and multiple surrogate dual functions lack quasi-concavity and may possess “false optima.” For the composite dual, complementary and alternate optimization over lagrangian and surrogate multipliers are shown to be nonoptimal techniques. However, some promising computational results, based on closing part of the gap between the surrogate dual and the primal, are reported for the alternating approach.
Search-Evasion Game in a Fixed Region
Authors: Washburn Alan R.
Published: November 2008

A game where a Searcher attempts to trap an Evader who knows the location of all past traps is formulated and solved, using average time to capture as the payoff. The Evader can move around freely, except that he is constrained to remain within a certain region.
Expected Coverage of a Randomly Located Target by Multiple Independent Salvos
Authors: Schroeter Gerhard
Published: November 2008

In models of the engagement of targets by salvos of weapons, so far mainly two sources of the variation of the relative positions of the weapon impact points and the target have been considered: the random deviation of the mean point of impact from the target center, and the dispersion of the individual rounds about the mean point of impact. New weapon systems, such as multiple-rocket launchers, add a third source of variation which generally cannot be neglected or lumped into one of the two mentioned before: the mean impact points of the individual launcher salvos scatter randomly about a common center. For the assessment of the effectiveness of such weapon systems, a measure is required that would include all three sources of variation. We derive expressions (improper integrals) for the expected destroyed value of a randomly located target, when all underlying distributions are circularly symmetric. Similar to the well-known coverage results for two-stage models, these expressions can be evaluated easily by numerical quadrature. Our coverage result is generalized to even more aggregated systems, where each rocket contains submunitions. Numerical results show that, with regard to a battery of multiple-rocket launchers, two-stage models generally are inadequate; such a model can produce an error whose size makes the result useless.
A Dynamic Programming Approach for Sequencing Groups of Identical Jobs
Authors: Psaraftis Harilaos N.
Published: November 2008

A Dynamic Programming approach for sequencing a given set of jobs in a single machine is developed, so that the total processing cost is minimized. Assume that there are N distinct groups of jobs, where the jobs within each group are identical. A very general, yet additive cost function is assumed. This function includes the overall completion time minimization problem as well as the total weighted completion time minimization problem as special cases. Priority considerations are included; no job may be shifted by more than a prespecified number of positions from its initial, First Come-First Served position in a prescribed sequence. The running time and the storage requirement of the Dynamic Programming algorithm are both polynomial functions of the maximum number of jobs per group, and exponential functions of the number of groups N. This makes our approach practical for real-world problems in which this latter number is small. More importantly, the algorithm offers savings in computational effort as compared to the classical Dynamic Programming approach to sequencing problems, savings which are solely due to taking advantage of group classifications. Specific cost functions, as well as a real-world problem for which the algorithm is particularly well-suited, are examined. The problem application is the optimal sequencing of aircraft landings at an airport. A numerical example as well as suggestions on possible extensions to the model are also presented.
DISCON: A New Method for the Layout Problem
Authors: Drezner Zvi
Published: November 2008

Layout problems often involve a given number of facilities which must be located in the plane. Each of these facilities has a given area, and the cost of interactions between every facility pair is known. Problem optimality is achieved when facilities do not overlap and the total cost, which is the sum of weighted distances between all pairs of facilities, is minimized. The problem is formulated and solved as a nonconvex mathematical programming problem using a procedure termed DISpersion-CONcentration.
The Linear Multiple Choice Knapsack Problem
Authors: Zemel Eitan
Published: November 2008

A fast algorithm is presented for the linear programming relaxation of the Multiple Choice Knapsack Problem. If N is the total number of variables and J and Jmax denote the total number of multiple choice variables and the cardinality of the largest multiple choice set, respectively, the running time of the algorithm is then bounded by 0(J log Jmax) + 0(N). Under certain conditions it is possible to reduce this bound to 0(N) steps on the average. Possible further improvements are also discussed.
A Tradeoff Cut Approach to Multiple Objective Optimization
Authors: Musselman K. , Talavage Joseph
Published: November 2008

There is a need to develop user-oriented math programming techniques for resolution of decision problems in which several objectives must be considered. One approach, the Geoffrion-Dyer-Feinberg algorithm, allows interaction between the computer and the decision maker during the solution process. The interactive approach is adopted in this paper. However, our approach focuses on reducing the feasible region of the decision space rather than improving the stored image of the overall preference function. In so doing, the problem is reduced to a series of pairwise tradeoffs between the objectives. This obviates the need for any type of choice among vectors on the part of the decision maker and stays reasonably within his capability to supply necessary information for problem solution.
Technical Note—Improved Bounds for Aggregated Linear Programs
Authors: Mendelssohn Roy
Published: November 2008

A method of Kallio for improving bounds on the optimal value of a linear program calculated from an intermediate iteration is used to improve Zipkin's bounds for an aggregated linear program. Both theoretical and computational results are given, demonstrating the improvement due to these new bounds.
A Stochastic Service Network Model with Application to Hospital Facilities
Authors: Hershey John C. , Weiss Elliott N. , Cohen Morris A.
Published: November 2008

This paper presents a methodology for estimating expected utilization and service level for a class of capacity constrained service network facilities operating in a stochastic environment. A semi-Markov process describes the flows of customers (patients) through a network of service units. We model the case where one of the units has finite capacity and no queues are allowed to form. We show that the expected level of utilization and service can be computed from a simple linear relationship based on (a) the equilibrium arrival rates at each unit which are associated with the case of infinite capacity, (b) mean holding times for each unit, and (c) the probability that the finite capacity unit is at full capacity. We use Erlang's loss formula to calculate the probability of full capacity, show this calculation to be exact for two cases, and recommend its use as an approximation in the general case. We test the accuracy of the approximation on a set of published data. In the discussion, we present a technique for analyzing collected patient flow data using the results of this methodology.
Ambushing Random Walks II: Continuous Models
Authors: Ruckle William H.
Published: November 2008

We consider a two person competitive problem in which a traveler (BLUE) wishes to cross a rectangle in such a way to avoid being ambushed by his adversary (RED) who has placed obstacles within the rectangle. Optimal strategies for BLUE and RED are derived in several cases, and applications of these results are suggested.
Logical Reduction Methods in Zero-One Programming—Minimal Preferred Variables
Authors: Guignard Monique , Spielberg Kurt
Published: November 2008

In the first part of this paper, the concept of logical reduction is presented Minimal preferred variable inequalities are introduced, and algorithms are given for their calculation. A simple illustrative example is carried along from the start, further examples are provided later. The second part of the paper describes certain properties of the generated logical inequalities. It then explains some of the decreases of computational effort which may be achieved by the use of minimal preferred inequalities and outlines a number of concrete applications with some numerical results. Finally, a number of more recent concepts and results are discussed, among them the notion of “probing” and a related zero-one enumeration code for large scale problems under the extended control language of MPSX/370.
The Multiperiod Multilocation Inventory Problem
Authors: Karmarkar Uday S.
Published: November 2008

This paper studies the structure of optimal policies in general multiperiod, multilocation inventory problems with proportional costs. It is shown that the multiperiod problem has the same generic form in each period as a one-period problem Hence, properties of the one-period problem are inherited by the multiperiod formulation; in particular the form of the optimal policy can be characterized. In the special case of a Leontief system structure (and for a somewhat more general class) it is shown that base-stock policies are optimal for certain initial states. For the stationary problem some results are derived about the monotonicity of the sequence of base stock vectors.
Equivalences and Continuity in Multivalent Preference Structures
Authors: Farquhar Peter H. , Fishburn Peter C.
Published: November 2008

In assessing multiattribute utility functions, the valence approach partitions the elements of each attribute into equivalence classes. Since attribute interactions are reflected by these equivalence classes, the functional forms of the utility representations are kept simple. This paper establishes equivalence relations for multivalent forms of additive independence, utility independence, and fractional independence, which lead to several new representation theorems. We show also that some simple partitions are not possible multivalent structures when the utility function is continuous. These results should simplify the assessment of utility functions when the attributes are interdependent.
Optimal Survivor Search with Multiple States
Authors: Discenza Joseph H. , Stone Lawrence D.
Published: November 2008

The optimal survivor search problem is to maximize the probability of finding a moving target alive. The target may be a person missing at sea or lost in a wilderness area. In a multistate target problem, the target is moving and changing states stochastically. Each state may imply different motion and detectability assumptions. We find necessary and sufficient conditions for optimal detection plans for multistate targets. Using these conditions, we extend the algoritnms of Brown and Stone for finding optimal detection search plans for moving targets to multistate target problems, and show that the optimal survivor search problem may be solved as a special case of the multistate target problem.
The Median Residual Lifetime: A Characterization Theorem and an Application
Authors: Schmittlein David C. , Morrison Donald G.
Published: November 2008

The concept of the median residual lifetime for a probability distribution is outlined and shown to have several advantages over its more common counterpart, the mean residual lifetime. A characterization theorem shows that a Pareto distribution of the second kind (or equivalently, a gamma mixture of exponentials) is the unique distribution with a linearly increasing median residual lifetime. An empirical example from the literature on strike durations is presented.
A New Optimization Method for Large Scale Fixed Charge Transportation Problems
Authors: Barr Richard S. , Glover Fred , Klingman Darwin
Published: November 2008

This paper presents a branch-and-bound algorithm for solving fixed charge transportation problems where not all cells exist. The algorithm exploits the absence of full problem density in several ways, thus yielding a procedure which is especially applicable to solving real world problems which are normally quite sparse. Additionally, streamlined new procedures for pruning the decision tree and calculating penalties are presented. We present computational experience with both a set of large test problems and a set of dense test problems from the literature. Comparisons with other codes are uniformly favorable to the new method, which runs more than twice as fast as the best alternative.
Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria
Authors: Magnanti T. L. , Wong R. T.
Published: November 2008

This paper proposes methodology for improving the performance of Benders decomposition when applied to mixed integer programs. It introduces a new technique for accelerating the convergence of the algorithm and theory for distinguishing “good” model formulations of a problem that has distinct but equivalent mixed integer programming representations. The acceleration technique is based upon selecting judiciously from the alternate optima of the Benders subproblem to generate strong or pareto-optimal cuts. This methodology also applies to a much broader class of optimization algorithms that includes Dantzig-Wolfe decomposition for linear and nonlinear programs and related “cutting plane” type algorithms that arise in resource directive and price decomposition. When specialized to network location problems, this cut generation technique leads to very efficient algorithms that exploit the underlying structure of these models. In discussing the “proper” formulation of mixed integer programs, we suggest criteria for comparing various mixed integer formulations of a problem and for choosing formulations that can provide stronger cuts for Benders decomposition. From this discussion intimate connections between the previously disparate viewpoints of strong Benders cuts and tight linear programming relaxations of integer programs emerge.
Heavy-Traffic Limits for Queues with Many Exponential Servers
Authors: Halfin Shlomo , Whitt Ward
Published: November 2008

Two different kinds of heavy-traffic limit theorems have been proved for s-server queues. The first kind involves a sequence of queueing systems having a fixed number of servers with an associated sequence of traffic intensities that converges to the critical value of one from below. The second kind, which is often not thought of as heavy traffic, involves a sequence of queueing systems in which the associated sequences of arrival rates and numbers of servers go to infinity while the service time distributions and the traffic intensities remain fixed, with the traffic intensities being less than the critical value of one. In each case the sequence of random variables depicting the steady-state number of customers waiting or being served diverges to infinity but converges to a nondegenerate limit after appropriate normalization. However, in an important respect neither procedure adequately represents a typical queueing system in practice because in the (heavy-traffic) limit an arriving customer is either almost certain to be delayed (first procedure) or almost certain not to be delayed (second procedure). Hence, we consider a sequence of (GI/M/S) systems in which the traffic intensities converge to one from below, the arrival rates and the numbers of servers go to infinity, but the steady-state probabilities that all servers are busy are held fixed. The limits in this case are hybrids of the limits in the other two cases. Numerical comparisons indicate that the resulting approximation is better than the earlier ones for many-server systems operating at typically encountered loads.
On Stochastic Bounds for the Delay Distribution in the GI/G/s Queue
Authors: Whitt Ward
Published: November 2008

A counterexample is constructed to show that the steady-state delay distribution in the GI/G/s queue with the FIFO discipline need not be stochastically less (in the sense of first-order stochastic dominance) than the steady-state delay distribution in the same system with the cyclic queue discipline. Such an ordering was conjectured by R. W. Wolff. However, it is shown that the stochastic dominance does hold for many GI/M/s queues. When it does, this bound on the delay distribution is often better than the bound for GI/M/s systems obtained by S. L. Brumelle, but neither bound appears to be very good, as is illustrated here for the M/M/s case.
Operations Research in Inventory Management: A Review and Critique
Authors: Silver Edward A.
Published: November 2008

The objectives of inventory management, including the relevant related costs, are examined in this paper. A brief review of standard problems, that have been effectively solved, is presented. However, we point out that a serious gap exists between theory and practice in many organizations. Suggestions are made for bridging this gap. Finally, a list is provided of a number of research problems whose implementable solution would have a major beneficial impact on the practice of inventory management.
Aggregation of Product Data for Hierarchical Production Planning
Authors: Axsäter Sven
Published: November 2008

When applying an aggregate view to production planning, the production system is given a hierarchical structure. The problem description at the upper level (which is less detailed) concerns product groups and machine groups rather than individual products and machines. This means that product structures and capacity requirements also must be expressed in terms of product groups and machine groups. In this paper it is shown under what conditions a perfect aggregation of product data can be obtained. If a perfect aggregation is not possible, our problem is to find a good approximate solution. A mathematical formulation of this approximation problem and its general solution is also given.
International Intra-Company Transfer Pricing
Authors: Kassicieh Suleiman K.
Published: November 2008

This paper presents the important issues of the multinational corporation's transfer pricing determination problem. It discusses the behavioral consequences of the setting of transfer prices by top management. It presents a model of transfer pricing that is developed further to include all of the issues that affect the total profits of the multinational corporation through transfer prices. The model is then expanded to include economic externalities and interdependencies such as nonlinear cost functions and functional relationships among demand, supply and transfer prices. An example is given and solved via geometric programming.
Computation of Steady-State Probabilities for M/M/1 Priority Queues
Authors: Miller Douglas R.
Published: November 2008

Recursive computational formulas for the steady-state distributions of exponential single-server (preemptive and nonpreemptive) priority queues with two classes of customers are derived using Neuts’ theory of matrix-geometric invariant probability vectors.
Optimal Control of a Birth and Death Epidemic Process
Authors: Lefévre Claude
Published: November 2008

We employ a birth and death process to describe the spread of an infectious disease through a closed population. Control of the epidemic can be effected at any instant by varying the birth and death rates to represent quarantine and medical care programs. An optimal strategy is one which minimizes the expected discounted losses and costs resulting from the epidemic process and the control programs over an infinite horizon. We formulate the problem as a continuous-time Markov decision model. Then we present conditions ensuring that optimal quarantine and medical care program levels are nonincreasing functions of the number of infectives in the population. We also analyze the dependence of the optimal strategy on the model parameters. Finally, we present an application of the model to the control of a rumor.
Feature Article—The Ellipsoid Method: A Survey
Authors: Bland Robert G. , Goldfarb Donald , Todd Michael J.
Published: November 2008

In February 1979 a note by L. G. Khachiyan indicated how an ellipsoid method for linear programming can be implemented in polynomial time. This result has caused great excitement and stimulated a flood of technical papers. Ordinarily there would be no need for a survey of work so recent, but the current circumstances are obviously exceptional. Word of Khachiyan's result has spread extraordinarily fast, much faster than comprehension of its significance. A variety of issues have, in general, not been well understood, including the exact character of the ellipsoid method and of Khachiyans result on polynomiality, its practical significance in linear programming, its implementation, its potential applicability to problems outside of the domain of linear programming, and its relationship to earlier work. Our aim is to help clarify these important issues in the context of a survey of the ellipsoid method, its historical antecedents, recent developments, and current research.
A New Linear Programming Approach to the Cutting Stock Problem
Authors: Dyckhoff Harald
Published: November 2008

A new approach to the one-dimensional cutting stock problem is described and compared to the classical model for which Gilmore and Gomory have developed a special column-generation technique. The new model is characterized by a dynamic use of simply structured cutting patterns. Nevertheless, it enables the representation of complex combinations of cuts. It can be advantageous in practical applications where many different stock lengths or a relatively large number of order lengths have to be dealt with. The new approach is applied to a real problem where the “trim loss” is not valueless, since it can be used for further demands arising in later planning periods.
Analysis of Preference Dependencies among Objectives
Authors: Keeney Ralph L.
Published: November 2008

In decision problems there are often preference dependencies for the achievement of various objectives. This paper suggests a problem-oriented approach to address such preference dependencies. First, a diagnostic analysis is conducted to identify the basis for the dependencies. Based on this, the attributes are divided into components or transformed into an alternate set of attributes with a lesser degree of preference dependence. Quantification of the value structure by developing a utility function is easier in such cases, making use of existing independence concepts.
The Use of Storage Water in a Hydroelectric System
Authors: Little John D. C.
Published: November 2008

The big water reservoirs of a hydroelectric system collect water during high river flows for use during low flows. The problem considered is how to use such stored water in the face of uncertain future flow. A method for handling the problem has been formulated and used to obtain numerical results for a simple case on a high-speed digital computer.

Operations Research, ISSN 0030-364X, was published as Journal of the Operations Research Society of America from 1952 to 1955 under ISSN 0096-3984.