Search

We review the past year and this Editor-in-Chief's editorship for the last six annual volumes in this issue's "From the Editors" column, which is coauthored with Managing Editor Kelly M. Kophazi, and then we preview this issue's research articles. Our first article, by Dorota Kurowicka is on "Conditionalization of Copula-Based Models." The next three papers address groups or teams. First is "A Note on a Group Preference Axiomatization with Cardinal Utility," by Luis C. Dias and Paula Sarabando. Next, Andrew Samuel and Seth D. Guikema address "Resource Allocation for Homeland Defense: Dealing with the Team Effect." Then, Arthur Carvalho and Kate Larson present a way for "Sharing Rewards Among Strangers Based on Peer Evaluations." Finally, Jeffrey M. Keisler and Patrick S. Noonan provide guidance for decision analysis practice in "Communicating Analytic Results: A Tutorial for Decision Consultants." [ABSTRACT FROM AUTHOR]

We give counterexamples for some statements of Borwein and sufficient conditions for the validity of these. [ABSTRACT FROM AUTHOR]

This paper generalizes, by the use of compound distributions, a result of HAIGHT (1966) on counts that are delayed but not lost. An application of Markov chains indicates a simple method of numerical evaluation of the distributions involved. Finally a continuous time analogue is studied. [ABSTRACT FROM AUTHOR]

The article presents the author's comments on criticisms of the management science paper "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," by William L. Maxwell. Maxwell presented an integer programming formulation for a one-machine job shop problem. The author contends that Maxwell's formulation was erroneous due to the intermediate steps leading from the original problem. He explains that the steps are not adequately described and therefore problematic. The author also explains that the counterexample to Maxwell's assessment is unable to be proven.

This paper provides the solution to the problem of the distribution of busy periods of the single-channel queue characterized by a time-dependent Poisson-distributed arrival rate and a general class of holding times. The notation is chosen in such a fashion that the main body of computations and mathematical analysis is identical with what was required in the solution of the general queuing equations considered in a previous paper which should be read first [4]. The solution of the problem for winch the traffic intensity is constant and the holding time distribution is Pearson type III is derived in closed form in terms of the Ink functions introduced previously. [ABSTRACT FROM AUTHOR]

In Weighted Scoring Rules and Convex Risk Measures, Dr. Zachary J. Smith and Prof. J. Eric Bickel (both at the University of Texas at Austin) present a general connection between weighted proper scoring rules and investment decisions involving the minimization of a convex risk measure. Weighted scoring rules are quantitative tools for evaluating the accuracy of probabilistic forecasts relative to a baseline distribution. In their paper, the authors demonstrate that the relationship between convex risk measures and weighted scoring rules relates closely with previous economic characterizations of weighted scores based on expected utility maximization. As illustrative examples, the authors study two families of weighted scoring rules based on phi-divergences (generalizations of the Weighted Power and Weighted Pseudospherical Scoring rules) along with their corresponding risk measures. The paper will be of particular interest to the decision analysis and mathematical finance communities as well as those interested in the elicitation and evaluation of subjective probabilistic forecasts. This paper establishes a new relationship between proper scoring rules and convex risk measures. Specifically, we demonstrate that the entropy function associated with any weighted scoring rule is equal to the maximum value of an optimization problem where an investor maximizes a concave certainty equivalent (the negation of a convex risk measure). Using this connection, we construct two classes of proper weighted scoring rules with associated entropy functions based on ϕ-divergences. These rules are generalizations of the weighted power and weighted pseudospherical rules. [ABSTRACT FROM AUTHOR]

In this paper, we use the penalty approach in order to study constrained minimization problems in infinite dimensional spaces. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper, we establish the exact penalty property for a large class of inequality-constrained minimization problems. [ABSTRACT FROM AUTHOR]

