Search

This paper proposes a new approach to solve finite-horizon optimal stopping problems for a class of Markov processes that includes one-dimensional diffusions, birth–death processes, and jump diffusions and continuous-time Markov chains obtained by time-changing diffusions and birth-and-death processes with Lévy subordinators. When the expectation operator has a purely discrete spectrum in the Hilbert space of square-integrable payoffs, the value function of a discrete optimal stopping problem has an expansion in the eigenfunctions of the expectation operator. The Bellman's dynamic programming for the value function then reduces to an explicit recursion for the expansion coefficients. The value function of the continuous optimal stopping problem is then obtained by extrapolating the value function of the discrete problem to the limit via Richardson extrapolation. To illustrate the method, the paper develops two applications: American-style commodity futures options and Bermudan-style abandonment and capacity expansion options in commodity extraction projects under the subordinate Ornstein-Uhlenbeck model with mean-reverting jumps with the value function given by an expansion in Hermite polynomials.

Game-theoretic tools are becoming a popular design choice for distributed resource allocation algorithms. A central component of this design choice is the assignment of utility functions to the individual agents. The goal is to assign each agent an admissible utility function such that the resulting game possesses a host of desirable properties, including scalability, tractability, and existence and efficiency of pure Nash equilibria. In this paper we formally study this question of utility design on a class of games termed distributed welfare games. We identify several utility design methodologies that guarantee desirable game properties irrespective of the specific application domain. Lastly, we illustrate the results in this paper on two commonly studied classes of resource allocation problems: “coverage” problems and “coloring” problems.

Quasi-Monte Carlo (QMC) methods are playing an increasingly important role in the pricing of complex financial derivatives. For models in which the prices of the underlying assets are driven by Brownian motions, the performance of QMC methods is known to depend crucially on the construction of Brownian motions. This paper focuses on the impact of various constructions. Although the Brownian bridge (BB) construction often yields very good results, as Papageorgiou pointed out, there are financial derivatives for which the BB construction performs badly [Papageorgiou, A. 2002. The Brownian bridge does not offer a consistent advantage in quasi-Monte Carlo integration. J. Complexity 18(1) 171–186]. In this paper we first extend Papageorgiou's analysis to establish an equivalence principle: if the BB construction (or any other construction) is the preferred construction for a particular financial derivative, then for any other construction, there is another financial derivative for which the latter construction is the preferred one. In this sense, all methods of construction are equivalent and no method is consistently superior to others; it all depends on the particular financial derivative. We then show how to find a good construction for a particular class of financial derivatives. In practice, our strategy is to find a good construction for an “easy” problem and then apply it to more complicated problems related to the easy one. This strategy is applied to the arithmetic Asian options (including Bermudan Asian options) based on the weighted average of the stock prices. We do this by studying a simpler problem, namely, the geometric Asian option, for which the best construction is easily available, and applying it to the arithmetic Asian option. Numerical experiments confirm the success of this strategy: whereas in QMC all the common methods (the standard method, BB, and principal component analysis) may lose their power in some situations, the new method behaves very well in all cases. Further large variance reduction can be achieved in combination with a control variate. The new method can be interpreted as a practical way of reducing the effective dimension for some class of functions.

In this paper, we examine the cross-efficiency concept in data envelopment analysis (DEA). Cross efficiency links one decision-making unit's (DMU) performance with others and has the appeal that scores arise from peer evaluation. However, a number of the current cross-efficiency approaches are flawed because they use scores that are arbitrary in that they depend on a particular set of optimal DEA weights generated by the computer code in use at the time. One set of optimal DEA weights (possibly out of many alternate optima) may improve the cross efficiency of some DMUs, but at the expense of others. While models have been developed that incorporate secondary goals aimed at being more selective in the choice of optimal multipliers, the alternate optima issue remains. In cases where there is competition among DMUs, this situation may be seen as undesirable and unfair. To address this issue, this paper generalizes the original DEA cross-efficiency concept to game cross efficiency. Specifically, each DMU is viewed as a player that seeks to maximize its own efficiency, under the condition that the cross efficiency of each of the other DMUs does not deteriorate. The average game cross-efficiency score is obtained when the DMU's own maximized efficiency scores are averaged. To implement the DEA game cross-efficiency model, an algorithm for deriving the best (game cross-efficiency) scores is presented. We show that the optimal game cross-efficiency scores constitute a Nash equilibrium point.

