In This Issue

OR Models Improve Net Present Value for the World's Largest Copper Producer

Long-term mining operations planning is a very complex task, mostly because of the large number of alternative solutions and the extensive evaluation period. Mining operations begin with the geologic estimations of the ore deposit and finish with the sale of refined mineral and its subproducts. Intermediate stages include rock size reduction, transportation and mineral concentration where waste material is removed. In “Optimizing Long-Term Production Plans in Underground and Open-Pit Copper Mines,” R. Epstein, M. Goic, A. Weintraub, J. Catalán, P. Santibáñez, R. Urrutia, R. Cancino, S. Gaete, A. Aguayo, and F. Caro present a mathematical programming model that optimizes long-term plans for multiple mines that share downstream processes. The 25-year net present value is maximized and, in contrast to previous work, the model simultaneously provides the minable ore reserves and the production schedule. The problem is formulated as a multiperiod capacitated network flow problem that takes into account geomechanical constraints. The problem's complexity calls for a strong formulation and a heuristic rounding procedure. The complete system includes a large database, a user interface, and a report generator. It has been implemented at all major divisions of Codelco, the world's largest copper producer. Since 2001, the system has been used on a regular basis and has increased the net present value of the production plan for a single mine by 5%. Moreover, integrating multiple mines provided an additional increase of 3%. The system also allows comparing several scenarios in reasonable time, something almost impossible with the traditional legacy approach. Finally, the use of this system has been of enormous help for constructing mining plans that comply with increasingly stringent ecological and environmental restrictions, in particular those related to the release of arsenic.

Guaranteed Targeted Display Advertising: Planning and Aggregation

Targeted ads—those shown only to audience segments requested by advertisers—are embedded in a wide spectrum of media, including Web pages, social media, video games, and in the not-so-distant future digital TV and electronic billboards. This huge volume of targeted ads is channeled to viewers via ad networks—intermediaries that package and sell ad space from multiple publishers' websites, video games, and other media vehicles. To match ads to appropriate audience segments, meet advertisers' goals, and ensure opportunities to serve advertising are not wasted, ad networks solve complex planning problems. In “The Planning of Guaranteed Targeted Display Advertising,” J. Turner solves the ad network's single-period planning problem that allocates impressions generated by multiple audience segments to multiple ad campaigns. By explicitly modeling audience uncertainty, forecast errors, and the ad server's execution of the plan, Turner shows when proportionally spreading impressions optimize two important quality of service metrics: the number of unique individuals reached by an ad campaign, and the variance of the number of impressions served. Low variability is particularly important for so-called “guaranteed” ad campaigns, because the ad network is contractually bound to deliver a set number of impressions in a smooth fashion over the campaign's life. Exploiting the fact that proportional spreading is desirable, Turner introduces two algorithms for intelligently aggregating the audience space while simultaneously solving the ad planning problem—a crucial technique for solving large problems.

Can Convex Programming Be Useful in the Design of Gas Distribution Networks?

Transmission of gas through pipes is governed by nonlinear equations that link flows and pressures. On the other hand, the cost of new equipment is a nonlinear function of the pipe diameters. As a result, the usual formulation of the problem of optimal design or reinforcement of gas transmission networks is a nonconvex nonlinear problem with local minima and significant numerical difficulties. In “Design and Operations of Gas Transmission Networks,” F. Babonneau, Y. Nesterov, and J.-P. Vial approximate the problem by a convex one, by a reformulation based on a minimum energy principle to model the stationary flows. They extend the minimization process to the choice of suitable diameters. Under a suitable and acceptable approximation of the structure of the investment cost function, the new problem turns out to be convex and tractable, even for very large networks.

Countering the IED Threat: Resource Allocation in Asymmetric Military Arms Races

Insurgents in places like Iraq and Afghanistan are constantly developing ever more deadly improvised explosive devices (IEDs) that have become the most serious threat for coalition forces operating in these areas. In response, the DoD has been investing large amounts in developing ever more sophisticated countermeasures (e.g., electronic devices that detonate IEDs well before the military vehicles approach them). The problem faced by the defender in such asymmetric arms races is how much and in which countermeasures to invest in each period to minimize the damage that might be caused by the attacker's weapons subject to cumulative and temporal budget constraints. In “Network Optimization Models for Resource Allocation in Developing Military Countermeasures,” B. Golany, M. Kress, M. Penn, and U. G. Rothblum formulate the defender's problem in different operational settings as deterministic constrained shortest path models and demonstrate the potential applicability and robustness of these models with respect to various scenarios.

Analytical Pricing of Asian Options with Jump Risk