In this paper, we provide a flexible framework allowing for a unified study of time consistency of risk measures and performance measures (also known as acceptability indices). The proposed framework not only integrates existing forms of time consistency, but also provides a comprehensive toolbox for analysis and synthesis of the concept of time consistency in decision making. In particular, it allows for in-depth comparative analysis of (most of) the existing types of time consistency--a feat that has not been possible before and, which is done in the companion paper by the authors. In our approach, the time consistency is studied for a large class of maps that are postulated to satisfy only two properties--monotonicity and locality. We call these maps LM-measures. The time consistency is defined in terms of an update rule. The form of the update rule introduced here is novel, and is perfectly suited for developing the unifying framework that is worked out in this paper. As an illustration of the applicability of our approach, we show how to recover almost all concepts of weak time consistency by means of constructing appropriate update rules. [ABSTRACT FROM AUTHOR]

The technique of perturbation analysis has recently been introduced as an efficient way to compute parameter sensitivities for discrete event systems. Thus far, the statistical properties of perturbation analysis have been validated mainly through experiments. This paper considers, for an M/G/1 queueing system, the sensitivity of mean system time of a customer to a parameter of the arrival or service distribution. It shows analytically that (i) the steady state value of the perturbation analysis estimate of this sensitivity is unbiased, and (ii) a perturbation analysis algorithm implemented on a single sample path of the system gives asymptotically unbiased and strongly consistent estimates of this sensitivity. (No previous knowledge of peturbation analysis is assumed, so the paper also serves to introduce this technique to the unfamiliar reader.) Numerical extensions to GI/G/1 queues, and applications to optimization problems, are also illustrated. [ABSTRACT FROM AUTHOR]

This paper deals with undiscounted infinite stage two-person zero-sum stochastic games with finite state and action spaces. It was recently shown that such games possess a value. But in general there are no optimal strategies. We prove that for each player there exists a nonempty set of easy initial states, i.e. starting states for which the player possesses an optimal stationary strategy. This result is proved with the aid of facts derived by Bewley and Kohlberg for the limit discount equation for stochastic games. [ABSTRACT FROM AUTHOR]

This paper provides a mathematical and economic analysis of 'Incentives and Computing Systems for Team-Based Organizations' by A. Barua, C. H. Sophie Lee, and A. B. Whinston, which was published in Organization Science in 1995. Several points were not adequately stated in the original article and one of the key definitions is not clear, nor is it in keeping with the classical theory of production. Although the Cobb-Douglas production function is often used in the article, it does not comply with the article's definitions. The two main contributions of this paper are (1) to provide a word of caution to other readers who might try to extend Barua et al. (1995) and (2) to suggest alternative formulations and directions for future research. [ABSTRACT FROM AUTHOR]

This paper proposes a computationally efficient simulation-based optimization (SO) algorithm suitable to address large-scale generally constrained urban transportation problems. The algorithm is based on a novel metamodel formulation. We embed the metamodel within a derivative-free trust region algorithm and evaluate the performance of this SO approach considering tight computational budgets. We address a network-wide traffic signal control problem using a calibrated microscopic simulation model of evening peak period traffic of the full city of Lausanne, Switzerland, which consists of more than 600 links and 200 intersections. We control 99 signal phases of 17 intersections distributed throughout the entire network. This SO problem is a high-dimensional nonlinear constrained problem. It is considered large-scale and complex in the fields of derivative-free optimization, traffic signal optimization, and simulation-based optimization. We compare the performance of the proposed metamodel method to that of a traditional metamodel method and that of a widely used commercial signal control software. The proposed method systematically and efficiently identifies signal plans with improved average city-wide travel times. [ABSTRACT FROM AUTHOR]

This paper investigates equilibrium R&D investment strategies of firms endowed with different innovation potentials. To address this issue, this paper permits two stages of innovation and develops a simple stochastic game model involving two firms. It is shown that in equilibrium, a leader in the multiple stage innovation game invests more than a follower; firms compete more vigorously in the later stages of innovation than in the earlier stages; and a follower is more likely to choose a riskier innovation path than one requiring, on average, equivalent effort. It provides an explanation of how the expected benefits, the cost of R&D, and interactions between competing firms combine to determine dynamic R&D strategies over time. [ABSTRACT FROM AUTHOR]

