Search

The article presents abstracts of contributed papers submitted for presentation at the Chicago Meeting. The paper "Computer Simulation in a Missile Operational Cycle," by Robert T. Morrison explains a model of a hypothetical weapon system is analyzed by simulation techniques using a digital computer. All the important parameters affecting the model are identified and values selected. Random numbers selected by the computer are used to determine the occurrence of missile and GSE malfunctions according to the failure rates established and also to determine the repair times for the missiles and GSE if malfunctions occur. Another paper "A Measure of Effectiveness for Weapon-System Evaluation," by Robert T. Morrison explains a concept for a measure of effectiveness is developed for evaluating and judging weapon-system design and operation The proposed measure of effectiveness considers the most important factors in any complex system-maximum performance and reliability with minimum cost and time This paper shows how the measure of effectiveness is valuable for system analysis in judging between alternative proposed systems in preliminary design and measuring and evaluating the selected system progress from prototype design through final system operation and maintenance.

Comments on the paper 'A General Method for Nonlinear Programming,' by Anthony V. Fiacco, Nicholas M. Smith and David Blackwell. Application of the principle of entry into a constrained space to Carroll's technique; Computation of the starting point for the original problem.

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.

Presents a letter to the editor about the optimal policy in a maintenance cost problem.

There is an error in one of the results of our paper [Huettner F, Boyacı T, Akçay Y (2019) Consumer choice under limited attention when alternatives have different information costs. Oper. Res. 67(3):671–699]. In this erratum, we point out the error and provide a correction based on Walker-Jones [(2023) Rational inattention with multiple attributes. J. Econom. Theory 212:105688]. Our key characterizations, insights, and numerical examples do not depend on this error and, hence, remain valid. The main implication is on the stopping condition used in the algorithm. We propose a fix based on the new sufficient condition and, if needed, standard convex optimization techniques. [ABSTRACT FROM AUTHOR]

Assortment optimization has received significant attention in recent revenue management and combinatorial optimization literature. In "The Approximability of Assortment Optimization Under Ranking Preferences," A. Aouad, V. Farias, R. Levi, and D. Segev provide best-possible approximability bounds for this problem under an almost general model specification, where preferences are expressed as a distribution over rankings. This paper shows how this optimization problem relates to the computational task of detecting large independent sets in graphs, allowing the establishment of strong complexity lower bounds with respect to various problem parameters. These findings are complemented by a number of algorithms that attain essentially best-possible approximation factors, proving that the hardness results are tight up to lower-order terms. Surprisingly, their results imply that a simple and widely studied policy, known as revenue-ordered assortments, achieves the best possible performance guarantee with respect to prices. The main contribution of this paper is to provide best-possible approximability bounds for assortment planning under a general choice model, where customer choices are modeled through an arbitrary distribution over ranked lists of their preferred products, subsuming most random utility choice models of interest. From a technical perspective, we show how to relate this optimization problem to the computational task of detecting large independent sets in graphs, allowing us to argue that general ranking preferences are extremely hard to approximate with respect to various problem parameters. These findings are complemented by a number of approximation algorithms that attain essentially best-possible factors, proving that our hardness results are tight up to lower-order terms. Surprisingly, our results imply that a simple and widely studied policy, known as revenue-ordered assortments, achieves the best possible performance guarantee with respect to the price parameters. [ABSTRACT FROM AUTHOR]

An important problem in the theory of dynamic programming is that of characterizing sufficient conditions under which the optimal policies for Markov decision processes (MDPs) under the infinite-horizon discounted cost criterion converge to an optimal policy under the average cost criterion as the discount factor approaches 1. In this paper, we provide, for stochastic inventory models, a set of such sufficient conditions. These conditions, unlike many others in the dynamic programming literature, hold when the action space is noncompact and the underlying transition law is weakly continuous. Moreover, we verify that these conditions hold for almost all conceivable single-stage inventory models with few assumptions on cost and demand parameters. As a consequence of our analysis, we partially characterize, for the first time, optimal policies for the following inventory systems under the infinite-horizon average-cost criterion, which have thus far been a challenge: (a) capacitated systems with setup costs, (b) uncapacitated systems with convex ordering costs plus a setup cost, and (c) systems with lost sales and lead times. [ABSTRACT FROM AUTHOR]

We address the problem of wallpapering a room so as to minimize the paper wasted. We show that the problem is equivalent to finding a shortest hamiltonian chain in a highly structured graph. When the chain connects two equivalent nodes (traveling salesman problem), the "nearest-neighbor" technique yields an optimal solution. [ABSTRACT FROM AUTHOR]

This paper presents a classified bibliography organized into six sections--static design models, dynamic control models, models involving queue discipline control, miscellaneous models, tutorial and survey papers, and books that have specific portions devoted to design and control. Some of the above categories are further subdivided when appropriate, and explanations of the types of models in each category and subcategory precede the actual list of references. Papers that fall into more than one category are cross-referenced. [ABSTRACT FROM AUTHOR]

