Search

This article presents comments by the author on a paper discussing heuristic and special case algorithms for dispersion problems. Problems discussed in this article are the subject of the paper in focus. The results presented in that paper include a simple heuristic for Max-Min Facility Dispersion (MMFD) which provides a performance guarantee of 1/2, and a similar heuristic for Max-Avg Facility Dispersion (MAFD) with a performance guarantee of 1/4. It is also proved there that obtaining a performance guarantee of more than 1/2 for MMFD is NP-hard. The paper also discussed the one- dimensional versions of MMFD and MAFD, where the vertex set V consists of a set of n points on the real line. Section 2 of the paper is devoted to the heuristic for MMPD. It should be noted that this heuristic was analyzed before. In fact, it is shown therein that the performance guarantee of 1/2, holds for a more general model where the selected set p is restricted to be in a compact subset of the network indiced by the edge distances.

In this paper we address the problem of finding the simulated system with the best (maximum or minimum) expected performance when the number of systems is large and initial samples from each system have already been taken. This problem may be encountered when a heuristic search procedure--perhaps one originally designed for use in a deterministic environment --has been applied in a simulation-optimization context. Because of stochastic variation, the system with the best sample mean at the end of the search procedure may not coincide with the true best system encountered during the search. This paper develops statistical procedures that return the best system encountered by the search (or one near the best) with a prespecified probability. We approach this problem using combinations of statistical subset selection and indifference-zone ranking procedures. The subset-selection procedures, which use only the data already collected, screen out the obviously inferior systems, while the indifference-zone procedures, which require additional simulation effort, distinguish the best from the less obviously inferior systems. [ABSTRACT FROM AUTHOR]

This paper describes 110 applications of decision analysis to health care. Each paper is characterized according to the particular problem it addresses and the methods employed in the application. These applications span 15 years of study and are reported in a widely dispersed literature. Nearly half of the published articles appear in journals with a medical audience and more than 25% of the studies remain unpublished. The major areas of application identified in this review have been the evaluation of alternatives in treatment and health policy planning. Studies discussing conceptual issues in the application of decision analysis represent a substantial portion of those identified. Almost equal numbers of applications involve the use of single and multiattribute utilities in scaling decision outcomes and relatively few apply to group utilities. General discussions of decision analysis methods and applications focused on probability assessments/analyses represent the other major categories of studies cited. [ABSTRACT FROM AUTHOR]

The question of aggregating pairwise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g., MSR's TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In most settings, in addition to obtaining a ranking, finding 'scores' for each object (e.g., player's rating) is of interest for understanding the intensity of the preferences. In this paper, we propose Rank Centrality, an iterative rank aggregation algorithm for discovering scores for objects (or items) from pairwise comparisons. The algorithm has a natural random walk interpretation over the graph of objects with an edge present between a pair of objects if they are compared; the score, which we call Rank Centrality, of an object turns out to be its stationary probability under this random walk. To study the efficacy of the algorithm, we consider the popular Bradley-Terry-Luce (BTL) model (equivalent to the Multinomial Logit (MNL) for pairwise comparisons) in which each object has an associated score that determines the probabilistic outcomes of pairwise comparisons between objects. In terms of the pairwise marginal probabilities, which is the main subject of this paper, the MNL model and the BTL model are identical. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. In particular, the number of samples required to learn the score well with high probability depends on the structure of the comparison graph. When the Laplacian of the comparison graph has a strictly positive spectral gap, e.g., each item is compared to a subset of randomly chosen items, this leads to dependence on the number of samples that is nearly order optimal. Experimental evaluations on synthetic data sets generated according to the BTL model show that our algorithm performs as well as the maximum likelihood estimator for that model and outperforms other popular ranking algorithms. [ABSTRACT FROM AUTHOR]

This paper considers the inverse problem of estimating time-varying attrition coefficients in Lanchester's square law with reinforcements, using observed data on some or all of the battle's strength histories and the reinforcement schedules. The method employed is a nonparametric extension of the parametric conjugate gradient method (P-CGM). We use hypothetical strength histories and reinforcement schedules that are known to be without error at several points in time to illustrate the method. However, the method has application in other circumstances. The problem of estimating the time-dependent attrition coefficients that best fit a set of given strength histories is inherently a nonparametric inverse problem. In this paper we cast it into a nonlinear optimization problem, and show how to solve it numerically by using a nonparametric conjugate gradient method (NP-CGM). Two numerical test cases are provided to illustrate the application of method. [ABSTRACT FROM AUTHOR]