The standard decomposition theorem for additive and multiplicative utility functions (Pollak [Pollak, R. O. 1967. Additive von Neumann-Morgenstern utility functions. Econometrica 35 485–494.], Keeney [Keeney, R. L. 1974. Multiplicative utility functions. Opns. Res. 22 22–34.]) assumes that the outcome set is a whole product set. In this paper this assumption is relaxed, and the question of whether or not a natural revision of this theorem necessarily holds is investigated. This paper proves that two additional conditions are needed for the decomposition theorem to hold in the context where the outcome set is a subset of a Cartesian product. It is argued that these two new conditions are satisfied by a large family of subsets corresponding to significant real-world problems. Further research avenues are suggested including a generalization of this new decomposition result to nonexpected utility theories.

This paper deals with the problem of finding an estimate of the maximal loss of optimality which can arise when terminal payoffs are uncertain and policies are restricted in some way. The original non-convex optimization problem is converted to a sequence of sub-problems involving the maximization of a bilinear function over a convex region. The paper deals solely with the theoretical issues.

In this paper we present a new formulation for the Capacitated Minimal Spanning Tree (CMST) problem. One advantage of the new formulation is that it is more compact (in the number of constraints) than a well-known formulation. Additionally, we show that the linear programming relaxation of both formulations produces optimal solutions with the same cost. We present a brief discussion concerning valid inequalities for the (CMST) which are directly derived from the new formulation. We show that some of the new inequalities are not dominated by some sets of facet-inducing inequalities for the (CMST). We derive some Lagrangian relaxation-based methods from the new formulation and present computational evidence showing that reasonable improvements on the original linear programming bounds can be obtained if these methods are strengthened by the use of cutting planes. The reported computational results indicate that one of the methods presented in this paper dominates, in most of the cases, the previous best methods reported in the literature. The most significant improvements are obtained in the instances with the root in the corner.

This paper studies a topical and economically significant capacitated network design problem that arises in the telecommunications industry. In this problem, given point-to-point communication demand in a network must be met by installing (loading) capacitated facilities on the arcs: Loading a facility incurs an arc specific and facility dependent cost. This paper develops modeling and solution approaches for loading facilities to satisfy the given demand at minimum cost. We consider two approaches for solving the underlying mixed integer program: a Lagrangian relaxation strategy, and a cutting plane approach that uses three classes of valid inequalities that we identify for the problem. We show that a linear programming formulation that includes these inequalities always approximates the value of the mixed integer program at least as well as the Lagrangian relaxation bound. Our computational results on a set of prototypical telecommunication data show that including these inequalities considerably improves the gap between the integer programming formulation and its linear programming relaxation: from an average of 25% to an average of 8%. These results show that strong cutting planes can be an effective modeling and algorithmic tool for solving problems of the size that arise in the telecommunications industry.

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.

The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. This paper comprehensively analyzes games of rank one, and shows the following: (1) For a game of rank r, the set of its Nash equilibria is the intersection of a generically one-dimensional set of equilibria of parameterized games of rank r-1 with a hyperplane. (2) One equilibrium of a rank-1 game can be found in polynomial time. (3) All equilibria of a rank-1 game can be found by following a piecewise linear path. In contrast, such a path-following method finds only one equilibrium of a bimatrix game. (4) The number of equilibria of a rank-1 game may be exponential. (5) There is a homeomorphism between the space of bimatrix games and their equilibrium correspondence that preserves rank. It is a variation of the homeomorphism used for the concept of strategic stability of an equilibrium component., New in v4: detailed comparison with Theobald (2009) on page 6. Footnotes removed. Final version accepted by OPERATIONS RESEARCH

