In This Issue
Scheduling for Selfish Users
Given a choice of a machine at a cloud computing provider, a user would naturally place a job on the machine that would finish it the soonest. However, whether this behavior of users produces a good overall outcome, such as quick completion of all jobs, depends on the strategy of the provider for determining the execution order of the jobs on each machine. In “Optimal Coordination Mechanisms for Unrelated Machine Scheduling,” Y. Azar, L. Fleischer, K. Jain, V. Mirrokni, and Z. Svitkina study different local ordering policies for selfish scheduling and determine lower and upper bounds for the performance of resulting equilibria compared to the global optimum solution.
Using Convex Programs to Characterize Network Bargaining Games
Understanding the effects of network structure on the equilibrium division of surplus is an old question in both economics and operations research. However, for tractability, previous efforts have mainly focused on cooperative bargaining solutions. In “Coalitional Bargaining in Network,” T. Nguyen develops a convex programming technique to characterize the equilibria of a noncooperative bargaining game with a general coalition structure. The author applies this framework to several settings to analyze the influence of an agent’s position in the network on her bargaining power. For example, in a trading network involving middlemen, it is shown that bargaining power coincides with congestion in a corresponding traffic network. Most importantly, the new approach to characterize the unique equilibrium payoff introduced in this paper can likely be applied to other economic and market settings that have previously been difficult to model.
A Random Utility Formulation of Elimination by Aspects
Introduced by Tversky in the 1970s, Elimination by Aspects (EBA) allows choice to violate even weak forms of independence of irrelevant alternatives. Although it is considered to represent the process of choice more faithfully than models assuming utility-maximizing consumers, EBA has seen little use, possibly because it is not based on an error theory and appears removed from standard choice models. In “Error Theory for Elimination by Aspects,” R. Kohli and K. Jedidi obtain an error theory for EBA and show that it generalizes multinomial logit and rank-ordered logit models. EBA is consistent with the assumption that consumers maximize utilities when selecting the sequence of aspects used to eliminate alternatives. The model can be estimated by modifying maximum likelihood procedures for logit models, and can be extended to allow aspect utilities to be functions of covariates. Latent class and random effects versions of EBA can allow heterogeneity in EBA rules used by consumers.
Optimizing Bank Regulatory Actions
On and after the global financial crisis, banking regulations have been playing an increasingly important role in maintaining the sound global financial system. In “An Excursion-Theoretic Approach to Regulator’s Bank Reorganization Problem,” M. Egami and T. Oryu propose a model that analyzes the cost and effect of the Prompt Corrective Action (PCA), which requires that undercapitalized banks improve the leverage ratio. Using the excursion theory for spectrally negative Lévy processes, the model explicitly deals with the bank’s leverage ratio that triggers a PCA. They compute various costs associated with PCA’s including cash infusion from public funds, and obtain the optimal threshold level that initiates a PCA and that minimizes the total cost. In particular, the paper demonstrates how costly it would be to rescue a bank that is “too big to fail.”
Pricing Asian Options under a Unified Framework
Asian options are among the most popular path-dependent options that are actively traded in the financial markets. In the paper “A General Framework for Pricing Asian Options under Markov Processes,” N. Cai, Y. Song and S. Kou propose a general framework for pricing both continuously and discretely monitored Asian options under one-dimensional Markov processes. They derive the double transform of the Asian option prices in terms of the unique bounded solutions to the related functional equations, and the analytical solutions for these transforms can be further obtained via matrix inversion under continuous-time Markov chains. Based on the above results, the authors develop a general pricing method which is shown to be accurate and fast under popular models, including the CIR model, the CEV model, Merton’s jump diffusion model, the double-exponential jump diffusion model, the variance gamma model and the CGMY model.
The Power of Limited Flexibility is Robust
In today’s complex consumer markets with volatile demand, firms have focused on an operations strategy, process flexibility, to better match supply with uncertain demand. The long chain, a class of structures with limited flexibility, has proven to be very effective for specific probability distributions of the random demand. However, it is not clear how sensitive its performance is to the choice of different demand distributions. In “Process flexibility: A distribution-free bound on the performance of k-chain,” X. Wang and J. Zhang demonstrate that the effectiveness of the long chain is robust under different demand distributions in asymptotically large systems. Specifically, they subsume the full probability distribution of the random demand into its first and second moments, and obtain in closed-form a sharp, distribution-free lower bound on the ratio of the expected sales of the k-chain relative to that of full flexibility.
Equilibrium Analysis for Price and Assortment Competition
In an industry, firms often compete simultaneously on prices as well as the product assortment offered to the market. In “Multi-Product Price and Assortment Competition,” A. Federgruen and M. Hu characterize the industry’s equilibrium choices under a general but parsimonious demand model. The model employs the unique extension of the commonly-used affine demand functions which satisfies an intuitive regularity condition: under any given price vector, when some product is priced out of the market, any increase of its price has no impact on the demand volumes. Under this demand model, they provide a full characterization of equilibrium prices and product assortments, for an arbitrary combination of cost rates and a general asymmetric price sensitivity matrix. While there may be multiple price equilibria, the equilibrium product assortments and sales volumes are shown to be unique. The equilibria can be computed, with only a few matrix multiplications and inverses, in some cases combined with the solution of a single linear program. They also derive a closed-form expression for the matrix of all direct and cross-product pass-through rates, along with even simpler upper and lower bound matrices.
Managing Perishable Inventory under Uncertainty
Perishable products, such as fresh food, pharmaceuticals, and blood banks are ubiquitous and an indispensable part of our society, and spoilage and outdating represent a major threat to the profitability of companies such as grocery retailers. However, the analysis of dynamic perishable inventory systems is notoriously difficult in both theory and computation due to the multi-dimensional nature. Indeed, the optimal control policies are very complex even in the case of independent and identically distributed demands, and the computation of optimal policies using dynamic program is in general intractable due to the well-known curse-of-dimensionality. In “Approximation Algorithms for Perishable Inventory Systems,” X. Chao, X. Gong, C. Shi, and H. Zhang develop approximation algorithms for perishable stochastic inventory systems with arbitrarily correlated demand processes that admit theoretical worst-case performance guarantees. They demonstrate through an extensive numerical study that their algorithms perform consistently near-optimal.
Utilizing Stockout Times to Help Manage Nonperishable Inventories
Utilizing product stockout times can help to improve the accuracy of demand forecasting. In “Managing Nonperishable Inventories with Learning about Demand Arrival Rate through Stockout Times,” A. Bensoussan and P. Guo consider how to utilize this information to help manage nonperishable inventories. The paper formulates the problem as a dynamic programming model with demand learning. The paper demonstrates that the optimal inventory order-up-to level with observable stockout times is larger than the one with observable lost sales and more information improves the system performance.
Near Optimal Decision Making in an Uncertain Environment
In recent years, decision rules have been established as the preferred solution method for addressing computationally demanding, multistage adaptive optimization problems. Despite their success, existing decision rules (a) are typically constrained by their a priori design and (b) do not incorporate in their modeling adaptive binary decisions. The paper “Design of Near Optimal Decision Rules in Multistage Adaptive Mixed-Integer Optimization” by D. Bertsimas and A. Georghiou addresses these problems by deriving the structure for optimal decision rules for continuous and binary decisions, and proposes a methodology for the optimal design of such decision rules using mixed-integer optimization. This work demonstrates the effectiveness of the method in the context of two multistage inventory control problems, providing global lower bounds and showing that the proposed approach is (i) practically tractable and (ii) provides high quality solutions that outperform alternative methods.
Robust Optimization using Nonrobust Solvers
The robust optimization framework offers a practical and scalable approach to optimization under uncertainty. However, in many cases, a straightforward solution of the robust optimization problem of a certain type requires solving an optimization problem of a more complicated type, which might even be NP-hard in some cases. In the paper “Oracle-Based Robust Optimization via Online Learning,” A. Ben-Tal, E. Hazan, T. Koren, and S. Mannor develop a new method for approximately solving a robust optimization problem using a black-box oracle (i.e., a solver) that solves the original, nonrobust problem. The new algorithms are based on primal-dual methodology and use tools from online convex optimization.
Estimating Pure Characteristics Demand Models with Pricing
Discrete-choice demand models are important and fundamental tools for understanding consumers’ choice behavior, and for analyzing firms’ operations and pricing strategies. One central task in estimating demand models is, based on observed data, to infer consumers’ preferences on observed product characteristics. In “A Constructive Approach to Estimating Pure Characteristics Demand Models with Pricing,” J.-S. Pang, C.-L. Su, and Y.-C. Lee consider such an estimation problem for the pure characteristics demand model. They first characterize consumers’ purchase decisions by a system of complementarity constraints. This new characterization leads to smooth approximated market share equations and allows us to cast the corresponding generalized method of moments (GMM) estimation problem as a mathematical program with complementarity constraints. They also extend this estimation framework to incorporate an endogenous pricing mechanism that captures the competitive profit maximization behavior of the producing firms. They provide existence results of a solution for the GMM estimator and present numerical results to demonstrate the computational effectiveness of our approach.
Project Portfolio Selection to Meet Target Return
One-fifth of the world’s economic activity is organized as a project. A major component of successful project management is selection of the right projects. An important perspective on project selection is achievement of a target return. In “Managing Underperformance Risk in Project Portfolio Selection,” N. G. Hall, D. Z. Long, J. Qi, and M. Sim propose a robust optimization model to consider the target return, where there is less than full distributional information about uncertain returns. Their model incorporates both correlation and interaction effects among projects, and is solved by Benders decomposition techniques. Comparisons with several classical portfolio optimization methods demonstrate the value of this approach. A heuristic approach is also provided, by which managers can quickly solve the optimization problem when there is only a single constraint for the budget.
Towards A Tractable Analysis of Queueing Networks via Robust Optimization
Given the modeling power of probability, a substantial literature of queueing theory was developed which views queueing primitives as renewal processes. While exponentiality leads to a tractable theory, assuming general distributions yields considerable difficulty with respect to analyzing queueing networks. In “Robust Queueing Theory,” C. Bandi, D. Bertsimas, and N. Youssef revisit the problem of analyzing single-class queueing systems and propose an optimization-based framework. The key idea is to model the uncertainty via polyhedral sets inspired by the probability limit laws and cast the performance analysis as a robust optimization problem. This approach leads to closed form bounds on the system times in multi-server queues and extends to analyzing steady-state queueing networks with possible heavy-tailed primitives. This approach yields accurate results relative to simulation and is by and large insensitive to the number of servers per queue, network size, degree of feedback and traffic intensity.
Models with Shelf-Age and Delay-Dependent Costs
After initial debates in pioneering books on inventory planning, in particular Hadley and Whitin (1963) and Naddor (1966), inventory theory quickly settled on the paradigm that inventory costs are assessed as a function of the total inventory, irrespective of its age composition; similarly backlogging costs are invariably assumed to be determined as a function of the total backlog size. However, this paradigm fails to be adequate in many applications: for example, holding costs often depend on time varying purchase prices and the interest rate that prevails at the time of purchase, so that inventory costs depend on the shelf ages of the units in stock. Similarly, under various financing schemes, the capital costs for a given order accumulate at rates that increase as a function of the time elapsed since the delivery of the order. In “Inventory Models with Shelf Age and Delay dependent Inventory Costs,” A. Federgruen and M. Wang show how any model with such cost structures may be transformed into an equivalent standard model with level dependent costs; this equivalency is pursued for models with full and partial backlogging and lost sales.
A Stochastic Programming Based Approach to Controlling Assemble-to-Order Inventory Systems
Determining an optimal control policy for Assemble-to-Order Inventory Systems, which involves both component replenishment and allocation decisions, is a difficult problem in general. The prevailing approach had been to make simplifying assumptions that involve the use or partial use of FIFO allocation and optimize other parameters. While tractable to analyze, FIFO and its variants are often inefficient for minimizing inventory cost. In “Asymptotically Optimal Inventory Control for Assemble-to-Order Systems with Identical Lead Times,” M. I. Reiman and Q. Wang present a new approach based on stochastic-programming. Starting from an ideal (infeasible) solution that sets a lower bound on the inventory cost, they provide feasible policies to mimic that solution. For systems with identical component lead times and a general Bill of Materials, they prove that their policies are asymptotically optimal on the diffusion scale: as the lead time increases, the percentage difference between the inventory cost under their policies and the minimum cost converges to zero.
Multiserver Priority Queue
In practice, prioritization of service often comes in systems with multiple agents serving jobs with heterogeneous service characteristics. Thus there is a need for the analysis of multi-server multi-priority systems with different service times. In “M/M/c Queue with Two Priority Classes,” J. Wang, O. Baron, and A. Scheller-Wolf consider these settings under a preemptive service discipline. They are the first to develop exact algorithms to calculate various performance measures for this system. Using these algorithms, they also: provide insights on the relative effect of reducing the service times of either priority class on the mean times in system; compare the performance of a system having many slow servers with one with a single fast server; and demonstrate that the square root staffing rule can maintain fixed performances for the low-priority customers while providing supreme service to the high-priority ones.
