In This Issue
Pricing Electricity Under Uncertainty
In “A Stochastic Market Clearing Formulation with Consistent Pricing Properties,” V.M. Zavala, K. Kim, J. Birge, and M. Anitescu study the problem of pricing electricity under uncertainty. The authors argue that deterministic market clearing formulations introduce arbitrary distortions between day-ahead and expected real-time prices that bias economic incentives. They extend and analyze the stochastic clearing formulation proposed by Pritchard et al. (2010) in which the social surplus function induces penalties between day-ahead and real-time quantities. The penalty interpretation is used to prove that the formulation yields bounded price distortions, and it is shown that adding a similar penalty term to transmission flows and phase angles ensures boundedness throughout the network. The authors also prove that when the price distortions are zero, day-ahead quantities equal a quantile of their real-time counterparts (with a probability level dictated by incremental bid prices). The results suggest that stochastic settings provide significant benefits over deterministic counterparts that go beyond social surplus improvements.
Managing Competition Among Buyers to Increase Seller’s Revenues
The structure of competitive relationships among potential buyers has a profound impact on the revenues of the seller. In “Mechanism and Network Design with Private Negative Externalities,” A. Belloni, C. Deng, and S. Pekeč show that too much competition among rivals could harm monopolist’s revenues: a market in which buyer competition is fragmented yields higher revenues than a fully competitive market. By jointly optimizing over (admissible) networks and mechanisms, optimal competitive structures from the revenue-maximizing monopolist’s perspective are fully described (and turn out to be non-trivial). Thus, when designing the market, the revenue-maximizing monopolist should not just focus on the optimal mechanism, but also on designing, changing, or influencing competitive relationships among buyers. These results provide guidance for design of future markets, and for evaluating the value of potential investment in changing or influencing (even if only partially) the existing competitive relationships.
Flexible Optical Networks: A New Approach for a New Era
With the explosive growth of Internet usage, utilized bandwidth of the optical fibers rapidly approaches its theoretical limits. Just worsening the problem, the rigid nature of the current optical networks cannot efficiently use available optical bandwidth to support this increasing traffic. The energy consumption of telecommunications networks is also adversely affected by wasteful resource utilization. Flexible optical network (FON) architecture emerges as a promising solution for this urgent problem. The lack of efficient network management algorithms constitutes one of the biggest barriers for the realization of FON. In “Regenerator Location Problems in Flexible Optical Networks,” B. Yildiz and O.E. Karasan introduce this problem to OR audience and present a new perspective to the general path based formulations. Considering different network topologies and demand structures they present interesting problem complexity results that will be very useful in guiding the algorithm design efforts for the solution of this challenging problem.
Elimination by Aspects and its Relation to the Logit Family of Models
In “Relation between EBA and Nested Logit Models,” R. Kohli and K. Jedidi show that nested logit and cross-nested logit models are equivalent to preference trees, which are a special case of Elimination by Aspects (EBA). An extended EBA model, in which the utilities of alternatives are functions of covariates, represents a two-stage choice process. Alternatives are first screened using a probabilistic lexicographic rule and then compared in terms of their compensatory utilities. We provide a typology of the relations between EBA and other logit models, and discuss issues concerning estimation, statistical testing and data collection. An application illustrates the construction of a preference tree with covariates, and is used to contrast the implications from comparable preference trees and nested logit models.
Improving Health Outcomes through Operational Policies
Insufficient capacity to meet the demand for inpatient beds is a common problem in hospitals. The problem is pronounced when admitting patients to acute care wards that do not necessarily specialize on the patient’s condition is not an option. For example, the patients who present at the emergency department with a stroke episode require the care of a multi-disciplinary stroke team. Delays in access to such specialized care have negative impact on the health outcomes. Design of patient admission rules becomes more complex when multiple types of patients with different medical characteristics are present. In “Managing Patient Admissions in a Neurology Ward,” S. Samiedaluie, B. Kucukyazici, V. Verter, and D. Zhang, formulate this problem as an infinite-horizon average cost dynamic program and propose an efficient approximation scheme. This approach can be used to develop dynamic patient admission policies that are based on the state of the ward and can reduce overall deterioration in patients’ health status.
Kernel Smoothing for Portfolio Risk Measurement
Portfolio risk measurement under a setting where repricing of financial instruments requires simulation has received increasing attention amongst researchers and practitioners. In “Kernel smoothing for nested estimation with application to portfolio risk measurement,” L. J. Hong, S. Juneja, and G. Liu propose a kernel smoothing approach to portfolio risk measurement under this setting. It is shown that the rate of convergence of the kernel smoothing approach deteriorates as dimension increases, and thus a direct use of it is not appropriate as typical portfolios involve high-dimensional risk factors. However, by observing that portfolio loss is essentially a summation of losses resulting from individual instruments that often depend on very few risk factors, the authors propose to decompose a high-dimensional problem into low-dimensional ones. In conjunction with the decomposition technique, the kernel smoothing approach may work well for large portfolios involving hundreds of risk factors.
Collecting Uncertain Information in a Threat Environment
In “Controlling a fleet of UAVs to collect uncertain information in a threat environment,” Y. Xia, R. Batta, and R. Nagi employ a decentralized control strategy while requiring Unmanned Aerial Vehicles (UAVs) to maintain radio silence during the entire mission. The strategy is analyzed based on a scenario where a fleet of vehicles is assigned to search and collect uncertain information in a set of regions within a given mission time. The benefits of region-sharing are demonstrated even when there is no extra reward gained from additional information collection. Implementing a region-sharing strategy requires solving a decentralized time-allocation problem, which is computationally intractable. To overcome this, an approximate formulation is developed under an independence assumption for information collected by different vehicles. A sufficient condition is developed under which the approximate formulation becomes exact. A case study is presented to illustrate region-sharing behaviors among UAVs while using practical parameter values.
Selecting Award Scheme in an Innovation Tournament
How many prizes should be awarded in a tournament? This is a key question faced by any company pursuing crowdsourcing or innovation tournaments. In “Optimal Award Scheme in Innovation Tournaments,” L. Ales, S. Cho, and E Körpeoğlu show, surprisingly, that a winner-take-all award scheme (which awards one prize only to the best) is optimal in many practical situations, especially when agents have symmetric beliefs about uncertain outcomes of their efforts. Yet, the winner-take-all scheme is not always optimal, so the authors further identify situations when multiple prizes may be optimal: for example, when agents perceive it very likely that only few agents receive high evaluation or when a tournament does not require substantial increase in agents’ marginal cost of effort to develop high-quality solutions. Finally, a larger winner prize should be offered when seeking a higher number of good solutions, but not necessarily when anticipating more participants to a tournament.
LTL versus FTL Shipments in Distribution Systems
In “On Integral Policies in Deterministic and Stochastic Distribution Systems,” Y. Bo, M. Dawande, G. Janakiraman, and S. McCormick show that even when downstream demands in a distribution supply network are in full-truckloads (FTL), it can sometimes be significantly more profitable to use less-than-truckload (LTL) shipments within the network. For instance, this occurs in settings where shipping costs are expected to increase in the future. In such situations, their results highlight the importance of strategically positioning inventory: LTL shipments can offer a more balanced allocation of inventory across the distribution network, leading to benefits that can exceed the savings from FTL shipments due to economies of scale. However, when costs are expected to remain flat, then FTL shipments are ideal, that is, maximize profits.
Eliciting, Evaluating, and Aggregating Multiple Quantiles
The use of multiple quantiles to assess uncertainty is growing in practice. For instance, multiple quantiles are commonly used for assessing conditional value-at-risk and in forecasting competitions. In “Quantile Evaluation, Sensitivity to Bracketing, and Sharing Business Payoffs,” Y. Grushka-Cockayne, C. Lichtendahl, V.R. Jose, and R. Winkler use a general class of strictly proper scoring rules for multiple quantiles to evaluate such quantile elicitation. We propose a condition called sensitivity to bracketing that restricts the rule to a specific form. We introduce the notion of quantile bracketing and argue that the score of a group’s combined quantile forecast should be better than that of a randomly-selected forecaster only when forecasters’ quantiles do not all fall on the same side of the realization. Finally, we show how weights can be set to match the payoffs in many important business contexts. We believe that this paper offers important theoretical developments associated with proper scoring rules. This paper should be of interest to decision analysts, statisticians, and economists who use, evaluate, and aggregate probabilistic forecasts.
Designing Responsive and Cost-Effective Networks
How can logistics, telecommunications, and other network service providers meet customer requirements for speedy and reliable service when economies of scale favor consolidating traffic, possibly degrading performance? In the paper “Optimal Network Design with End-to-End Service Requirements,” A. Balakrishnan, G. Li and P. Mirchandani develop and solve an optimization model to address this problem. Their large-scale integer programming model, based on arc flows, incorporates the complex trade-offs involved in designing a cost-effective, but responsive, network that meets end-to-end service requirements. Using insights about the structure of this network design problem, the authors develop polyhedral results and methods to strengthen the model and accelerate the solution procedure. Complemented with optimization-based heuristics, the authors’ composite solution method significantly outperforms standard solvers for an extensive set of problem instances. The theoretical results and methods developed in this paper provide a valuable foundation for practical tools to design contemporary service networks.
Ambiguous Joint Chance Constraints under Mean and Dispersion Information
A wide variety of decision problems in engineering, science and economics are impacted by exogenous random quantities that are governed by a probability distribution which is itself only partially known. Such problems give rise to ambiguous chance constrained programs that aim to determine the best decision in view of the most adverse or most favorable distribution that is compatible with the available a priori information. In “Ambiguous Joint Chance Constraints under Mean and Dispersion Information,” G. A. Hanasusanto, V. Roitch, D. Kuhn, and W. Wiesemann study ambiguous chance constrained programs where the unknown true probability distribution is characterized by the mean and the support of the random quantities, as well as by an upper bound on their dispersion. The authors present a minimal set of conditions under which such problems give rise to tractable conic reformulations, and they demonstrate that the obtained reformulations allow them to solve large-scale project management and image reconstruction models to global optimality.
An Effective New Approach for Solving Integer Bilevel Optimization Problems
Bilevel programming has multiple applications in areas such as traffic systems, natural gas market regulation, waste management, and chemical engineering. However, mixed-integer bilevel programs are notoriously difficult to solve because the leader’s feasible region is defined in part by optimality conditions governing an embedded follower subproblem. In this setting, optimality conditions are difficult to characterize because of the nonconvexity of the subproblem. In “A Value-Function-Based Exact Approach for the Bilevel Mixed-Integer Programming Problem,” L. Lozano and J. C. Smith propose an exact finite algorithm for a class of these problems based on an adaptive sampling scheme. The authors demonstrate how this algorithm can be tailored to accommodate either optimistic or pessimistic assumptions on the follower’s behavior. Computational experiments show that the proposed approach outperforms an existing state-of-the-art algorithm, and that the approach is capable of solving instances of a competitive scheduling problem involving nonlinear objectives.
Minimizing the Expected Opportunity Cost in Ranking and Selection
The expected opportunity cost (EOC) is an important measure to assess the quality of selection for the best design in ranking and selection problems. It penalizes a particularly bad choice more than a good but non-optimal selection, and thus is preferred by risk-neutral practitioners and decision makers. In “A New Budget Allocation Framework for the Expected Opportunity Cost,” S. Gao, W. Chen, and L. Shi develop an optimal procedure for ranking and selection problems with general underlying distributions based on this quality measure. The high efficiency of the proposed procedure is illustrated via various numerical experiments. The authors also compare the EOC with the traditional probability of correct selection (PCS) measure by showing the asymptotic equivalence of the EOC and PCS-based selection problems and analyzing their different behaviors under a limited computing budget.
Strategic Inspection of a Queue
Some customers join a queue without first inspecting it, others find it worthwhile to make an effort and find out the queue length before deciding whether or not to join it. As many others inspect the queue, the probability of extremely long queues decreases and the incentive of an individual to make the necessary effort associated with inspection decreases too. In “The Impact of Inspection Cost on Equilibrium, Revenue and Social Welfare in a Single Server Queue,” R. Hassin and R. Roet-Green analyses the outcome of interdependence of customer strategies and draws relevant managerial conclusion.
Large-Scale Parallel Ranking and Selection
In “Efficient Ranking and Selection in Parallel Computing Environments,” E. Ni, D. F. Ciocan, S. Henderson, and S. Hunter develop a parallel ranking and selection algorithm that (1) provides a strong statistical guarantee on the quality of the returned solution and (2) has been used to solve a problem containing over one million systems. Ranking and selection algorithms can be used to solve simulation-optimization problems in which it is feasible to simulate all solutions, or systems, to some extent. Historically, these algorithms have been practical only for small problem instances. This paper discusses the general design principles required to make ranking and selection algorithms work efficiently in a parallel computing environment, and demonstrates the potential scale and broad applicability of this approach by implementing versions of the algorithm on a high-performance computing environment, and in the cloud, using message-passing interface, MapReduce, and Spark.