Decomposable Markov decision processes (MDPs) are problems where the stochastic system can be decomposed into multiple individual components. Although such MDPs arise naturally in many practical applications, they are often difficult to solve exactly due to the enormous size of the state space of the complete system, which grows exponentially with the number of components. In this paper, we propose an approximate solution approach to decomposable MDPs that is based on re-solving a fluid linear optimization formulation of the problem at each decision epoch. This formulation tractably approximates the problem by modeling transition behavior at the level of the individual components rather than the complete system. We prove that our fluid formulation provides a tighter bound on the optimal value function than three state-of-the-art formulations: the approximate linear optimization formulation, the classical Lagrangian relaxation formulation, and a novel, alternate Lagrangian relaxation that is based on relaxing an action consistency constraint. We provide a numerical demonstration of the effectiveness of the approach in the area of multiarmed bandit problems, where we show that our approach provides near optimal performance and outperforms state-of-the-art algorithms.

This paper is motivated by the following question: How to construct good approximation for the distribution of the solution value to linear optimization problem when the random objective coefficients follow a multivariate normal distribution? Using Stein’s Identity, we show that the least squares normal approximation of the random optimal value can be computed by estimating the persistency values of the corresponding optimization problem. We further extend our method to construct a least squares quadratic estimator to improve the accuracy of the approximation; in particular, to capture the skewness of the objective. Computational studies show that the new approach provides more accurate estimates of the distributions of project completion times compared to existing methods.

This paper develops a spectral theory of Markovian asset pricing models where the underlying economic uncertainty follows a continuous-time Markov process X with a general state space (Borel right process, or BRP) and the stochastic discount factor (SDF) is a positive semimartingale multiplicative functional of X. A key result is the uniqueness theorem for a positive eigenfunction of the pricing operator such that X is recurrent under a new probability measure associated with this eigenfunction (recurrent eigenfunction). As economic applications, we prove uniqueness of the Hansen and Scheinkman factorization of the Markovian SDF corresponding to the recurrent eigenfunction; extend the Recovery Theorem from discrete time, finite state irreducible Markov chains to recurrent BRPs; and obtain the long-maturity asymptotics of the pricing operator. When an asset pricing model is specified by given risk-neutral probabilities together with a short rate function of the Markovian state, we give sufficient conditions for the existence of a recurrent eigenfunction and provide explicit examples in a number of important financial models, including affine and quadratic diffusion models and an affine model with jumps. These examples show that the recurrence assumption, in addition to fixing uniqueness, rules out unstable economic dynamics, such as the short rate asymptotically going to infinity or to a zero lower bound trap without possibility of escaping.

This paper formulates the optimal control problem for a class of mathematical models in which the system to be controlled is characterized by a finite-state discrete-time Markov process. The states of this internal process are not directly observable by the controller; rather, he has available a set of observable outputs that are only probabilistically related to the internal state of the system. The formulation is illustrated by a simple machine-maintenance example, and other specific application areas are also discussed. The paper demonstrates that, if there are only a finite number of control intervals remaining, then the optimal payoff function is a piecewise-linear, convex function of the current state probabilities of the internal Markov process. In addition, an algorithm for utilizing this property to calculate the optimal control policy and payoff function for any finite horizon is outlined. These results are illustrated by a numerical example for the machine-maintenance problem.

This paper describes a method of obtaining results from the simulation of a countably infinite state, positive recurrent aperiodic Markov chain at a cost considerably below that required to achieve the same accuracy with pure random sampling. Reorganizing k independent epochs or tours simulated serially into k replications simulated in parallel can induce selected joint distributions across replications that produce the cost savings. The joint distributions follow from the use of rotation sampling, a special case of the antithetic variate method. The chains considered are of the band type so that for some integer δ a transition from any state i = 0, 1, 2, … can move no further than to states i − δ and i + δ. The paper shows that an estimator of interest has variance bounded above by O(δ2(ln k)4/k2) when using rotation sampling, as compared to a variance O(1/k) for independent sampling. Moreover, the mean cost of simulation based on rotation sampling has an upper bound O((δ ln k2)) as compared to a cost of at least O(k) for independent sampling. The paper also describes how one can exploit special structure in a model together with rotation sampling to improve the bound on variance for essentially the same mean cost.