This paper develops an efficient iterative algorithm to calculate the steady-state distribution of nearly all irreducible discrete-time Markov chains. Computational experiences suggest that, for large Markovian systems (more than 130 states), the proposed algorithm can be ten times faster than standard Gaussian elimination in finding solutions to an accuracy of 0.1%. The proposed algorithm is developed in three stages. First, we develop a very efficient algorithm for determining steady-state distributions of a restricted class of Markovian systems. A second result establishes a relationship between a general irreducible Markovian system and a system in the restricted class of Markovian systems. Finally, we combine the two results to produce an efficient, iterative algorithm to solve Markov systems. The paper concludes with a discussion of the observed performance of the algorithm. [ABSTRACT FROM AUTHOR]

Convex regression is concerned with computing the best fit of a convex function to a data set of n observations in which the independent variable is (possibly) multidimensional. Such regression problems arise in operations research, economics, and other disciplines in which imposing a convexity constraint on the regression function is natural. This paper studies a least- squares estimator that is computable as the solution of a quadratic program and establishes that it converges almost surely to the "true" function as n → ∞ under modest technical assumptions. In addition to this multidimensional consistency result, we identify the behavior of the estimator when the model is misspecified (so that the "true" function is nonconvex), and we extend the consistency result to settings in which the function must be both convex and nondecreasing (as is needed for consumer preference utility functions). [ABSTRACT FROM AUTHOR]

In this paper, we give a finite disjunctive programming procedure to obtain the convex hull of general mixed-integer linear programs (MILP) with bounded integer variables. We propose a finitely convergent convex hull tree algorithm that constructs a linear program that has the same optimal solution as the associated MILP. In addition, we combine the standard notion of sequential cutting planes with ideas underlying the convex hull tree algorithm to help guide the choice of disjunctions to use within a cutting plane method. This algorithm, which we refer to as the cutting plane tree algorithm, is shown to converge to an integral optimal solution in finitely many iterations. Finally, we illustrate the proposed algorithm on three well-known examples in the literature that require an infinite number of elementary or split disjunctions in a rudimentary cutting plane algorithm. [ABSTRACT FROM AUTHOR]

This paper develops a methodology using risk properties to characterize the functional form of a utility measure for decision making under uncertainty. The constant absolute risk property, for example, is known to be necessary and sufficient, with appropriate regularity conditions, for the utility function to have either a linear or an exponential form. A new generalization of this property, called the constant exchange risk property, gives a characterization of six utility functions: the linear function, the exponential function, the quadratic function, the sum of two exponential functions, the sum of a linear and an exponential function, and the product of a linear and an exponential function. Since all of these functional forms have been used previously as approximations, this methodology allows analysts to distinguish beforehand between alternative forms and thus properly specify the utility function in applications. [ABSTRACT FROM AUTHOR]

This paper extends previous results for calculating the centers and medians of a graph so that every point on every edge as well as all vertices are served. [ABSTRACT FROM AUTHOR]

This paper describes some measures commonly used to evaluate anticrime programs and proposes directions for research on improved measures. Since the police are usually seen as the main crime control agency, the paper first discusses the differences between evaluating the police and evaluating crime control programs. Five measures used to evaluate such programs are then analyzed: crime rate, clearance rate, arrest rate, police response time, and crime seriousness index. The last measure suggests the direction for the development of an improved measure of crime: the development of a more complete taxonomy of crime and the discrimination between and explication of the different types of harm caused by crime. [ABSTRACT FROM AUTHOR]

This paper describes an experimental comparison of flow-shop algorithms, motivated by the need to consolidate recent research on this topic. Using a set of test problems, it investigated various branch-and-bound and elimination strategies in a comparative study and then combined them to produce a new and efficient solution algorithm. [ABSTRACT FROM AUTHOR]