This paper presents a class of utility functions (class A[sub ∞]) that contains all of the utility functions commonly used for mathematical modeling: the class consisting of those utility functions whose derivatives alternate in sign. A simple representation via mixtures of exponential utilities is provided for this class which is both mathematically convenient and conducive to functional operations. A connection with Laplace transforms and the resultant implications for preference relations, aggregation and utility assessment are discussed. [ABSTRACT FROM AUTHOR]

Queueing systems with interruptions serve as models for a variety of situations occurring in every day life. Usually, for each type of interruption, a separate queueing analysis is required. In this paper we present a single queueing model which can be used to analyze many such systems. The model is in the form of an approximation that is based upon several parameters, which reflect the particular queueing system under consideration. Applications to queueing systems with priorities and breakdowns are given in the paper. [ABSTRACT FROM AUTHOR]

This paper is based on the notion of discriminatory power of a pattern classifier acting over a feature space. Discriminant functions are normally used to trace out regions of the feature space corresponding to specific pattern classes. Indeterminate cases occur whenever a pattern lies on a class boundary. The number of occurrences of such indeterminacies measures the relative discriminatory power of a family of discriminant functions. In this paper these concepts are applied to majority voting decisions. It is first shown how regular majority voting leads to discriminant functions with insufficient discriminatory power whenever intransitive social ordering occurs. An (improved) family of discriminant functions is proposed to resolve such cases. [ABSTRACT FROM AUTHOR]

In a previous paper the ground work was laid for a new theoretical model of combat called the 'stochastic duel.' The principal elements of the model were fixed kill probabilities on each round fired, a random time between rounds fired, and unlimited ammunition supply. This paper extends the solution to those more realistic cases of limited ammunition supply. The general solution (as a quadrature) is obtained and it is applied to several specific examples. The special case of finite, fixed ammunition supply is treated separately. [ABSTRACT FROM AUTHOR]

The paper presents a method for solving the linear programming problems, which is itself a step towards the generalization of the classical Simlex Method. It replaces two basic variables by two non-basic variables at each iteration. Naturally this will reduce the total number of steps to reach the final solution. The paper also includes the solution of one example to illustrate the applicability of the method. [ABSTRACT FROM AUTHOR]

This paper explores several important notions relevant to modern utility theory. Restricting the discussion to the consideration of bivariate utility functions, the paper defines and examines the interrelationships between (1) independence in the utility sense, (2) trade-off or indifference curves, and (3) transformation curves (as defined herein). Following the form in which a set of basic axioms of utility are stated, independence is defined in terms of indifference between 50-50 gambles, and it is shown that, if the condition of the definition holds, then φ (x, y), the bivariate utility function, can be written as a function of x plus a function of y. The concepts of trade-off curve (indifference curve) and transformation curve are also defined on the basis of the indifference relation but are not concerned with gambles. After exploring relationships among the three notions it is shown how the utility curves for the two variables under independence can be constructed on the basis of two trade-off curves. [ABSTRACT FROM AUTHOR]

Intensive care unit (ICU) beds are valuable resources that are typically in short supply and therefore their effective and efficient use is essential particularly during periods when patient demand is high. In "Allocation of Intensive Care Unit Beds in Periods of High Demand," H. Ouyang, N.T. Argon, and S. Ziya provide insights into what kind of patient prioritization decisions are likely to improve patient health outcomes by analyzing stylized mathematical formulations that capture the fundamental trade-off involved in ICU bed management. They also propose simple policies that are likely to perform well in practice and test them with a simulation study. Findings suggest that even simple policies are likely to bring significant benefits, although more work is needed to investigate whether there could be benefits to using methods that aim to capture patient health condition in a manner that is more precise than assumed in the paper. The objective of this paper is to use mathematical modeling and analysis to develop insights into and policies for making bed allocation decisions in an intensive care unit (ICU) of a hospital during periods when patient demand is high. We first develop a stylized mathematical model in which patients' health conditions change over time according to a Markov chain. In this model, each patient is in one of two possible health stages, one representing the critical and the other representing the highly critical health stage. The ICU has limited bed availability and therefore when a patient arrives and no beds are available, a decision needs to be made as to whether the patient should be admitted to the ICU and if so, which patient in the ICU should be transferred to the general ward. With the objective of minimizing the long-run average mortality rate, we provide analytical characterizations of the optimal policy under certain conditions. Then, based on these analytical results, we propose heuristic methods, which can be used under assumptions that are more general than what is assumed for the mathematical model. Finally, we demonstrate that the proposed heuristic methods work well by a simulation study, which relaxes some of the restrictive assumptions of the mathematical model by considering a more complex transition structure for patient health and allowing for patients to be possibly queued for admission to the ICU and readmitted from the general ward after they are discharged. [ABSTRACT FROM AUTHOR]