This paper presents an algorithm for solving resource-constrained network scheduling problems, a general class of problems that includes the classical job-shop-scheduling problem. It uses Lagrange multipliers to dualize the resource constraints, forming a Lagrangian problem in which the network constraints appear explicitly, while the resource constraints appear only in the Lagrangian function. Because the network constraints do not interact among jobs, the problem of minimizing the Lagrangian decomposes into a subproblem for each job. Algorithms are presented for solving these subproblems. Minimizing the Lagrangian with fixed multiplier values yields a lower bound on the cost of an optimal solution to the scheduling problem. The paper gives procedures for adjusting the multipliers iteratively to obtain strong bounds, and it develops a branch-and-bound algorithm that uses these bounds in the solution of the scheduling problem. Computational experience with this algorithm is discussed.

This paper provides sufficient conditions for the optimal value in a discrete-time, finite, partially observed Markov decision process to be monotone on the space of state probability vectors ordered by likelihood ratios. The paper also presents sufficient conditions for the optimal policy to be monotone in a simple machine replacement problem, and, in the general case, for the optimal policy to be bounded from below by an easily calculated monotone function.

In this paper, we present an efficient numerical method for calculating the waiting time and idle time distributions of the arithmetic GI/G/1 queue. Our method is based on the Wiener-Hopf factorization, which is briefly reviewed. Compared to the related methods suggested in the literature, our method seems to perform very well, and it is often faster by several orders of magnitude. A number of numerical examples conclude the paper.

This paper develops dynamic-programming and other shortest-route algorithms for optimizing sequentially patterned questioning procedures, called diagnostic questionnaires. It uses graph-theoretic methods and solves certain combinatorial problems associated with the Catalan numbers. The paper obtains general properties of optimal questionnaires, including an ordering relation, a convexity result, and the determination of essentially complete classes of questionnaires. It explores a logarithmic charging scheme in detail and obtains a minimal result. Finally, the paper examines the relation with Huffman coding of information theory, and a simple method of Shannon efficiency.

This paper describes a method of obtaining results from the simulation of an n + 1 finite state positive recurrent aperiodic Markov chain at a cost considerably less than that required by pure random sampling to achieve the same accuracy. The method reorganizes k independent epochs (or tours) simulated serially into k replications simulated in parallel, and therefore produces cost savings by inducing selected joint distributions across replications. The joint distributions are derived by the use of rotation sampling, a special case of the antithetic variate method. The paper first describes the method as it applies to a finite state nearest neighbor chain. In particular, it shows that even for independent parallel replications, the cost of achieving a specified accuracy with serial simulation, relative to the cost for parallel simulation, has a lower bound O(k1/2/n) as k → ∞. When rotation sampling is used, this bound is O(k2/n(ln k)3). A simulation of the M/M/1 queueing model with finite capacity n illustrates the effectiveness of the technique for selected values of k, n and activity level ρ. The paper then describes how this variance reducing technique applies to the simulation of a more general finite state chain. In particular, the lower bound on relative cost is O(k2/ϕ(ln k)3), where ϕ is the total number of transitions that can occur from all n + 1 states. A computer program that implements the method for the general finite state case is briefly described.

This paper introduces a stochastic model and uses the system point theory for queues and dams to obtain the long range probability distribution function of consumer response in a single ad campaign with Poisson repetitions. The consumer response is treated analogously to the content of a dam with a general release rule and stochastically decreasing increments from higher contents. This approach to repetition effects provides an alternative technique to contemporary marketing models. The paper also discusses applications to the choice of media schedules that optimize market response and generaliza- tions of the model.

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.

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.

A simple extension of the Lagrange optimization method is valuable in allocating defense resources among a large number of independent defense locations. This kind of allocation problem is complicated by the fact that the attacker can optimize his attack against whatever defense is chosen. This paper describes an extended or double Lagrange method, which provides strictly optimal allocations for the attacker, but not necessarily for the defender. Nevertheless, by careful use of the method, it is possible to obtain defense allocations that are at least approximately optimum. The major part of the paper provides a technique for verifying results and computing bounds for the error—a technique that is necessary because the uncritical application of the method can occasionally give results that are far from optimum.

