In This Issue
Scheduling Extraction in an Open-pit Mine to Maximize Profit
In “Hierarchical Benders Decomposition for Open-pit Mine Block Sequencing,” T. Vossen, K. Wood and A. Newman show that the standard integer program for a common version of this classical, resource-constrained production scheduling problem is unnecessarily restrictive. In particular, certain binary variables can be made continuous, while still maintaining critical pit-wall slopes at acceptable angles. To solve the new mixed-integer program, the authors create a “hierarchical” version of nested Benders decomposition that incorporates time-aggregated sub-models to improve empirical convergence and to enable a more flexible decomposition. For example, instead of recursively decomposing the model into a master problem at time period t and a single subproblem that estimates the “cost to go from period t” the hierarchical method can do this: recursively decompose the model into a master problem at t and two independent subproblems, one estimating the cost to go from t and the other estimating “the cost to get to t.” Nested Benders decomposition typically solves linear programs, but a branch-and-bound heuristic customized for the hierarchical decomposition solves standard test problems accurately. Indeed, to the authors’ knowledge, computational results are the best reported in the literature for models with both lower- and upper-bounding resource constraints.
Combining Spot Market and Futures Market for Secondary Spectrum Trading
In “Combining Spot and Futures Markets: A Hybrid Market Approach to Dynamic Spectrum Access,” L. Gao, B. Shou, Y.-J. Chen, and J. Huang propose and analyze a hybrid secondary spectrum market consisting of a futures market and a spot market, where secondary users (buyers) purchase under-utilized licensed spectrum from primary spectrum regulator (seller), either through the pre-defined contracts via the futures market, or through the spot transactions via the spot market. We study the optimal spectrum trading/allocation problem that aims to maximize the secondary spectrum utilization efficiency. To solve this challenging problem, we first derive an off-line optimal allocation policy that maximizes the ex-ante expected spectrum utilization efficiency based on the stochastic distribution of network information. Then, we propose an on-line VCG auction that determines the real-time allocation and pricing of every spectrum based on the realized network information and the pre-derived off-line policy. We further propose a heuristics approach based on an on-line VCG-like mechanism with polynomial-time complexity for the scenario with spatial frequency reuse, and characterize the corresponding performance loss bound analytically.
Efficient Ads
In “Efficient Advert Assignment,” F. Kelly, P. Key, and N. Walton develop a framework for the analysis of large-scale ad-auctions. For this pay-per-click market, an efficient mechanism that maximizes social welfare is described. It is shown that the social welfare optimization can be solved in separate optimizations conducted on the time-scales relevant to the search platform and advertisers. Here, on each search occurrence, the platform solves an assignment problem and, on a slower time-scale, each advertiser submits a bid which matches its demand for click-throughs with supply. Importantly, knowledge of global parameters, such as the distribution of search terms, is not required when separating the problem in this way. Exploiting the information asymmetry between the platform and advertiser, it describes a simple mechanism which incentivizes truthful bidding and has a unique Nash equilibrium that is socially optimal and implements the decomposition.
Managing Conflicts between Commercials Assigned to TV Program Breaks
Selling commercial air time to advertisers is a critical task for television networks, as advertising revenues represent an important part of their income. Several problems arise in this context, at different decisional levels, like negotiating advertising contracts, assigning commercials to breaks in each TV program, and eventually scheduling commercials within each break. In “New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials,” G. Giallombardo, H. Jiang, and G. Miglionico introduce three new and efficient optimization models for the Conflict Resolution Problem, arising in the allocation of commercials to TV breaks, as broadcasters have to account for competition-avoidance requirements issued by advertisers, whose aim is to have commercials promoting highly competing products assigned to different breaks. They provide theoretical and numerical evidence of the improved efficiency of the proposed models in terms of both solution quality and computation time, making these models practical for use at broadcast companies.
Solving Large-Scale Dynamic Portfolio Optimization Problems with Taxes
Large-scale dynamic portfolio optimization problems with taxes are very challenging to solve because the tax owed whenever a security is sold depends on the cost-basis. This results in high-dimensional problems which cannot be solved exactly except in the case of very small stylized problems. In “Tax Aware Asset Allocation,” M. Haugh, G. Iyengar and C. Wang consider exact and average cost-basis problems when there are differential tax rates for long- and short-term capital gains. They develop simple heuristic trading policies and use information relaxation techniques to assess the performance of these trading policies by constructing unbiased lower and upper bounds on the (unknown) optimal value function. The principal contribution of their work is in demonstrating that while the primal problem remains very challenging to solve exactly, it is easy solve very large dual problem instances. They also show that dual tractability extends to standard variations of the problem.
Speedup and Slowdown Behaviors in Queueing Systems
Servers in real queueing systems speed up in response to “load” and slowdown in response to “overwork,” when load has been high for an extended time period. In “Modeling Load and Overwork Effects in Queueing Systems with Adaptive Service Rates,” M. Delasay, A. Ingolfsson, and B. Kolfal extend the commonly used fixed-server-speed Erlang C model to a two-dimensional Markov chain that incorporates flexible dependence of service rates on load and overwork. The resulting model is a quasi-birth-and-death process for which the authors develop efficient algorithms to compute steady-state probabilities and system performance measures. The authors show that the model encompasses a wide-range of empirically observed behavior, and demonstrate how using models that ignore adaptive server behavior can result in inconsistencies between planned and realized performance and can lead to suboptimal, unstable, or oscillatory staffing decisions.
A Markovian Approach to Modeling Preferences
One of the fundamental challenging in revenue management problems is to model customer preferences among substitutable products. Customer preferences affect the substitution behavior, which in turn affects the demands of different products. Modeling preferences is especially challenging as we only observe the eventual selections made by the customers and not their underlying preference orders. In “A Markov Chain Approximation to Choice Modeling,” J. Blanchet, G. Gallego and V. Goyal consider a new paradigm for choice modeling where substitutions are modeled as transitions in a Markov chain over the set of products. They show that the model provides a simultaneous approximation for all random utility based choice models including multinomial logit model (MNL), nested logit and mixture of MNL models. They also show that the assortment optimization problem (where the goal is to select a subset of products to maximize the expected revenue) can be solved efficiently for the Markov chain choice model. Therefore, the Markov chain choice model provides a tractable approach to choice modeling and assortment optimization that is robust to model selection errors.
Optimizing Inventory and Shipment Decisions in Supply Chains
Efficient and sustainable management of supply chains require coordination of transportation planning and inventory control decisions. In “Exact Analysis of Divergent Inventory Systems with Time-Based Shipment Consolidation and Compound Poisson Demand,” O. Stenius, A.G. Karaarslan, J. Marklund, and A.G. de Kok analyze how this can be done in a one warehouse multi-retailer inventory system with a time-based shipment consolidation policy at the warehouse. A new approach, also applicable for many other system configurations, is used for determining exact expressions for the system’s inventory level distributions, fill rates, and expected shipment, holding and backorder costs. Furthermore, a method for joint optimization of the reorder levels and shipment intervals is presented. It is based on deriving optimality bounds for the decision variables, using analytical properties of the considered objective functions. The results apply to both single-item and multi-item systems.
Power Transmission Problems with Switching
It is well-known that optimizing network topology by switching on and off transmission lines improves the efficiency of power delivery in electrical networks. In fact, the Energy Policy Act of 2005 (Section 1223) states that the U.S. should “encourage, as appropriate, the deployment of advanced transmission technologies” including “optimized transmission line configurations.” In “A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching,” B. Kocuk, H. Jeon, S. Dey, J. Linderoth, J. Luedtke, and X. Sun study the Direct-Current version of the Optimal Transmission Switching Problem (DC-OTS). We formally establish that DC-OTS is NP-Hard, even if the network is a series-parallel graph with at most one load-demand pair. Inspired by Kirchoff’s Voltage Law, we give a cycle-based formulation for DC-OTS and use the new formulation to build a cycle-induced relaxation. We characterize the convex hull of this relaxation and provide strong valid inequalities that are used in a cutting-plane approach to solve DC-OTS. We give details of a practical algorithm and show promising computational results on standard benchmark instances.
Solving Probabilistic Problems with Nonlinear Random Technology Matrix
In “Solving Chance-Constrained Optimization Problems with Stochastic Quadratic Inequalities,” M. Lejeune, and F. Margot present a reformulation and algorithmic approach to solve a complex class of stochastic programming problems involving a joint chance constraint with random technology matrix and stochastic quadratic inequalities. The method is general enough to apply to non-convex as well as non-separable quadratic terms. We present a basic mixed-integer nonlinear reformulation based on Boolean modeling and detailed empirical results comparing the various reformulations and several easy-to-implement algorithmic ideas that improve performances of the mixed-integer nonlinear solver Couenne for solving these problems. Guidelines on how to tune the solver and selecting reformulations are presented. The test instances are epidemiology and disaster management facility location models.
Statistical Optimization in High Dimensions
Many decision problems in fields ranging from operations management to machine learning through financial engineering are obtained by solving optimization problems built on historical data. These data often have the following properties: they are noisy and high-dimensional where problem dimension can even exceed the number of samples; and have low intrinsic dimension—the parameters come from an underlying low dimensional subspace. In “Statistical Optimization in High Dimensions,” H. Xu, C. Caramanis, and S. Mannor propose and analyze three methods for such problems. The key observation is that by combining dimensionality reduction techniques from machine learning with optimization, it is possible to balance between solution quality and running time, taking advantage of low intrinsic dimensionality.
New Method Developed for Solving Multistage Problems with Discrete Decisions
A new method for solving multistage robust optimization problems with discrete recourse decisions is presented in “Multistage Robust Mixed Integer Optimization with Adaptive Partitions” by D. Bertsimas and I. Dunning, both from the MIT Operations Research Center. The method, based on the “finite adaptability” approximation to robust problems with recourse variables, partitions the “uncertainty set” of scenarios and assigns a different decision variable to each partition. The solution to the resulting mixed-integer optimization problem can be used to then define new partitions, and this process can be repeated to obtain tighter and tighter approximations. The authors provide a complementary bound on the ideal solution, enabling the quality of approximation to be established. They then demonstrate the method on classic operations research problems like inventory control and project selection, showing that the method quickly obtains high-quality solutions.
Structural Properties for Robust Maintenance Control with Learning
In “Robust Control of Partially Observable Failing Systems,” M. Kim examines a stochastically failing system whose underlying state is unobservable and can only be inferred using imperfect signals. At each stage, the decision maker acquires data and processes this information using Bayesian learning to obtain a posterior distribution over the underlying system state. The paper is concerned with situations in which the decision maker distrusts the nominal model and fears that it may be miss-specified. The focus of the analysis is on characterizing the structure of the optimal robust policy. In this regard, the primary contribution to the maintenance optimization literature is establishing new structural properties and insights for decision-making in the presence of model miss-specification. More generally, the findings in this paper make contributions to the robust dynamic optimization literature in which very few structural results characterizing the optimal robust policy have been published.
Consumption, Retirement, and Asset Allocation in an Incomplete Market
Starting from pioneering works by R. C. Merton, intertemporal models of optimal consumption and portfolio choice have evolved into some interesting generalizations. In “Unemployment Risks and Optimal Retirement in an Incomplete Market,” A. Bensoussan, B.-G. Jang, and S. Park present a life-cycle model that explicitly incorporates a precautionary savings motive induced by the presence of unhedgeable labor income risk that results in market incompleteness and stems from a forced unemployment event. A new convex-duality approach for reformulating the original retirement problem is introduced and an iterative numerical method is provided to solve it. The proposed life-cycle model gives an explanation for lower consumption and risky investment behaviors of individuals, and for relatively higher stock holdings of the poor. The model also explains a counter-cyclical pattern of the number of unemployed job leavers.
Incentive-Aware System Design
The effect of workload routing and staffing policies on employee performance has been mostly ignored in the queueing and network design literature. For example, if work is assigned to the fastest available employee, then (in the absence of volume-based payments) that employee has an incentive to slow down to avoid being overworked. Similarly, increasing staffing in response to high employee utilization provides an incentive for employees to stretch their service times to ensure they are always busy. In “Routing and Staffing when Servers are Strategic,” R. Gopalakrishnan, S. Doroudis, A. Ward, and A. Wierman study the impact on performance caused by the implicit incentives that workload routing and staffing policies create for employees (i.e., servers). We find that some policies common in the academic literature (such as fastest-server-first and square root safety staffing) may not perform as anticipated when employee incentives are taken into account.