This paper considers the problem of optimally terminating a number of stochastic processes when the time varying random rewards have distributions belonging to an exponential family with an unknown parameter. The problem is formulated as a Bayesian adaptive control model with the objective of minimizing the difference between the expected reward and the optimal reward when the parameter is known. The paper establishes an asymptotic lower bound on this difference and constructs policies based on a Kullback-Leibler index that obtains this lower bound. The results are applied to models of tree harvesting and destructive testing. A simulation study shows that these policies are efficient when the number of processes is large. [ABSTRACT FROM AUTHOR]

Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the processing times of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. By means of a novel time-indexed linear programming relaxation, we show how to compute in polynomial time a scheduling policy with provable performance guarantee for the stochastic version of the unrelated parallel machine scheduling problem with the weighted sum of completion times objective. Our performance guarantee depends on the squared coefficient of variation of the processing times and we show that this dependence is tight. Currently best-known bounds for deterministic scheduling problems are contained as special cases. [ABSTRACT FROM AUTHOR]

Recommendation stability measures the extent to which a recommendation algorithm provides predictions that are consistent with each other. Several approaches have been proposed in prior work to defining, measuring, and improving the stability of recommendation algorithms. Previous studies have focused primarily on understanding and evaluating recommendation stability in prediction-oriented settings, i.e., recommendation settings where it is crucial to provide the precise prediction of a user's preference rating for an item. However, the research literature has been largely silent on the topic of recommendation stability in other important types of settings, such as classification-oriented (i.e., where it is important to accurately classify the item as relevant versus irrelevant, without having to quantify the user's preference precisely), ranking-oriented (i.e., where it is important to provide accurate relative ranking of items to users), or top-K oriented (i.e., where it is important to suggest K items that are most appealing to the user). Therefore, this paper builds on prior work by generalizing the notion of stability to a broader set of recommendation settings and developing corresponding stability metrics. The paper also provides a comprehensive empirical analysis of classification, ranking, and top-K stability performance of popular recommender algorithms on real-world rating data sets under a variety of settings. [ABSTRACT FROM AUTHOR]

This paper discusses the application of the likelihood ratio gradient estimator to simulations of large Markovian models of highly dependable systems. Extensive empirical work, as well as some mathematical analysis of small dependability models, suggests that (in this model setting) the gradient estimators are not significantly more noisy than the estimates of the performance measures themselves. The paper also discusses implementation issues associated with likelihood ratio gradient estimation, as well as some theoretical complements associated with application of the technique to continuous-time Markov chains. [ABSTRACT FROM AUTHOR]

This paper describes a simple set of coordination structures that model certain kinds of information processing involved in organizations and markets. Four generic coordination structures are defined: product hierarchies, functional hierarchies, centralized markets, and decentralized markets. Then tradeoffs among these structures are analyzed in terms of production costs, coordination costs, and vulnerability costs. This model is unusual in that it includes detailed definitions of the structures at a micro-level and mathematical derivations of comparisons among them at a macro-level. In the final section of the paper, several connections are made between these formal results and previous work on organizational design. [ABSTRACT FROM AUTHOR]

The paradox involved in sequences of Prisoner's Dilemma games is due to the fact that game theoretic definitions of optimality rarely coincide with any natural meaning of the word. Decision makers should incorporate their beliefs and experience into any mathematical analysis of the games. Once this has been done, via subjective probabilites, use of the cooperative move in iterated Prisoner's Dilemma games can often be justified. The paper provides a simple algorithm for determining an optimal strategy, once the decision maker's subjective probabilities have been specified. [ABSTRACT FROM AUTHOR]