In this paper we obtain a series expansion for the expected fraction of damage to a circular target when it is assumed that a salvo of n rounds is delivered onto the target area with a noncircular normal or gaussian distribution and the damage function for each round can be represented by a noncircular exponential square fall-off law. The results are easily extended to an elliptical-shaped target. The aim of the paper is to obtain explicit approximations for target damage.

The approach to the traffic-flow problem based on an integral differential equation of the Boltzmann type which has been considered by one of us (I P ) in a recent paper is further developed. The possibility of passing is explicitly introduced into the equation for the velocity distribution function. As in the previous paper, it is shown that at sufficiently high concentration a collective flow process must take place. In order to study more specifically the effects of one car on another, we define reduced n-car distribution functions giving the probability of finding a cluster of n cars all having the same velocity. We derive an equation for the evolution of this distribution function. Study of it yields some information as to the way traffic changes from relatively free flow to completely hindered, “condensed” flow.

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 which 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.

How best to allocate offensive weapons of various types to a group of targets in order to maximize the payoff constitutes a very important problem for optimizing strategies of defense. Solutions to the allocation problem, for the case where one type of weapon is involved, exist in the literature. Essentially these solutions fall into two categories digital solutions which yield integral results, and analytical solutions, based on the Lagrange Multipliers, which treat the number of weapons as a continuous variable and thus produce fractional answers. Whenever the number of weapons is large compared with the number of targets, analytical methods are preferred to digital ones because they achieve a saving in computer time at a negligible loss of accuracy. On the other hand, if the number of weapons is of the same order of magnitude as the number of targets, digital methods are preferable because they yield exact answers, as opposed to analytical solutions that produce rounding errors too large to render the results useful. The object of this paper is to generalize an analytical solution to the case where the attacker has more than one type of weapon available for assignment to an undefended or virtually undefended target complex. Defense strategies are not included. The paper presents a computational example where three types of weapons, each with a different number of attacking vehicles, are allocated to twenty targets. This example also permits a comparison between the fractional results of an analytical solution and the integral values obtained by a computer-oriented algorithm.

This paper deals with a nonstationary discrete-time Markov process whose transition probabilities vary periodically in time. Each transition results in a reward that varies within the same cycle as the transition matrix. For infinite processes a policy-iteration algorithm is developed that effectively determines an optimal policy maximizing the total discounted reward. The paper represents an extension of R. A. Howard's policy-iteration technique for stationary Markov processes. A numerical example is given in which the developed iteration algorithm is demonstrated.

This paper examines Markovian decision processes in which the transition probabilities corresponding to alternative decisions are not known with certainty. The processes are assumed to be finite-state, discrete-time, and stationary. The rewards axe time discounted. Both a game-theoretic and the Bayesian formulation are considered. In the game-theoretic formulation, variants of a policy-iteration algorithm are provided for both the max-min and the max-max cases. An implicit enumeration algorithm is discussed for the Bayesian formulation where upper and lower bounds on the total expected discounted return are provided by the max-max and max-min optimal policies. Finally, the paper discusses asymptotically Bayes-optimal policies.

This paper combines the monotonic-penalty-function and surrogate models into a general model called the penalty-function/surrogate model. It unifies and generalizes the central theorems of earlier papers, and provides some new theorems that can be specialized to the Lagrangian penalty-function model (GLM) or to linear surrogates.

This paper describes a new method for solving a general linear programming problem. THIS PAPER presents a method that permits movement in either the feasible and/or infeasible regions of the given linear programming problem in the search for the optimal solution. The initial point, too, could thus be either feasible or infeasible, and is therefore invariably available from the problem itself. This, in turn, obviates the necessity of starting always with a feasible point, as is prerequisite with some methodsin particular, the simplex method of linear programming. The concepts of Euclidean distance and angle have been used to derive the distances of all the bounding hyperplanes from the origin in the increasing direction of the normal to the jZjj hyperplane with a view to selecting the pivotal row as the particular bounding hyperplane (discussed later) that is nearest to the origin. Once the pivotal row has thus been chosen, it is a trivial matter to select the appropriate pivotal column (the axis) in different iterations. The pivotal element so obtained is used for performing the usual Gaussian eliminational transformations. The method is iterative, with each iteration performing a sequence of steps as detailed in the algorithm given in Section 5. Three examples have been worked out in Section 6 to explain, as well as illustrate, the power of the method.

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.