This article informs about the Operations Research Society of America's "Thirteenth National Meeting" which was held at Boston, Massachusetts from May 15-17, 1958. From a total 521 registrations, there were 301 were members, 186 were non-members, 34 were students. Seventy-one contributed and twelve invited papers were read. For the purpose twelve sessions were held, nine of which were half-day sessions. All-day sessions were held on Dynamic Programming, on Operational Gaming and Simulation and on Techniques of Simulation Using Digital Computers, the latter was the only session on May 17 and was held at the Computation Center of the Massachusetts Institute of Technology. The subjects of some of the individual sessions, and their chairmen, were: George E. Kimball for Dynamic Programming; Philip M. Morse for Forecasting; William Young for Contributed Papers; John M. Magee for Experimentation; Jay W. Forrester for Operations Research in Data Processing and Leon S. Pocinky for Techniques in Simulations Using Digital Computers.

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]

Bilevel optimization problems are very challenging optimization models arising in many important practical contexts, including pricing mechanisms in the energy sector, airline and telecommunication industry, transportation networks, critical infrastructure defense, and machine learning. In this paper, we consider bilevel programs with continuous and discrete variables at both levels, with linear objectives and constraints (continuous upper level variables, if any, must not appear in the lower level problem). We propose a general-purpose branch-and-cut exact solution method based on several new classes of valid inequalities, which also exploits a very effective bilevel-specific preprocessing procedure. An extensive computational study is presented to evaluate the performance of various solution methods on a common testbed of more than 800 instances from the literature and 60 randomly generated instances. Our new algorithm consistently outperforms (often by a large margin) alternative state-of-the-art methods from the literature, including methods exploiting problem-specific information for special instance classes. In particular, it solves to optimality more than 300 previously unsolved instances from the literature. To foster research on this challenging topic, our solver is made publicly available online. The online appendix is available at . [ABSTRACT FROM AUTHOR]

In many classical combinatorial optimization problems, including critical and shortest paths, maximum flow, and network reliability, the introduction of uncertainty considerably complicates the calculation of system performance. In fact, in these contexts, computing system performance exactly can often be an impossible task. Therefore, obtaining (stochastic) bounds on the system's performance becomes an attractive and useful alternative. This paper studies several stochastic bounds that are applicable to these contexts and to a broader set of problems that can be described by the general combinatorial concepts of clutters and blocking clutters. We begin our discussion by defining these unifying concepts and illustrating their specialization in several problem contexts. [ABSTRACT FROM AUTHOR]

This paper is concerned with a linear fractional problem of the form: max[sub x] min[sub y] F(X, Y) = (cX + dY + α)/(fX + gY + β), subject to AX + BY less than or equal to b; X, Y greater than or equal to O. This problem represents a generalization of a problem considered in the literature in which F(X, Y) is assumed to be linear. A number of results for the linear case are extended; and, in particular, it is shown that this fractional max-min problem is equivalent to a quasi-convex programming problem whose optimal solution lies at a vertex of the feasible region. Using these results, we develop an algorithm for solving this problem. The paper concludes with a numerical example. [ABSTRACT FROM AUTHOR]

This paper examines properties and interrelations of several concepts of generalized concavity. It shows that the class of functions that are both ‘generalized concave’ and ‘generalized convex’ is closely related to the class of monotone functions of a single variable. After excluding a certain small class of exceptions, the paper shows that, for arbitrary (perhaps not differentiable) functions, concave implies pseudoconcave, pseudoconcave implies strictly quasiconcave, and strictly quasiconcave implies quasiconcave. Several results characterizing the extreme values of generalized concave functions are given. [ABSTRACT FROM AUTHOR]