Asian options have a wide application in equity, interest rate, currency, energy, and commodity, and are among the most popular path-dependent options traded in both exchanges and over-the-counter markets. However, analytical pricing of Asian options beyond the classical Black-Scholes model remains challenging. In the paper “Pricing Asian Options Under a Hyper-Exponential Jump Diffusion Model,” N. Cai and S. Kou derive a closed-form solution for the double-Laplace transform of Asian options under a general model including jumps. The Laplace transform can be inverted numerically via a two-sided Euler inversion algorithm. Numerical results indicate that the pricing method is fast, stable, and accurate.

Estimating the Probability of Large Losses

In “Sequential Importance Sampling and Resampling for Dynamic Portfolio Credit Risk,” S. Deng, K. Giesecke, and T. L. Lai develop a sequential Monte Carlo method for estimating rare-event probabilities for a portfolio of defaultable assets such as loans and corporate bonds. The method is based on a change of measure and involves a resampling mechanism. The authors propose resampling weights that lead, under technical conditions, to a logarithmically efficient simulation estimator of the probability of large portfolio losses. A numerical analysis illustrates the features of the method and contrasts it with other rare-event schemes recently developed for portfolio credit risk.

Allocating Warehouse Stock to Retailers

Much research has been carried out on how to allocate central warehouse stock among competing retailers. The risk-pooling benefit of keeping some stock centrally is not easy to consider. In “Lower Bounds and Heuristics for Supply Chain Stock Allocation,” J. Marklund and K. Rosling present a solution that typically leaves some stock at the warehouse to make possible future reallocation among retailers. The method is quite general and may be applied to many other logistical problems. It improves with the number of retailers and becomes optimal in the limit. It also renders a lower bound on the optimal cost that improves earlier results.

The Inventory Routing Problem: A Branch-Price-and-Cut Approach

The inventory routing problem (IRP) is at the heart of many supply chain problems. It integrates two well-studied but difficult problems, namely, vehicle routing and inventory management. This makes solving practical IRPs extremely difficult. In “A Branch-Price-and-Cut Algorithm for Single-Product Maritime Inventory Routing,” F. G. Engineer, K. C. Furman, G. L. Nemhauser, M. W. P. Savelsbergh, and J.-H. Song develop a branch-price-and-cut algorithm for a complex maritime inventory routing problem with pricing and cutting plane innovations. The approach solves practically sized problems motivated by the operations of an oil company to optimality, and it provides reasonable bounds for even larger instances.

Near-Optimal Policies for Vehicle Routing with Stochastic Demands

The vehicle routing problem is a basic problem in logistics, where a capacitated vehicle distributes items from a depot to several demand locations. In the more realistic stochastic version, demands are random variables with known distributions. In “Approximation Algorithms for VRP with Stochastic Demand,” A. Gupta, V. Nagarajan, and R. Ravi develop simple randomized policies that are provably near-optimal. In fact, the performance guarantee of their algorithm for stochastic demand matches the best known result for the nonstochastic case where the demands are known precisely. To obtain this tight bound, their algorithm relies on randomization in the refilling quantity.

Spotting Opportunities for Stable Coalition and Efficient Allocation

Submodularity is a combinatorial property that is frequently encountered in the payoff and/or cost functions in a variety of economic decision models. The importance of submodularity can be gauged by its more familiar continuous counterpart: convexity. Usually, the presence of submodularity would manifest a crucial orderliness: whenever submodularity is in the right place, an efficient solution can henceforth be expected. Such examples include the validation of the greedy approach to certain combinatorial optimization problems and the existence of a core distribution in cooperative game theory. Despite its importance, submodularity is hitherto deduced and dealt with on an ad hoc basis in most cases. In “Polymatroid Optimization, Submodularity, and Joint Replenishment Games,” S. He, J. Zhang, and S. Zhang present structural results in the form of parametric optimization whereby submodularity is shown to be readily associated. The new results are simple to state and easy to use. While the application of the structural results is supposedly abundant, they elaborate on a specific problem in a joint replenishment game to showcase the power of the new results, offering an assertive answer to an open question regarding this game problem.

Bounds for Combinatorial Optimization Problems Under Objective Uncertainty

Estimating bounds on the expected optimal value of a combinatorial optimization problem with random objective is known to be challenging. In fact, few tight bounds are known even for cases where the deterministic combinatorial optimization problem is efficiently solvable. An instance of a problem where tightness is provable is for the Frechet class of joint distributions that have fixed univariate marginal distributions. In “On the Complexity of Nonoverlapping Multivariate Marginal Bounds for Probabilistic Combinatorial Optimization Problems,” X. V. Doan and K. Natarajan extend this result to the class of joint distributions that have fixed nonoverlapping multivariate marginal distributions. The result helps capture partial dependency information among the random objective coefficients and extends some of the polynomial complexity results for this problem.

Independence: A Costly Illusion?