We consider the information relaxation approach for calculating performance bounds for stochastic dynamic programs (DPs). This approach generates performance bounds by solving problems with relaxed nonanticipativity constraints and a penalty that punishes violations of these nonanticipativity constraints. In this paper, we study DPs that have a convex structure and consider gradient penalties that are based on first-order linear approximations of approximate value functions. When used with perfect information relaxations, these penalties lead to subproblems that are deterministic convex optimization problems. We show that these gradient penalties can, in theory, provide tight bounds for convex DPs and can be used to improve on bounds provided by other relaxations, such as Lagrangian relaxation bounds. Finally, we apply these results in two example applications: first, a network revenue management problem that describes an airline trying to manage seat capacity on its flights; and second, an inventory management problem with lead times and lost sales. These are challenging problems of significant practical interest. In both examples, we compute performance bounds using information relaxations with gradient penalties and find that some relatively easy-to-compute heuristic policies are nearly optimal.

Random search algorithms are often used to solve discrete optimization-via-simulation (DOvS) problems. The most critical component of a random search algorithm is the sampling distribution that is used to guide the allocation of the search effort. A good sampling distribution can balance the trade-off between the effort used in searching around the current best solution (which is called exploitation) and the effort used in searching largely unknown regions (which is called exploration). However, most of the random search algorithms for DOvS problems have difficulties in balancing this trade-off in a seamless way. In this paper we propose a new scheme that derives a sampling distribution from a fast fitted Gaussian process based on previously evaluated solutions. We show that the sampling distribution has the desired properties and can automatically balance the exploitation and exploration trade-off. Furthermore, we integrate this sampling distribution into a random research algorithm, called a Gaussian process-based search (GPS) and show that the GPS algorithm has the desired global convergence as the simulation effort goes to infinity. We illustrate the properties of the algorithm through a number of numerical experiments.

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.

This paper considers a continuous-review, single-product, production-inventory system with a constant replenishment rate, compound Poisson demands, and lost sales. Two objective functions that represent metrics of operational costs are considered: (1) the sum of the expected discounted inventory holding costs and lost-sales penalties, both over an infinite time horizon, given an initial inventory level; and (2) the long-run time average of the same costs. The goal is to minimize these cost metrics with respect to the replenishment rate. It is, however, not possible to obtain closed-form expressions for the aforementioned cost functions directly in terms of positive replenishment rate (PRR). To overcome this difficulty, we construct a bijection from the PRR space to the space of positive roots of Lundberg's fundamental equation, to be referred to as the Lundberg positive root (LPR) space. This transformation allows us to derive closed-form expressions for the aforementioned cost metrics with respect to the LPR variable, in lieu of the PRR variable. We then proceed to solve the optimization problem in the LPR space and, finally, recover the optimal replenishment rate from the optimal LPR variable via the inverse bijection. For the special cases of constant or loss-proportional penalty and exponentially distributed demand sizes, we obtain simpler explicit formulas for the optimal replenishment rate.

One long-standing challenge in both the optimization and investment communities is to devise an efficient algorithm to select a small number of assets from an asset pool such that a portfolio objective is optimized. This cardinality constrained investment situation naturally arises due to the presence of various forms of market friction, such as transaction costs and management fees, or even due to the consideration of mental cost. Unfortunately, the combinatorial nature of such a portfolio selection problem formulation makes the exact solution process NP-hard in general. We focus in this paper on the cardinality constrained mean-variance portfolio selection problem. Instead of tailoring such a difficult problem into the general solution framework of mixed-integer programming formulation, we explore the special structures and rich geometric properties behind the mathematical formulation. Applying the Lagrangian relaxation to the primal problem results in a pure cardinality constrained portfolio selection problem, which possesses a symmetric property, and to which geometric approaches can be developed. Different from the existing literature that has primarily focused on some direct relaxations of the cardinality constraint, we consider modifying the objective function to some separable relaxations, which are immune to the hard cardinality constraint. More specifically, we develop efficient lower bounding schemes by using the circumscribed box, the circumscribed ball, and the circumscribed axis-aligned ellipsoid to approximate the objective contour of the problem. In particular, all these cardinality constrained relaxation problems can be solved analytically. Furthermore, we derive efficient polynomial-time algorithms for the corresponding dual search problems. Most promisingly, the lower bounding scheme using the circumscribed axis-aligned ellipsoid leads to a semidefinite programming (SDP) formulation and offers a sharp bound and high-quality feasible solution. By integrating these lower bounding schemes into a branch-and-bound algorithm (BnB), our solution scheme outperforms CPLEX significantly in identifying the exact optimal portfolio.