This paper considers the case of a product consisting of several components, each of which is batch manufactured. It assumes that the product demands occur singly, and that the components are manufactured in equal-batch quantities in a reorder level-batch quantity system. The paper is concerned with the optimal phasing of the components in order to minimize the variance of holding cost for the product. It shows that the optimal policy is independent of the order of sequencing of the components and is given when the phase lag between consecutive components in the cycle is equal to [(Ai+Aj)/∑all i Ai. (q/2), where Ai, Aj are the unit values of the components, and q is the batch quantity. A specific example is included to illustrate the three-component case and the discrete practical solution for any number of components is indicated. [ABSTRACT FROM AUTHOR]

The past decade has given rise to a considerable amount of research in the fields of inventory control and production planning. One of the most useful mathematical models originated with the paper of K. D. ARROW, T. E. HARRIS, AND J. MARSCHAK, "Optimal Inventory Policy," Econometrica 19, 250-272 (1951). This model was further improved in RICRARD BELLMAN'S book, Dynamic Programming, pp. 152-182, Princeton University Press, Princeton, New Jersey, 1957. In the present paper, another formulation of the same problem is exhibited. The attentive reader will observe many similarities to the dynamic programming formulation. [ABSTRACT FROM AUTHOR]

Although the earliest discussions of linear programming date back to the 1930's, to the work of German and Austrian mathematicians and economists, the mathematics has been extensively developed only in the past six or eight years. Because of the relative newness of the subject, the literature is widely scattered and it is rather difficult for one just starting to learn about linear programming to know where to begin. Because of human limitations, the bibliography is necessarily incomplete. All papers and books that could be acquired that seemed to deal with the subject were perused and, if applicable, included. No extensive effort was made, however, to include papers dealing more or less exclusively with closely related topics, for example, the problem of determination of value and optimal strategies in a zero-sum, two-person game, the pure inequalities problem with no optimization, the subjects of convex functions and convex polyhedra, unless they also relate these topics directly to linear programming.

Presents a letter to the editor about the optimal design of optimization experiments.

Learning Compact High-Dimensional Models in Noisy Environments Building compact, interpretable statistical models where the output depends upon a small number of input features is a well-known problem in modern analytics applications. A fundamental tool used in this context is the prominent best subset selection (BSS) procedure, which seeks to obtain the best linear fit to data subject to a constraint on the number of nonzero features. Whereas the BSS procedure works exceptionally well in some regimes, it performs pretty poorly in out-of-sample predictive performance when the underlying data are noisy, which is quite common in practice. In this paper, we explore this relatively less-understood overfitting behavior of BSS in low-signal noisy environments and propose alternatives that appear to mitigate such shortcomings. We study the theoretical statistical properties of our proposed regularized BSS procedure and show promising computational results on various data sets, using tools from integer programming and first-order methods. We study a seemingly unexpected and relatively less understood overfitting aspect of a fundamental tool in sparse linear modeling—best subset selection—which minimizes the residual sum of squares subject to a constraint on the number of nonzero coefficients. Whereas the best subset selection procedure is often perceived as the "gold standard" in sparse learning when the signal-to-noise ratio (SNR) is high, its predictive performance deteriorates when the SNR is low. In particular, it is outperformed by continuous shrinkage methods, such as ridge regression and the Lasso. We investigate the behavior of best subset selection in the high-noise regimes and propose an alternative approach based on a regularized version of the least-squares criterion. Our proposed estimators (a) mitigate, to a large extent, the poor predictive performance of best subset selection in the high-noise regimes; and (b) perform favorably, while generally delivering substantially sparser models, relative to the best predictive models available via ridge regression and the Lasso. We conduct an extensive theoretical analysis of the predictive properties of the proposed approach and provide justification for its superior predictive performance relative to best subset selection when the noise level is high. Our estimators can be expressed as solutions to mixed-integer second-order conic optimization problems and, hence, are amenable to modern computational tools from mathematical optimization. Funding: R. Mazumder acknowledges research funding from the Office of Naval Research [Grants N000141512342 and N000141812298] and the National Science Foundation [Grant NSF-IIS-1718258]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2022.2276. [ABSTRACT FROM AUTHOR]

The United States Coast Guard (USCG), a part of the U.S. Department of Homeland Security, is the nation's leading agency in maritime security, safety, and stewardship. One of the primary USCG resources is a fleet of boats (maritime vessels less than 65 feet in length) of various types that must be allocated to USCG stations nationwide. This paper describes the academic-industry collaboration between the authors and the USCG, which resulted in the development of an integer linear programming model that optimally matches supplies of various types of boats to station demands. The paper also introduces a model for the optimal sharing of scarce boat resources. In addition, we generalize our model, using value-at-risk and robust optimization ideas, to manage the risk of boat shortages. The paper reports on the USCG implementation process and discusses internal resistance issues and eventual adoption. We describe USCG modifications to the model recommendations due to practicalities not captured by our model. Finally, we present the significant improvements to USCG quantitative performance metrics that resulted from our model's recommendations. These include a considerable reduction of excess capacity and boat shortages at the stations, a decrease in the overall fleet size with a simultaneous increase in boat utilization, and overall reduction of the fleet operating cost. We also discuss in depth how our model effected these improvements. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of maximizing a separable concave function over a polymatroid. More specifically, we study the submodularity of its optimal objective value in the parameters of the objective function. This question is interesting in its own right and is encountered in many applications. But our research has been motivated mainly by a cooperative game associated with the well-known joint replenishment model. By applying our general results on polymatroid optimization, we prove that this cooperative game is submodular (i.e., its characteristic cost function is submodular) if the joint setup cost is a normalized and nondecreasing submodular function. Furthermore, the same result holds true for a more general one-warehouse multiple retailer game, which affirmatively answers an open question posed by Anily and Haviv [Anily, S., M. Haviv. 2007. The cost allocation problem for the first order interaction joint replenishment model.] [ABSTRACT FROM AUTHOR]

This paper reports on an application of network-flow integer programming to a vacation timeshare exchange problem. A typical timeshare owner has purchased yearly access to a specific week at a specific resort. The resulting lack of vacation variety is mitigated by systems that allow owners to exchange owned weeks for different weeks at different resorts according to their preferences, the assessed value of what they are exchanging, their contractual priority, and resort availability. The timeshare exchange problem is similar to other preference-based assignment problems such as labor scheduling, preferential bidding, and traditional timetabling, but different in the formulation of the objective function. This paper demonstrates how the effectiveness of timeshare exchange processes can be improved through mathematical optimization, as measured by increased satisfaction of participant preferences. Optimization also presents exchange managers with the opportunity to more precisely manage preference and priority trade-offs among various classes of participants. The trade-off decisions are aided by sensitivity analysis utilizing a minmax criterion. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the properties of the sampled version of the fictitious play algorithm, familiar from game theory, for games with identical payoffs, and propose a heuristic based on fictitious play as a solution procedure for discrete optimization problems of the form max {u(y) y = (y1,…yn ∈ y1 x … x yn} i.e., in which the feasible region is a Cartesian product of finite sets y1 i ∈ N = (1, …, n). The contributions of this paper are twofold. In the first part of the paper, we broaden the existing results on convergence properties of the fictitious play algorithm on games with identical payoffs to include an approximate fictitious play algorithm that allows for errors in players 'best replies. Moreover, we introduce sampling-based approximate fictitious play that possesses the above convergence properties, and at the same time provides a computationally efficient method for implementing fictitious play. In the second part of the paper, we motivate the use of algorithms based on sampled fictitious play to solve optimization problems in the above form with particular focus on the problems in which the objective function u(·) comes from a "black box," such as a simulation model, where significant computational effort is required for each function evaluation. [ABSTRACT FROM AUTHOR]

In this paper, we study inverse optimization problems defined as follows. Let S denote the set of feasible solutions of an optimization problem P, let c be a specified cost vector, and x[sup 0] be a given feasible solution. The solution x[sup 0] may or may not be an optimal solution of P with respect to the cost vector c. The inverse optimization problem is to perturb the cost vector c to d so that x[sup 0] is an optimal solution of P with respect to d and ||d − c||[sub p] is minimum, where ||d − c||[sub p] is some selected L[sub p] norm. In this paper, we consider the inverse linear programming problem under L[sub 1] norm (where ||d − c||[sub p] = Σ[sub i ∈J] w[sub j]|d[sub j] − c[sub j]|, with J denoting the index set of variables x[sub j] and w[sub j] denoting the weight of the variable j) and under L[sub ∞] norm (where ||d − c||[sub p] = max[sub j∈J]{w[sub j]|d[sub j] − c[sub j]|}). We prove the following results: (i) If the problem P is a linear programming problem, then its inverse problem under the L[sub 1] as well as L[sub ∈] norm is also a linear programming problem. (ii) If the problem P is a shortest path, assignment or minimum cut problem, then its inverse problem under the L[sub 1] norm and unit weights can be solved by solving a problem of the same kind. For the nonunit weight case, the inverse problem reduces to solving a minimum cost flow problem. (iii) If the problem P is a minimum cost flow problem, then its inverse problem under the L[sub 1] norm and unit weights reduces to solving a unit-capacity minimum cost flow problem. For the nonunit weight case, the inverse problem reduces to solving a minimum cost flow problem. (iv) If the problem P is a minimum cost flow problem, then its inverse problem under the L[sub ∈] norm and unit weights reduces to solving a minimum mean cycle problem. For the nonunit weight case, the inverse problem reduces to solving a minimum cost-to-time... [ABSTRACT FROM AUTHOR]

This paper describes a methodology for investigating optimal production policies for hydrocarbon reservoirs by an approach that brings together reservoir simulation models and numerical optimization techniques. It describes the results of applying this methodology to a dry gas storage reservoir using a single phase, two-dimensional reservoir simulator. The paper investigates optimal production strategies for several optimization criteria and potential constraints on reservoir operations, and discusses extensions to more complex systems. [ABSTRACT FROM AUTHOR]

This paper treats the discounted cost, optimal control problem for Markov processes with incomplete state information. The optimization approach for these partially observable Markov processes is a generalization of the well-known policy iteration technique for finding optimal stationary policies for completely observable Markov processes. The state space for the problem is the space of state occupancy probability distributions (the unit simplex). The development of the algorithm introduces several new ideas, including the class of finitely transient policies, which are shown to possess piecewise linear cost functions. The paper develops easily implemented approximations to stationary policies based on these finitely transient policies and shows that the concave hull of an approximation can be included in the well-known Howard policy improvement algorithm with subsequent convergence. The paper closes with a detailed example illustrating the application of the algorithm to the two-state partially observable Markov process. [ABSTRACT FROM AUTHOR]

A mathematical program with a maximin objective function is defined as an optimization problem of the following type: Maxz=min[sub i] c[sub i]x[sub i], subject to AX = b, X * (This character cannot be converted in ASCII text) O. Although the c[sub i] can be in the interval (-- ∞, ∞), the paper discusses the more common practical case where all c[sub t] * (This character cannot be converted in ASCII text) 0. It shows that problems of this type arise in a variety of applications where it is required to maximize a production function of the 'fixed proportion' type subject to a set of linear constraints. Although it is well known that the solution to this type of problem can be found by linear programming, this paper shows that, if the existence of a certain condition can be demonstrated, then a simplified method can be used to determine the optimum solution. Many problems of practical interest can be solved by this simplified method; an example involving the readiness of a ship is presented. [ABSTRACT FROM AUTHOR]

The model described in this paper was developed to provide guidance for price and promotion decisions in a consumer-goods division doing business in the United States marketplace. Demand is a dynamic function of price and promotion; the total market is divided into M interacting market segments that often have different needs and wants for the product and that can be sent different promotional messages; the segments usually have different price and promotion elasticities. For a given planning horizon, the model determines the optimal price to be charged in the M segments, the optimal promotional budget, and its allocation over the M segments. A convex programming formulation is utilized. The paper discusses the reality of the environment to be modeled, develops the model in relation to this reality, and then provides an empirical illustration of the model. [ABSTRACT FROM AUTHOR]

This paper examines a production system with variable repair-service rates. Considering costs dependent on the service rates and costs due to lost production, it seeks to minimize the long-run expected average cost of the system. The model is a continuous-time Markovian decision problem. The paper states sufficient conditions for eliminating from consideration certain service rates and for the existence of an optimal stationary policy from a 'simple' class. It also gives an example of a nonsimple optimal policy. [ABSTRACT FROM AUTHOR]

This paper deals with systems (such as electronic devices and corporations) that are designed to accomplish multiple goals and whose internal structures are characterized by networks of interacting component parts. Each component of such a system is typically associated with a probability of failure, while each system goal is associated with a reward value. Failure of any network component may ultimately result in the inability to achieve one or more goals and force the forfeiture of the associated rewards. A basic problem in component-system design is to determine how the expectation of total reward may be maximized through the cost-limited acquisition of redundant (backup) components. This paper provides a formal statement of this redundancy-optimization problem and argues that the problem may not be solved easily by standard linear or integer programming techniques. It introduces an algorithm to solve this problem, proves its convergence, and presents computational results taken from a battery of test problems and an algorithm-efficiency study based on these tests. [ABSTRACT FROM AUTHOR]

This paper treats the optimal location of nuclear-power plants in the Pacific Northwest with respect to capital-construction, operating, and transmission costs. It presents a mathematical formulation of this two-product (peak and energy power) plant-location problem, using the simplex method in conjunction with a branch-and-bound process, and indicates a check procedure using Vogel's approximation method in conjunction with an algorithm for solving the transportation problem and a branch-and-bound process. The paper gives results for demand-growth rates of 4, 5, 6 and 7 percent and alternative designs and their costs. It also discusses the stability of the optimal solution. [ABSTRACT FROM AUTHOR]

This paper develops a new cutting plane for primal integer programming. This cut, when it exists and is used as pivot row, has the property that the minimum of the simplex evaluators of the next tableau is strictly larger (by an integer) than the minimum for the current tableau. The paper gives a sufficient condition in the form of a linear program for the existence of such a cut, and proposes an algorithm for generating such cuts. It also presents two additional sufficient conditions. The process of cut generation is then imbedded into a convergent primal algorithm to be used in an attempt to overcome the proof-of-optimality problem experienced with the primal algorithm. [ABSTRACT FROM AUTHOR]

Natural policy gradient (NPG) methods, in conjunction with entropy regularization to encourage exploration, are among the most popular policy optimization algorithms in contemporary reinforcement learning. Despite the empirical success, the theoretical underpinnings for NPG methods remain severely limited. In "Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization", Cen, Cheng, Chen, Wei, and Chi develop nonasymptotic convergence guarantees for entropy-regularized NPG methods under softmax parameterization, focusing on tabular discounted Markov decision processes. Assuming access to exact policy evaluation, the authors demonstrate that the algorithm converges linearly at an astonishing rate that is independent of the dimension of the state-action space. Moreover, the algorithm is provably stable vis-à-vis inexactness of policy evaluation. Accommodating a wide range of learning rates, this convergence result highlights the role of preconditioning and regularization in enabling fast convergence. Natural policy gradient (NPG) methods are among the most widely used policy optimization algorithms in contemporary reinforcement learning. This class of methods is often applied in conjunction with entropy regularization—an algorithmic scheme that encourages exploration—and is closely related to soft policy iteration and trust region policy optimization. Despite the empirical success, the theoretical underpinnings for NPG methods remain limited even for the tabular setting. This paper develops nonasymptotic convergence guarantees for entropy-regularized NPG methods under softmax parameterization, focusing on discounted Markov decision processes (MDPs). Assuming access to exact policy evaluation, we demonstrate that the algorithm converges linearly—even quadratically, once it enters a local region around the optimal policy—when computing optimal value functions of the regularized MDP. Moreover, the algorithm is provably stable vis-à-vis inexactness of policy evaluation. Our convergence results accommodate a wide range of learning rates and shed light upon the role of entropy regularization in enabling fast convergence. [ABSTRACT FROM AUTHOR]

Taming high-dimensional Markov models In "Learning Markov models via low-rank optimization", Z. Zhu, X. Li, M. Wang, and A. Zhang focus on learning a high-dimensional Markov model with low-dimensional latent structure from a single trajectory of states. To overcome the curse of high dimensions, the authors propose to equip the standard MLE (maximum-likelihood estimation) with either nuclear norm regularization or rank constraint. They show that both approaches can estimate the full transition matrix accurately using a trajectory of length that is merely proportional to the number of states. To solve the rank-constrained MLE, which is a nonconvex problem, the authors develop a new DC (difference) programming algorithm. Finally, they apply the proposed methods to analyze taxi trips on the Manhattan island and partition the island based on the destination preference of customers; this partition can help balance supply and demand of taxi service and optimize the allocation of traffic resources. Modeling unknown systems from data is a precursor of system optimization and sequential decision making. In this paper, we focus on learning a Markov model from a single trajectory of states. Suppose that the transition model has a small rank despite having a large state space, meaning that the system admits a low-dimensional latent structure. We show that one can estimate the full transition model accurately using a trajectory of length that is proportional to the total number of states. We propose two maximum-likelihood estimation methods: a convex approach with nuclear norm regularization and a nonconvex approach with rank constraint. We explicitly derive the statistical rates of both estimators in terms of the Kullback-Leiber divergence and the ℓ 2 error and also establish a minimax lower bound to assess the tightness of these rates. For computing the nonconvex estimator, we develop a novel DC (difference of convex function) programming algorithm that starts with the convex M-estimator and then successively refines the solution till convergence. Empirical experiments demonstrate consistent superiority of the nonconvex estimator over the convex one. [ABSTRACT FROM AUTHOR]

Consider a central planner with a limited budget charging taxes and allocating copayment subsidies to competing producers of a commodity, with the goal of maximizing its aggregate consumption (for example, the Global Fund trying to increase the consumption of artemisinin combination therapy antimalarials in Africa). The policy most frequently implemented allocates uniform copayments (i.e., every firm gets the same copayment), even if some firms are more efficient than others. The central question in this paper is to evaluate the worst possible efficiency loss induced by uniform copayments. We show that uniform copayments are guaranteed to induce a large fraction of the market consumption induced by the optimal policy. This is important, because we also show that the optimal policy is hard to implement. In summary, our results provide theoretical support to continue the use of the simple uniform copayments policy in practice. We study a subsidies and taxes allocation problem with endogenous market response subject to a budget constraint. The central planner's objective is to maximize the consumption of a good, and she allocates per-unit copayments and taxes to its producers. We show that the optimal policy taxes the more efficient firms and allocates larger copayments to less efficient firms, making it impractical. Therefore, we consider the simple and frequently implemented policy that allocates the same copayment to each firm, known as uniform copayments, and provide the first worst-case performance guarantees for it. Namely, we show that uniform copayments are guaranteed to induce a significant fraction of the consumption induced by the optimal policy in small markets for price-taking (Cournot) producers with affine increasing marginal costs facing any nonincreasing (linear) inverse demand function, even for different firms' efficiency levels. Moreover, compared with the best policy that allocates copayments only, uniform copayments induce at least one-half of the optimal consumption. Furthermore, for Cournot competition with linear demand and constant marginal costs, the latter guarantee increases to more than 85% of the optimal consumption. Our results suggest that uniform copayments are surprisingly powerful in increasing the market consumption of a good. The e-companion is available at https://doi.org/10.1287/opre.2018.1785. [ABSTRACT FROM AUTHOR]

The need to understand complex city traffic patterns has led to an increase in the amount and the diversity of traffic data being collected. For instance, taxi companies in an increasing number of major cities have started recording metadata for every individual car ride, such as its origin, destination, and travel time. By leveraging network optimization insights, we can extract accurate travel time estimations from such origin–destination data. For example, we can reconstruct traffic patterns at the scale of Manhattan using only origin–destination information for a few hundred thousand taxi trips, without any information about vehicles' individual paths. Twenty-first century urban planners have identified the understanding of complex city traffic patterns as a major priority, leading to a sharp increase in the amount and the diversity of traffic data being collected. For instance, taxi companies in an increasing number of major cities have started recording metadata for every individual car ride, such as its origin, destination, and travel time. In this paper, we show that we can leverage network optimization insights to extract accurate travel time estimations from such origin–destination data, using information from a large number of taxi trips to reconstruct the traffic patterns in an entire city. We develop a method that tractably exploits origin–destination data, which, because of its optimization framework, could also take advantage of other sources of traffic information. Using synthetic data, we establish the robustness of our algorithm to high variance data, and the interpretability of its results. We then use hundreds of thousands of taxi travel time observations in Manhattan to show that our algorithm can provide insights about urban traffic patterns on different scales and accurate travel time estimations throughout the network. [ABSTRACT FROM AUTHOR]

With the emergence of ride-sharing companies that offer transportation on demand at a large scale and the increasing availability of corresponding demand data sets, new challenges arise to develop routing optimization algorithms that can solve massive problems in real time. In "Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications," D. Bertsimas, P. Jaillet, and S. Martin present a novel and generalizable backbone algorithm that uses integer optimization to find high-quality solutions to large routing optimization problems. The algorithm, together with the real-time routing optimization software framework developed and shared by the authors, can dispatch thousands of taxis serving more than 25,000 customers per hour. An extensive study with historical simulations of Yellow Cabs in New York City is used to both show that the algorithm improves on the performance of existing heuristics and to provide insights on the optimization opportunities of a large ride-sharing fleet. With the emergence of ride-sharing companies that offer transportation on demand at a large scale and the increasing availability of corresponding demand data sets, new challenges arise to develop routing optimization algorithms that can solve massive problems in real time. In this paper, we develop an optimization framework, coupled with a novel and generalizable backbone algorithm, that allows us to dispatch in real time thousands of taxis serving more than 25,000 customers per hour. We provide evidence from historical simulations using New York City routing network and yellow cab data to show that our algorithms improve upon the performance of existing heuristics in such real-world settings. The online supplement is available at https://doi.org/10.1287/opre.2018.1763. [ABSTRACT FROM AUTHOR]

A complementary programming problem is a linear programming problem with the additional restriction that xpxq=0 holds for each specified pair (xp, xq). This paper obtains constraints called C-cuts from the restriction xpxq=0, and uses them to facilitate the computation of the branch-and-bound procedure proposed in an earlier paper [Opns. Res. 19, 1523–1528 (1971)]. Some computational results are also reported. [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 sets forth mathematical means for optimizing the simultaneous apportionments of reliability and maintainability by means of two techniques Lagrange multipliers and dynamic programming. Since one of the constraint equations revolves allocating both variables, this simultaneous apportionment problem differs from the usual two-dimensional dynamic programming problems. Two cost problems are treated the first minimizes cost while satisfying availability requirements under the assumption that an unlimited ceiling exists for the cost, and the second maximizes reliability and maintainability given a fixed budget. Although these problems appear closely related, step functions usually preclude considering them together The paper also considers two numerical examples, an interesting cost model for maintainability, and using computers with its models. [ABSTRACT FROM AUTHOR]

This paper considers the problem of partitioning N entities into M disjoint and nonempty subsets (clusters). Except when both N and N--M are very small, a search for the optimal solution by total enumeration of all clustering alternatives is quite impractical. The paper presents a dynamic programming approach that reduces the amount of redundant transitional calculations implicit in a total enumeration approach. A comparison of the number of calculations required under each approach is presented in Appendix A. Unlike most clustering approaches used in practice, the dynamic programming algorithm will always converge on the best clustering solution. The efficiency of the dynamic programming approach depends upon the rapid-access computer memory available. A numerical example is given in Appendix B. [ABSTRACT FROM AUTHOR]

This paper finds sufficient conditions for the ergodicity and recurrence of irreducible and aperiodic Markov chains. They extend some of the ones commonly used. The paper also indicates their use in discussing a certain class of queuing problem with state dependent service times. [ABSTRACT FROM AUTHOR]

This paper develops a new algorithm for solving the general nonlinear programming problem that melds the flexible simplex search of NELDER AND MEAD with various additional rules to take care of equality and/or inequality constraints. The set of violated inequalities and equalities is lumped into one inequality constraint loosely satisfied during the early progress of the optimization and more closely satisfied during its final stages. To permit this type of search, the method sets up a special tolerance criterion, a function that does not depend on either the values of the objective function or the values of the constraints. The new algorithm has solved successfully a number of problems that have been proposed in the literature as test problems. Finally, to indicate the algorithm's capabilities, the paper describes an example composed of a linear objective function of twenty-four variables subject to fourteen nonlinear equalities and thirty inequalities. [ABSTRACT FROM AUTHOR]

This is the first of a senes of papers devoted to the computational solution of dynamic programming processes In it we use the functional-equation approach to treat a tactical air-waref are model that A Mengel previously has considered by means of classical variational techniques [ABSTRACT FROM AUTHOR]

Finding optimal policies when the objective function can only be observed with a noisy error has traditionally required repeated observations to average out the noise. In this paper, we prove for a very large class of continuous stochastic optimization problems and search algorithms that a single observation for each candidate solution suffices to completely eliminate the error. This surprising result can best be understood through the metaphor of facing a continuum of slot machines and observing the reward for a single pull of the arm for each machine as we search for a machine delivering the best return. By the impossibility of systems, the average winnings must approach the expected winnings regardless of how we select the sequence of machines to test. This same martingale property is inherited for simulation optimization so that a single observation also suffices for convergence to the global optimum. The resulting savings in simulation time can be quite significant. Optimizing the performance of complex systems modeled by stochastic computer simulations is a challenging task, partly because of the lack of structural properties (e.g., convexity). This challenge is magnified by the presence of random error whereby an adaptive algorithm searching for better designs can at times mistakenly accept an inferior design. In contrast to performing multiple simulations at a design point to estimate the performance of the design, we propose a framework for adaptive search algorithms that executes a single simulation for each design point encountered. Here the estimation errors are reduced by averaging the performances from previously evaluated designs drawn from a shrinking ball around the current design point. We show under mild regularity conditions for continuous design spaces that the accumulated errors, although dependent, form a martingale process, and hence, by the strong law of large numbers for martingales, the average errors converge to zero as the algorithm proceeds. This class of algorithms is shown to converge to a global optimum with probability one. By employing a shrinking ball approach with single observations, an adaptive search algorithm can simultaneously improve the estimates of performance while exploring new and potentially better design points. Numerical experiments offer empirical support for this paradigm of single observation simulation optimization. The e-companion is available at https://doi.org/10.1287/opre.2018.1759. [ABSTRACT FROM AUTHOR]

Bandwidth-sharing networks provide a natural modeling framework for describing the dynamic flow-level interaction among elastic data transfers in computer and communication systems, and can be used to develop traffic pricing/charging mechanisms. At the same time, such models are exciting from an operations research perspective because their analysis requires techniques from stochastic modeling and optimization. In this paper, we develop a framework to approximate bandwidth-sharing networks under the assumption that the number of users as well as the capacities of the system are large, and the assumption that the traffic that each user is allowed to submit is bounded above by some rate, which is standard in practice. We also assume that customers on each route in the network abandon according to exponential patience times. Under Markovian assumptions, we develop fluid and diffusion approximations, which are quite tractable: for most parameter combinations, the invariant distribution is multivariate normal, with mean and diffusion coefficients that can be computed in polynomial time as a function of the size of the network. [ABSTRACT FROM AUTHOR]

In this paper, we develop efficient Monte Carlo methods for estimating American option sensitivities. The problem can be reformulated as how to perform sensitivity analysis for a stochastic optimization problem with model uncertainty. We introduce a generalized infinitesimal perturbation analysis (IPA) approach to resolve the difficulty caused by discontinuity of the optimal decision with respect to the underlying parameter. The IPA estimators are unbiased if the optimal decisions are explicitly known. To quantify the estimation bias caused by intractable exercising policies in the case of pricing American options, we also provide an approximation guarantee that relates the sensitivity under the optimal exercise policy to that computed under a suboptimal policy. The price-sensitivity estimators yielded from this approach demonstrate significant advantages numerically in both high-dimensional environments and various process settings. We can easily embed them into many of the most popular pricing algorithms without extra simulation effort to obtain sensitivities as a by-product of the option price. Our generalized approach also casts new insights on how to perform sensitivity analysis using IPA: we do not need path-wise continuity to apply it. [ABSTRACT FROM AUTHOR]

We study the strip packing problem, in which a set of two-dimensional rectangular items has to be packed in a rectangular strip of fixed width and infinite height, with the aim of minimizing the height used. The problem is important because it models a large number of real-world applications, including cutting operations where stocks of materials such as paper or wood come in large rolls and have to be cut with minimum waste, scheduling problems in which tasks require a contiguous subset of identical resources, and container loading problems arising in the transportation of items that cannot be stacked one over the other. The strip packing problem has been attacked in the literature with several heuristic and exact algorithms, nevertheless, benchmark instances of small size remain unsolved to proven optimality. In this paper we propose a new exact method that solves a large number of the open benchmark instances within a limited computational effort. Our method is based on a Benders' decomposition, in which in the master we cut items into unit-width slices and pack them contiguously in the strip, and in the slave we attempt to reconstruct the rectangular items by fixing the vertical positions of their unit-width slices. If the slave proves that the reconstruction of the items is not possible, then a cut is added to the master, and the algorithm is reiterated. We show that both the master and the slave are strongly NP-hard problems and solve them with tailored preprocessing, lower and upper bounding techniques, and exact algorithms. We also propose several new techniques to improve the standard Benders' cuts, using the so-called combinatorial Benders' cuts, and an additional lifting procedure. Extensive computational tests show that the proposed algorithm provides a substantial breakthrough with respect to previously published algorithms. [ABSTRACT FROM AUTHOR]