Saurabh Bansal and James S. Dyer study a common problem in the commercial agribusiness market, where farmers have a preference for a farm input such as a seed based on a fit with their geographical location but are also willing to accept a closely related substitute. Such consumer-driven choices may not be adequately represented by traditional models that maximize the profit of a firm that seeks to make substitutions while maximizing its profit. They use a set of recent results for evaluations of moments over polyhedra to determine the exact inventory levels a firm should keep of substitutable products. Using proprietary data from a large firm in this domain, they highlight the role of geographical and climate-related factors that affect product substitution in the agribusiness industry and identify specific regions in the United States where product substitution is a source of substantial revenue for firms. In this paper, we consider the problem in which a firm offers a portfolio of products (agricultural seeds) to multiple customer segments comprising farmers under aggressive fill-rate constraints, and some, but not all, customers will accept a substitute to their preferred choice. This business situation is not adequately represented by traditional inventory-management models, where a firm initiates a substitution based on its monetary considerations. By exploiting some recent results on polyhedral expectations, we develop a decomposition-based approach to determine optimal inventory levels for the firm's seed portfolio under aggressive fill-rate targets. The approach provides an exact solution that is implementable in managerial-friendly environments and permits a what-if analysis for real-time decision support. Subsequently we extend the technical development to establish: (i) a simple computable bound on the value of substitution, (ii) a procedure for determining implied penalty costs for substitutable products, and (iii) comparative static results for the product portfolio. We also discuss the implementation of the technical development at a Fortune 100 firm that has resulted in significant monetary savings. Finally, we provide geography- and climate-specific managerial insights for managing seed substitution by end-users. [ABSTRACT FROM AUTHOR]

This paper presents a novel framework for studying partially observable Markov decision processes (POMDPs) with finite state, action, observation sets, and discounted rewards. The new framework is solely based on future-reward vectors associated with future policies, which is more parsimonious than the traditional framework based on belief vectors. It reveals the connection between the POMDP problem and two computational geometry problems, i.e., finding the vertices of a convex hull and finding the Minkowski sum of convex polytopes, which can help solve the POMDP problem more efficiently. The new framework can clarify some existing algorithms over both finite and infinite horizons and shed new light on them. It also facilitates the comparison of POMDPs with respect to their degree of observability, as a useful structural result. [ABSTRACT FROM AUTHOR]

We introduce a generalization of K-concavity termed weak (K1, K2)-concavity and show how it can be used to analyze certain dynamic systems arising in capacity management. We show that weak (K1, K2)-concavity has two fundamental properties that are relevant for the analysis of such systems: First, it is preserved for linear interpolations; second, it is preserved for certain types of linear extensions. In capacity management problems where both buying and selling capacity involve a fixed cost plus a proportional cost/revenue term, interpolations and extensions are fundamental building blocks of the optimality analysis. In the context of the capacity management problem studied by Ye and Duenyas (2007), we show that weak (K1, K2)-concavity is sufficient to prove the general structure of the optimal policy established in that paper. [ABSTRACT FROM AUTHOR]

Nonsmoothness and nonconvexity in optimization problems often arise because a combinatorial structure is imposed on smooth or convex data. The combinatorial aspect can be explicit, e.g., through the use of "max," ''min," or "if" statements in a model; or implicit, as in the case of bilevel optimization, where the combinatorial structure arises from the possible choices of active constraints in the lower-level problem. In analyzing such problems, it is desirable to decouple the combinatorial aspect from the nonlinear aspect and deal with them separately. This paper suggests a problem formulation that explicitly decouples the two aspects. A suitable generalization of the traditional Lagrangian framework allows an extension of the popular sequential quadratic programming (SQP) methodology to such structurally nonconvex nonlinear programs. We show that the favorable local convergence properties of SQP are retained in this setting and illustrate the potential of the approach in the context of optimization problems with max-min constraints that arise, for example, in robust optimization. [ABSTRACT FROM AUTHOR]

There is an extensive theory regarding optimal continuous path search for a mobile or immobile 'target.' The traditional theory assumes that the target is one of three types: (i) an object with a known distribution of paths, (ii) a mobile or immobile hider who wants to avoid or delay capture, or (iii) a rendezvouser who wants to find the searcher. This paper introduces a new type of search problem by assuming that aims of the target are not known to the searcher. The target may be either a type (iii) cooperator (with a known cooperation probability c) or a type (ii) evader. This formulation model searches problems like that for a lost teenager who may be a 'runaway,' or a lost intelligence agent who may be a defector. In any given search context, it produces a continuum of search problems T (c), 0 ≤ c ≤ 1, linking a zero-sum search game (with c = 0) to a rendezvous problem (with c = 1). These models thus provide a theoretical bridge between two previously distinct parts of search theory, namely search games and rendezvous search. [ABSTRACT FROM AUTHOR]

In this article, the author recalls the circumstances leading to his co-authorship of the 1951 paper, "Optimal Inventory Policy." His involvement in inventory research could be described as a confluence of chance events. He had started my graduate study at Columbia University in 1940. His main interest was mathematical statistics. One of the few teachers was Harold Hotelling. However, there was then no Department of Statistics anywhere in the United States. His studies were interrupted by World War II. He volunteered for military service and spent a little over three years on duty as a weather officer. While in the military, he received one of the first documents outlining the idea of sequential statistical analysis, and was excited by it both for practical reasons and for the intellectual horizons it opened up. The Navy had a clear interest in minimizing inventory costs. His team had begun research through a logistics project at George Washington University. The other inventory model was stochastic but static; there was only one period involved.