This paper investigates a Lagrangian dual problem for solving the optimal power flow problem in rectangular form that arises from power system analysis. If strong duality does not hold for the dual, we propose two classes of branch-and-bound algorithms that guarantee to solve the problem to optimality. The lower bound for the objective function is obtained by the Lagrangian duality, whereas the feasible set subdivision is based on the rectangular or ellipsoidal bisection. The numerical experiments are reported to demonstrate the effectiveness of the proposed algorithms. We note that no duality gap is observed for any of our test problems.

When decisions are made in the presence of high-dimensional stochastic data, handling joint distribution of correlated random variables can present a formidable task, both in terms of sampling and estimation as well as algorithmic complexity. A common heuristic is to estimate only marginal distributions and substitute joint distribution by independent (product) distribution. In this paper, we study possible loss incurred on ignoring correlations through a distributionally robust stochastic programming model, and we quantify that loss as price of correlations (POC). Using techniques of cost sharing from game theory, we identify a wide class of problems for which POC has a small upper bound. To our interest, this class will include many stochastic convex programs, uncapacitated facility location, Steiner tree, and submodular functions, suggesting that the intuitive approach of assuming independent distribution acceptably approximates the robust model for these stochastic optimization problems. Additionally, we demonstrate hardness of bounding POC via examples of subadditive and supermodular functions that have large POC. We find that our results are also useful for solving many deterministic optimization problems like welfare maximization, k-dimensional matching, and transportation problems, under certain conditions.

In two-moment decomposition approximations of queueing networks, the arrival process is modeled as a renewal process, and each station is approximated as a GI/G/1 queue whose mean waiting time is approximated based on the first two moments of the interarrival times and the service times. The departure process is also approximated as a renewal process even though the autocorrelation of this process may significantly affect the performance of the subsequent queue depending on the traffic intensity. When the departure process is split into substreams by Markovian random routing, the split processes typically are modeled as independent renewal processes even though they are correlated with each other. This cross correlation might also have a serious impact on the queueing performance. In this paper, we propose an approach for modeling both the cross correlation and the autocorrelation by a three-moment four-parameter decomposition approximation of queueing networks. The arrival process is modeled as a nonrenewal process by a two-state Markov-modulated Poisson process, viz., MMPP(2). The cross correlation between randomly split streams is accounted for in the second and third moments of the merged process by the innovations method. The main contribution of the present research is that both the cross correlation and the autocorrelation can be modeled in parametric decomposition approximations of queueing networks by integrating the MMPP(2) approximation of the arrival/departure process and the innovations method. We also present numerical results that strongly support our refinements.

This paper presents a robust optimization model for n-person finite state/action stochastic games with incomplete information. We consider nonzero sum discounted stochastic games in which none of the players knows the true data of a game, and each player adopts a robust optimization approach to address the uncertainty. We call these games discounted robust stochastic games. Such games allow us to use simple uncertainty sets for the unknown data and eliminate the need to have an a-priori probability distribution over a set of games. We prove the existence of equilibrium points and propose an explicit mathematical programming formulation for an equilibrium calculation. We illustrate the use of discounted robust stochastic games in a single server queueing control problem.

We investigate the (S − 1, S) inventory policy under stuttering Poisson demand and generally distributed lead time when the excess demand is lost. We correct results presented in Feeney and Sherbrooke's seminal paper [Feeney, G. J., C. C. Sherbrooke. 1966. The (S − 1, S) inventory policy under compound Poisson demand. Management Sci. 12(5) 391–411] and note that the stationary distribution of units on order for the general compound Poisson demand case is still an open question.