This paper extends recent work on finding the stochastic queue median (SQM) on a network. The SQM is the optimal location of a single mobile server, when idle, who travels to customers in response to requests for service. Customer demands are limited to the nodes of the network and their requests for service arrive according to a time homogeneous Poisson process, independently from each node. When a service request finds the server busy with a previous customer, it is entered into an M/G/1 queue that is depleted in a first-in, first-out (FIFO) manner. The SQM is the point on the network at which the sum of mean queueing delay and mean travel time is minimized. In this paper the transportation network is restricted to be a tree. By discovering and exploiting convex properties of the objective function and related functions, an efficient finite-step algorithm is found for locating the SQM on a tree. [ABSTRACT FROM AUTHOR]

It is well known that all betting systems applied to independent, repeated, and identically distributed trials will result in the same expected gain per average unit wagered as that which applies to a single trial. This paper develops the asymptotic and paradoxical manner in which that constant win rate is maintained for optimal proportional betting according to the Kelly criterion. The appropriateness of using this traditional measure of win rate for proportional betting is contrasted with that of various alternatives. [ABSTRACT FROM AUTHOR]

In a companion paper we developed a unified scheme for using poststratified sampling and control variables to improve the efficiency of regenerative queueing simulations. We adapted these variance reduction techniques to the estimation methods of replication analysis and regenerative analysis by exploiting the asymptotic joint normality of certain standardized concomitant variables that are defined on each input process sampled during a queueing simulation. In this paper we present an experimental evaluation of the reductions in point-estimator variance and confidence-interval width that can be achieved with each procedure in several closed and mixed machine-repair systems. For the analytically tractable model, nominal and actual confidence-interval coverage probabilities are also compared. Poststratification generally produced variance reductions ranging from 10% to 40% and confidence-interval reductions between 1% and 20%. The control-variates schemes yielded variance reductions ranging from 20% to 90% and confidence-interval reductions between 10% and 70%. In some instances where small sample sizes were used, the poststratification schemes produced confidence-interval width increases between 1% and 10%. With a small number of regenerative cycles, some loss of confidence-interval coverage was observed with both poststratified and controlled regenerative analysis. When larger sample sizes were used, all of the estimation schemes yielded fairly consistent efficiency gains. [ABSTRACT FROM AUTHOR]

This paper is a comprehensive study of methods for assessing unidimensional expected utility functions. The paper describes the utility assessment process in decision analysis and then reviews problem formulation, sources of bias in preference judgments, and the analysis of risk attitudes. Two dozen utility assessment methods of which half appear for the first time are critically examined. These methods are grouped into preference comparison methods, probability equivalence methods, value equivalence methods, certainty equivalence methods, hybrid methods, paired-gamble methods, and other approaches. The paper emphasizes the nature of judgmental biases in comparing different assessment procedures. Since most multiattribute utility functions are decomposed into single-attribute functions, this study should facilitate such applications. The paper concludes with several directions for further developmental, empirical, and applied research. [ABSTRACT FROM AUTHOR]

Because public systems problems are frequently ill-defined and have fuzzy constraints and vague multiple objectives, their solution by means of formal optimization models is not widely accepted. This paper will explore the modes (both useful and otherwise) in which optimization has been applied to such problems. The need for optimization models which somehow "fit" the decision-makers' methods and backgrounds will be discussed. Several other aspects of public systems optimization will be considered, in a somewhat random fashion. This paper will raise more questions than answers. [ABSTRACT FROM AUTHOR]

Due to the complexity of optimum replacement problems over finite time horizons various asymptotic criteria based upon fixed age replacement policies have been employed in the literature and in practice. In this paper the relationships between the optimum policies under three alternative cost criteria are considered. An ordering of the accounting costs under two of these is obtained, and for distributions with Increasing Hazard Rate an ordering of the optimum replacement time is derived. For a finite time horizon the policies are compared to the optimal sequential and fixed-age replacement polices through the example of a gamma distribution previously investigated by Barlow and Proschan (1962, 1965). [ABSTRACT FROM AUTHOR]