When faced with the challenge of making decisions in the presence of multiple uncertainties, a common simplifying heuristic is to assume independence among various sources. Although popular, the effect of this heuristic on the solution quality is little understood. In ”Price of Correlations in Stochastic Optimization,” S. Agrawal, Y. Ding, A. Saberi, and Y. Ye examine the risk associated with ignoring correlations by introducing a new concept of price of correlations (POC). Price of correlations captures the value of information in stochastic optimization—a small POC will imply that the efficient heuristic of assuming independence is actually robust against any adversarial correlations, whereas a large POC will suggest that it is important to invest more in data collection and learning correlations. They use function properties such as monotonicity and submodularity and employ techniques of cross-monotonic cost-sharing schemes from game theory in a novel manner to provide a tight characterization of functions with small POC. Results include small constant bounds for many popular applications such as stochastic facility location, stochastic Steiner tree network design, and stochastic bottleneck matching.

Asymptotic Optimality of Balanced Routing

Routing control is a key component in many engineering and service systems. Consider a system of parallel servers, where an arriving job can be dispatched to any one of the servers. When the arriving job can observe the queue-lengths of all servers, it is natural to apply the well-known join-the-shortest-queue (JSQ) policy, which often yields a good performance. However, retrieving the queue-length information, as required by the JSQ policy, may be costly in many situations. In their paper, “Asymptotic Optimality of Balanced Routing,” H. Chen and H.-Q. Ye study a so-called balanced routing policy; upon each job arrival, choose a few servers randomly and then send the job to the one with the shortest queue. They show through both theoretical analysis and numerical studies that such a policy asymptotically minimizes the system workload and distributes the work among all the servers evenly. Their findings demonstrate that the balanced routing policy would be an appealing option to strike a trade-off between reducing information retrieval and optimizing system performance.

Efficient Strategic Experimentation in Online Learning with Correlated Beliefs

Online learning occurs when we optimize under uncertainty in real time. Our decisions carry immediate economic rewards or costs, while also providing information that can improve future decisions. This trade-off is formalized in the well-known multiarmed bandit problem. There is a finite set of reward processes (energy portfolios, medical treatments, etc.) with unknown means, and when we activate one process (prescribe a treatment to a patient), we receive a stochastic payoff. In “The Knowledge Gradient Algorithm for a General Class of Online Learning Problems,” I. O. Ryzhov, W B. Powell, and P. I. Frazier present a novel strategy for making decisions (e.g., which treatment to prescribe) in the online setting. The technique uses an intuitive one-period look-ahead concept and leads to an elegant, computationally efficient algorithm. In experiments, this heuristic performs competitively against the best existing approximation to the optimal “Gittins index” method. Moreover, it generalizes to a broader class of problems with correlated beliefs, allowing to tackle larger and more realistic learning problems.

Estimation of a Convex Function in Multiple Dimensions

In many settings, either theoretical or modeling considerations make it natural to constrain a regression model so that the fitted function satisfies some shape constraint, such as convexity or monotonicity. Such shape-constrained regression models have been studied since the 1950s, in the presence of multidimensional monotonicity or one-dimensional convexity constraints. In “Consistency of Multidimensional Convex Regression,” E. Lim and P. W. Glynn establish that when least squares is used to estimate a multidimensional convex regression function, the estimator can be computed as the solution of a quadratic program, and they establish that the estimated convex function is a consistent estimator when the underlying “true” function is convex. They further consider the behavior of the estimator when the problem is misspecified, so that the underlying “true” function is nonconvex.

Solution Concept for Infinite-Horizon Dynamic Games

In the modern world there are many situations in which agents have numerous opportunities to act within a short interval of time, such as online auctions and trade in stock exchanges. The agents in such situations can often coordinate their actions in advance, but coordination during the game consumes too much time. In such situations, an equilibrium has to be sequential in order to handle mistakes made by players. In “Sequential Correlated Equilibria in Stopping Games,” Y. Heller models these interactions as infinite-horizon dynamic games and proposes a new solution concept for these games: a sequential uniform normal-form correlated approximate equilibrium. He makes two assumptions on these games: (1) the agents have symmetric information, and (2) each player has a “default” action, and he may take other actions only a finite number of times throughout the game. Under these assumptions, he shows that every such game admits this equilibrium.

Solving Decision Trees with Dependent Uncertainties

With the advantage of a visual interface and natural backward dynamics for analyzing strategic investment decisions, the decision tree has become one of the fundamental tools for modeling investment opportunities. However, one weakness in its practical use is that it is computationally difficult to incorporate dependencies among different uncertainties in the decision tree. In “A Copulas-Based Approach to Modeling Dependence in Decision Trees,” T. Wang and J. S. Dyer present an efficient general framework to model dependency through the use of a decision tree based on copulas. The construction of a decision tree model that portrays the multiple sources of uncertainty associated with an investment opportunity has many potential industrial applications. They show how this model could be applied in multivariate decision analysis and multivariate time series analysis with examples from the airline and oil industries.