Reliable facility location models consider unexpected failures with site-dependent probabilities, as well as possible customer reassignment. This paper proposes a compact mixed integer program (MIP) formulation and a continuum approximation (CA) model to study the reliable uncapacitated fixed charge location problem (RUFL), which seeks to minimize initial setup costs and expected transportation costs in normal and failure scenarios. The MIP determines the optimal facility locations as well as the optimal customer assignments and is solved using a custom-designed Lagrangian relaxation (LR) algorithm. The CA model predicts the total system cost without details about facility locations and customer assignments, and it provides a fast heuristic to find near-optimum solutions. Our computational results show that the LR algorithm is efficient for mid-sized RUFL problems and that the CA solutions are close to optimal in most of the test instances. For large-scale problems, the CA method is a good alternative to the LR algorithm that avoids prohibitively long running times.

Markov decision processes are an effective tool in modeling decision making in uncertain dynamic environments. Because the parameters of these models typically are estimated from data or learned from experience, it is not surprising that the actual performance of a chosen strategy often differs significantly from the designer's initial expectations due to unavoidable modeling ambiguity. In this paper, we present a set of percentile criteria that are conceptually natural and representative of the trade-off between optimistic and pessimistic views of the question. We study the use of these criteria under different forms of uncertainty for both the rewards and the transitions. Some forms are shown to be efficiently solvable and others highly intractable. In each case, we outline solution concepts that take parametric uncertainty into account in the process of decision making.

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.

In an incremental optimization problem, we are given a feasible solution x0 of an optimization problem P, and we want to make an incremental change in x0 that will result in the greatest improvement in the objective function. In this paper, we study the incremental optimization versions of six well-known network problems. We present a strongly polynomial algorithm for the incremental minimum spanning tree problem. We show that the incremental minimum cost flow problem and the incremental maximum flow problem can be solved in polynomial time using Lagrangian relaxation. We consider two versions of the incremental minimum shortest path problem, where increments are measured via arc inclusions and arc exclusions. We present a strongly polynomial time solution for the arc inclusion version and show that the arc exclusion version is NP-complete. We show that the incremental minimum cut problem is NP-complete and that the incremental minimum assignment problem reduces to the minimum exact matching problem, for which a randomized polynomial time algorithm is known.

A complex product, such as a software system, is often inspected more than once in a sequential manner to further improve its quality and reliability. In such a case, a particularly important task is to accurately estimate the number of errors still remaining in the product after a series of multiple inspections. In the paper, we first develop a maximum likelihood method of estimating both the number of undiscovered errors in the product and the detection probability. We then compare its performance with that of an existing estimation method that has several limitations. We also propose a Bayesian method with noninformative priors, which performs very well in a Monte Carlo simulation study. As the prior knowledge is elicited and incorporated in the analysis, the prediction accuracy of the Bayesian method improves even further. Thus, it would be worthwhile to use various estimation methods and compare their estimates in a specific inspection environment.

In this paper, we propose to solve the linear multicommodity flow problem using a partial Lagrangian relaxation. The relaxation is restricted to the set of arcs that are likely to be saturated at the optimum. This set is itself approximated by an active set strategy. The partial Lagrangian dual is solved with Proximal-ACCPM, a variant of the analytic center cutting-plane method. The new approach makes it possible to solve huge problems when few arcs are saturated at the optimum, as appears to be the case in many practical problems.

This paper develops algorithms for the pricing of discretely sampled barrier, lookback, and hindsight options and discretely exercisable American options. Under the Black-Scholes framework, the pricing of these options can be reduced to evaluation of a series of convolutions of the Gaussian distribution and a known function. We compute these convolutions efficiently using the double-exponential integration formula and the fast Gauss transform. The resulting algorithms have computational complexity of O(nN), where the number of monitoring/exercise dates is n and the number of sample points at each date is N, and our results show the error decreases exponentially with N. We also extend the approach and provide results for Merton’s lognormal jump-diffusion model.