The subject of this paper is a classification and discussion of algorithms for solution of nonlinear pure integer programming problems. The survey is organized by characterizing the mathematical form of the nonlinear optimization problems addressed by the various algorithms. If any method can be used without changes to solve mixed integer nonlinear programming problems that fact is mentioned in the description of the algorithm. However algorithms which must be applied only to mixed integer problems are not surveyed. [ABSTRACT FROM AUTHOR]

A question that recurs in the decision analysis literature is: What is the value of additional data gathering? We use a very general definition of data that includes subjective probability distributions provided by experts, calculations from models, and traditional experimental data. General expressions for the expected value of data have little practical use because they involve probability distributions whose arguments are themselves probability distributions. The traditional approach to alleviate the problem of dimensionality is to introduce arbitrary parameterization of the data. This paper shows that for an interesting class of decision problems, arbitrary parameterization is not necessary. For the class of decision problems in which the value function over outcomes is a quadratic function of the state and decision variables, the value of data depends on the state variables only through the prior covariances of the posterior means. To use this result in the calculation of the approximate value of data for practical problems, it is necessary to simplify the value function. The paper suggests simplifying the value function by expanding it in a Taylor series with respect to the state and decision variables. The resulting expressions for the approximate value of information should be useful and inexpensive to evaluate for practical decision problems. [ABSTRACT FROM AUTHOR]

This paper, which is presented in two parts, is a contribution to the theory of fractional programming, i.e. maximization of quotients subject to constraints. In Part 1, duality theory for linear and concave-convex fractional programs is developed and related to recent results by Bector, Craven-Mond, Jagannathan, Sharma-Swarup, et al. Basic duality theorems of linear, quadratic and convex programming are extended. In Part II Dinkelbach's algorithm solving fractional programs is considered. The rate of convergence as well as a priori and a posteriori error estimates are determined. In view of these results the stopping rule of the algorithm is changed. Also the starting rule is modified using duality as introduced in Part I. Furthermore a second algorithm is proposed. In contrast to Dinkelbach's procedure the rate of convergence is still controllable. Error estimates are obtained too. [ABSTRACT FROM AUTHOR]

In this paper a proof of Herbert Scarf's on the optimality of (S,s) policies in inventory theory is extended to cases where differentiability of cost functions may not be available. In addition to an ordering cost composed of a unit cost plus a reorder cost all that is needed in the proof is that the expected holding and shortage cost function be convex. [ABSTRACT FROM AUTHOR]

A newsvendor game allows the players to collaborate on inventory pooling and share the resulting total cost. There are several possible ways to allocate the cost. Previous studies have focused on the core of the game. It is known that the core of the newsvendor game is nonempty, and one can use duality theory in stochastic programming to construct an allocation—referred to as the dual-based allocation—belonging to the core. Yet, an allocation that lies in the core does not necessarily guarantee the unhindered formation of a coalition, as some existing members' allocated costs may increase when new members are added in the process. In this work, we use the concept of population monotonic allocation scheme (PMAS), which requires the cost allocated to every member of a coalition to decrease as the coalition grows, to study allocation schemes in a growing population. We show that when the demands faced by the newsvendors are independent, log-concavity of their distributions is sufficient to guarantee the existence of a PMAS. Specifically, for continuous demands, log-concavity ensures that the game is convex, which in turn implies a PMAS exists. We also show that under the same condition the dual-based allocation scheme is a PMAS. For discrete and log-concave demands, however, the game may no longer be convex, but we manage to show that, even so, the dual-based allocation scheme is a PMAS. When the demands are dependent, the game is in general not convex. We derive a sufficient condition based on the dependence structure, measured by the copula, to ensure that the dual-based allocation scheme is still a PMAS. We also include an example of a game with no PMAS. This paper was accepted by Yinyu Ye, optimization. The online appendix is available at https://doi.org/10.1287/mnsc.2018.3053. [ABSTRACT FROM AUTHOR]

This paper presents an approach, similar to penalty functions, for solving arbitrary mathematical programs. The surrogate mathematical program is a lesser constrained problem that, in some cases, may be solved with dynamic programming. The paper deals with the theoretical development of this surrogate approach. [ABSTRACT FROM AUTHOR]