In this paper we describe four axioms that uniquely characterize the class of locations in tree networks that are obtained by minimizing an additively separable, nonnegative, nondecreasing, differentiable, and strictly convex function of distances. This result is analogous to results that have been obtained in the theory of bargaining, social choice, and fair resource allocation. [ABSTRACT FROM AUTHOR]

This paper describes a randomized algorithm for solving the maximum-flow maximum-cut problem on connected random graphs. The algorithm is very fast--it does not look up most vertices in the graph. Another feature of this algorithm is that it almost surely provides, along with an optimal solution, a proof of optimality of the solution. In addition, the algorithm's solution is, by construction, a collection of vertex-disjoint paths which is maximum. Under a restriction on the graph's density, an optimal solution to the NP-hard communication problem is provided as well, that is, finding a maximum collection of vertex-disjoint paths between sender-receiver pairs of terminals. The algorithm lends itself to a sublogarithmic parallel and distributed implementation. Its effectiveness is demonstrated via extensive empirical study.. [ABSTRACT FROM AUTHOR]

Some 30 years ago, O. G. Haywood, Jr. published a pioneering paper relating game theory considerations to historical cases of World War II ("Military Decision and Game Theory"). The paper has become one of the most cited in military operations research literature. Facts revealed long after its publication have shed new light upon the historical case and bear upon the core of that paper. We present the story and consider its implications. [ABSTRACT FROM AUTHOR]

Previous authors have presented expressions for expected waiting time in linearly time-dependent queue disciplines. This paper points out two errors in a paper by Hsu on linearly decreasing priority systems. [ABSTRACT FROM AUTHOR]

This paper shows that solving the optimal whereabouts search problem for a moving target is equivalent to solving a finite number of optimal detection problems for moving targets. This generalizes the result of Kadane [1971] for stationary targets. [ABSTRACT FROM AUTHOR]

This paper considers the following model, described in terms of an investment problem. We have D units available for investment. During each of N time periods an opportunity to invest will occur with probability p. As soon as an opportunity presents itself, we must decide how much of our available resources to invest. If we invest y, then we obtain an expected profit P(y), where P is a nondecreasing continuous function. The amount y then becomes unavailable for future investment. The problem is to decide how much to invest at each opportunity so as to maximize total expected profit. When P(y) is a concave function, the structure of the optimal policy is obtained (Section 1). Bounds on the optimal value function and asymptotic results are presented in Section 2. A closed-form expression for the optimal value to invest is found in Section 3 for the special cases of P(y) = log y and P(y) = y[sup α] for 0<α<1. Section 4 presents a continuous-time version of the model, i.e., we assume that opportunities occur in accordance with a Poisson process. Other applications of the model are also considered. [ABSTRACT FROM AUTHOR]

This paper introduces the concept of generalized utility independence. Subject to various generalized utility independence assumptions, we derive three functional forms for a multiattribute von Neumann-Margenstern utility function u. These are the additive, the multiplicative, and the quasi-additive forms, each of which expresses u as a combination of utility functions defined on the separate attributes. It is demonstrated that if u is unbounded from above and below, then given the three forms, either reversal of preferences over some attributes occurs or else the additive form must hold. [ABSTRACT FROM AUTHOR]

This paper comments on the limiting distribution of the inventory position in a continuous review inventory system with arbitrary customer interarrival-time distribution. Sivazlian has considered an inventory model of a continuous-review system in which the interarrival times between successive customers are independent and identically distributed with arbitrary density function. The inventory position includes the stock on hand, less any backorders, plus the total amount on order. That the distribution of the inventory position in the unit demand ease is uniform is certainly not surprising. Thus, the embedded Markov chain that describes the process immediately after each demand has uniform distribution. By adjusting these values for the amount of time spent in each state, which has the same distribution regardless of the state, and normalizing, the mathematician obtain the desired result.

This paper shows that seemingly different 'adjustment' procedures are equivalent, if viewed in appropriate coordinate systems. It extends previous results concerning sequential adjustments that are constrained to be linear functions of observed impact points to the class of translation-invariant procedures. It also reviews properties of the optimal sequential adjustment procedure, including some related to stochastic approximation. [ABSTRACT FROM AUTHOR]