This paper introduces a generalization of the frequently discussed problem of finding the optimum redundancy that maximizes the reliability of a network of components. Past work has restricted consideration to arrangements of redundant components called series-parallel networks. This paper allows a much broader class of arrangements called series-parallelseries networks. It is important to consider such arrangements for realistic situations in which components have more than one failure mode, or the combination of parallel paths introduces a failure probability. A dynamic programming algorithm is used to solve the more general problem for the case in which there are no constraints on the optimum solution. The algorithm is extended to handle multiple constraints using dominance and a variety of elimination methods to reduce the storage required in a compurer implementation of the algorithm. Problems with as many as 15 serial components and three constraints have been solved with reasonable digital computer computation times. [ABSTRACT FROM AUTHOR]

This paper gives general conditions for the convergence of a class of cutting-plane algorithms without requiring that the constraint sets for the subproblems be sequentially nested. Conditions are given under which inactive constraints may be dropped after each subproblem. Procedures for generating cutting-planes include those of KELLEY, CHENEY AND GOLDSTEIN, and a generalization of the one used by both ZOUTENDIJK and VEXNoTT. For algorithms with nested constraint sets, these conditions reduce to a special case of those of ZANGWILL for such problems and include as special cases the algorithms of Kelley, Cheney and Goldstein, and Veinott. Finally, the paper gives an arithmetic convergence rate. [ABSTRACT FROM AUTHOR]

A cursory survey of the theory of games is presented. The basic models for games in extensive form, normal form, and characteristic function form are discussed, and some generalizations and extensions of these models are mentioned briefly. Some general remarks about the applicability of the theory are made in §2, and a few specific applications are referred to in sections subsequent to the description of the particular models. Mention is made throughout this paper to the other game theoretic articles in this issue in an attempt to place them somewhat within this outline of the subject. [ABSTRACT FROM AUTHOR]

This paper describes a stochastic game in which the play terminates in a finite number of steps with probability 1. The game is called a terminating stochastic game. When the play terminates at any step, the play is regarded to reach to an absorbing state in the Markov chain under consideration. Hence, the terminating stochastic game is a nonstationary Markov chain with rewards in which our concern is the transient behavior before absorption. In particular, when one of the players is a dummy, the stochastic game reduces to a Markovian decision process of special type. This paper discusses such games. We introduce a new concept of rewards and formulate three problems arising in the games by linear programming. Finally, numerical examples are presented. [ABSTRACT FROM AUTHOR]

The general problem of control of a set of individuals to achieve the objective of a controller is common to many areas such as business and government. This paper attempts a mathematical formulation and analysis of such problems. It is assumed that each individual is a rational being acting in his own self-interest. The interests of different individuals are, in general, conflicting, thus leading to a competitive situation which can be analyzed using Game Theory notions. An important aim of mathematical analysis of such a situation will be to study the effectiveness of various kinds of power that a controller might have over the individuals. Most of the results in this paper are concerning a class of 'coordination problems' where the controller's objective is to maximize the total utility to the whole group of individuals and where competition arises due to constraints on strategies. The analysis indicates that in such cases the simple power to accept or reject strategies which violate the constraints may be sufficient to realize the controller's goals. [ABSTRACT FROM AUTHOR]

The paper presents a new approach to solving a class of combinatorial economic allocation problems. One member of this class is known as the quadratic assignment problem. Besides presenting an algorithm to solve this problem, we will discuss in general terms the techniques for treating combinatorial problems. A novel feature of the paper is the development of the statistical properties of the criterion function. These statistical properties are used in conjunction with a general enumerative procedure to form the main parts of the algorithm. Using the idea of confidence level enumeration, an extension of the algorithm is proposed which should allow for the effective treatment of large scale combinatorial problems. Finally we present some computational results in order to illustrate the effectiveness of the general approach. [ABSTRACT FROM AUTHOR]

The first part of this paper is concerned with the semi-infinite linear programs studied by Charnes, Cooper and Kortanek. A form of the Farkas lemma stated by Haar appears to apply to such programs and leads to a duality theorem. In this paper an example of a semi-infinite program is given which is consistent and which has a finite minimum. However the dual program is found to be inconsistent. With a variation of the example a situation is exhibited in which both the program and its dual are consistent and have finite extrema. In this case, however, the minimum of the former is not equal to the maximum of the latter. The existence of such a ‘duality gap’ indicates that Haar's statement needs qualification. In the second part of the paper a correct form of Haar's theorem is stated and proved. The proof invokes the infinite programming theory of Duffin and Kretschmer. The last part of the paper develops a new duality theory for infinite programs which, as a special case, insures a weak form of duality for programs typified by the examples. This new duality theory is somewhat simpler than previous theories of infinite programming. [ABSTRACT FROM AUTHOR]

This study extends the results of a paper on inventory models by H. M. Wagner and T. M. Whitin. Particular attention is given to the usefulness of planning horizon theorems in simplifying computations. [ABSTRACT FROM AUTHOR]

The paper evaluates and compares classes of multi-item inventory problems where joint order of several items may save a part of the setup cost. A cost ratio and simple decision rule are determined for joint versus individual orders in specified cases. The comparisons call for the necessity of a new policy for reorder point-triggered random output multi-item systems. This policy, "the random joint order policy," operates through the determination of a reorder range within which several items can be ordered. The existence of an optimum reorder range is proved, and a computational technique is demonstrated with the help of a machine-interference type queueing model. Under favorable conditions the results exhibited on the diagram of optimum reorder ranges are generally applicable. The random joint order policy model is especially suitable for computer controlled inventory systems. [ABSTRACT FROM AUTHOR]

In this paper, we present an analysis of the strength of sparse cutting planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is nonnegative. Given an MILP instance of one of these three types, assume that we decide on the support of cutting planes to be used and the strongest inequalities on these supports are added to the linear programming relaxation. We present bounds on the ratio of optimal value of the LP relaxation after adding cuts and the optimal value of the MILP that depends only on the sparsity structure of the constraint matrix and the support of sparse cuts selected, that is, these bounds are completely data independent. These results also shed light on the strength of single-scenario cuts for two-stage stochastic MILPs. [ABSTRACT FROM AUTHOR]

In 1964, Kleinrock proposed a queueing discipline for a single-server queue in which customers from different classes accumulate priority as linear functions of their waiting time. At the instant that a server becomes free, it selects the waiting customer with the highest accumulated priority, provided that the queue is nonempty. He developed a recursion for calculating the expected waiting time for each class. In 2014, Stanford, Taylor, and Ziedins reconsidered this queue, which they termed the accumulating priority queue (APQ), and derived the waiting time distribution for each class. Kleinrock and Finkelstein in 1967 also studied an accumulating priority system in which customers' priorities increase as a power-law function of their waiting time. They established that it is possible to associate a particular linear APQ with such a power-law APQ, so that the expected waiting times of customers from all classes are preserved. In this paper, we extend their analysis to characterise the class of nonlinear APQs for which an equivalent linear APQ can be found, in the sense that, for identical sample paths of the arrival and service processes, the ordering of all customers is identical at all times in both the linear and nonlinear systems. [ABSTRACT FROM AUTHOR]

We discuss two possible parallel strategies for randomized restart algorithms. Given a set of available algorithms, one can either choose the best performing algorithm and run its multiple copies in parallel (single algorithm portfolio) or choose some subset of algorithms to run in parallel (mixed algorithm portfolio). It has been previously shown that the latter approach may provide better results computationally. In this paper, we provide theoretical investigation of the extent of such improvement generalizing some of the known results from the literature. In particular, we estimate the computational value of mixing randomized restart algorithms with different properties. Under some mild assumptions, we prove that in the best case the mixed algorithm portfolio may perform approximately up to 1.58 times faster than the best single algorithm portfolio. We also show that the obtained upper bound is sharp. Furthermore, the constructive proof of the main result allows us to characterize algorithms that are likely to form an effective mixed algorithm portfolio. [ABSTRACT FROM AUTHOR]