MSOM Society Student Paper Competition: Abstracts of 2014 Winners

Optimization in Online Content Recommendation Services: Beyond Click-Through Rates

Yonatan Gur

Stanford University, [email protected]

Advisors: Omar Besbes, Columbia University; Assaf Zeevi, Columbia University

A new class of online services allows Internet media sites to direct users from articles they are currently reading to other content they may be interested in. This process creates a “browsing path” along which there is potential for repeated interaction between the user and the provider, giving rise to a dynamic optimization problem. A key metric that often underlies this recommendation process is the click-through rate (CTR) of candidate articles. While CTR is a measure of instantaneous click likelihood, we analyze the performance improvement that one may achieve by some lookahead that accounts for the potential future path of users. To that end, using a large data set of user path history at major media sites, we introduce and derive a representation of content along two key dimensions: clickability, the likelihood to click to an article when it is recommended; and engageability, the likelihood to click from an article when it hosts a recommendation. We then propose a class of heuristics that leverage both clickability and engageability, and provide theoretical support for favoring such path-focused heuristics over myopic heuristics that focus only on clickability (no lookahead). We conduct a live pilot experiment that measures the performance of a practical proxy of our proposed class, when integrated into the operating system of a worldwide leading provider of content recommendations. We estimate the aggregate improvement in clicks-per-visit relative to the CTR-driven current practice. The documented improvement highlights the importance and the practicality of efficiently incorporating for the future path of users in real time.

Improving HIV Early Infant Diagnosis Supply Chains in Sub-Saharan Africa: Models and Application to Mozambique

Jónas Oddur Jónasson

London Business School, [email protected]

Advisors: Jérémie Gallien, London Business School; Sarang Deo, Indian School of Business

Early diagnosis of HIV among infants born to HIV-infected mothers is critical because roughly 50% of untreated infected infants die before the age of two years. Yet most countries in sub-Saharan Africa experience significant delays in diagnosis due to operational inefficiencies in early infant diagnosis (EID) networks. We develop a two-part modeling framework relying on optimization and simulation to generate operational improvements in the assignment of clinics to laboratories and the allocation of capacity across laboratories, and evaluate the associated impact on the number of infants initiating treatment. Applying our methodology to EID program data from Mozambique, we validate our simulation model and estimate that optimally re-assigning clinics to labs would decrease the average sample turnaround time (TAT) by 11% and increase the number of infected infants starting treatment by about 4% relative to the current system. Further, consolidating all diagnostic capacity in one centralized lab would decrease average TATs by an estimated 22% and increase the number of infected infants initiating treatment by 7%. Our sensitivity analysis suggests that the consolidation of capacity in a single location would remain near-optimal across a wide range of laboratory utilization levels in Mozambique. However, this full consolidation solution is dominated by configurations with two or more labs for EID networks with average transportation times larger than those currently observed in Mozambique by at least 15%.

Sparse Process Flexibility Designs: Is Long Chain Really Optimal?

Antoine Désir

Columbia University, [email protected]

Advisor: Vineet Goyal, Columbia University

Sparse process flexibility and long chain has become an important concept in design flexible manufacturing systems since the seminal paper of Jordan and Graves (1995). In this paper, we study the performance of long chain in comparison to all designs with at most 2n edges over n supply and n demand nodes. We show that, surprisingly, long chain is not optimal in this class of networks even for i.i.d. demand distributions. In particular, we present a family of instances where a disconnected network with 2n edges has a strictly better performance than long chain even for i.i.d. demand distributions. This is quite surprising and contrary to the intuition that a connected design performs better than a disconnected one for symmetric distributions. Moreover, our family of instances shows that the optimal design depends on the particular demand distribution. We also study the performance of long chain in comparison to connected designs with at most 2n arcs. We show that long chain is optimal in this class of designs for exchangeable demand distributions. Our proof is based on a coupling argument and a combinatorial analysis of the structure of maximum flow in directed networks. The analysis provides useful insights towards not just understanding the optimality of long chain but also towards designing more general sparse flexibility networks.

Municipal Groundwater Management: Optimal Allocation and Control of a Renewable Natural Resource

Karthik Murali

University of Illinois at Urbana–Champaign, [email protected]

Advisors: Michael Lim, University of Illinois at Urbana–Champaign; Nicholas Petruzzi, University of Illinois at Urbana–Champaign

The growing scarcity of water has led to a changing water management paradigm, two ingredients of which, are market-like institutions for the reallocation of water, and the privatization of water management. We formulate a deterministic optimal control model to study a community’s problem of managing its renewable and exhaustible groundwater resource to determine optimal allocation and control policies in the presence of market-based water transfer opportunities. We establish and characterize threshold polices governing export or import decisions of the community. Next, we study the implications of privatizing groundwater management in the presence of the aforementioned water transfer opportunities. Throughout this study, we adopt a Triple Bottom Line (3BL) perspective while analyzing the consequences of water transfers and privatization. To this end, we develop metrics of social and environmental consequences in the context of groundwater management. We find that despite the economic benefits, water transfers may prove detrimental from a social and environmental perspective. In particular, we find that the most commonly observed instances of trade between two communities with very different groundwater characteristics can result in the most detrimental social and environmental outcomes. We also identify conditions under which privatizing groundwater management can lead to beneficial consequences from a 3BL perspective.

Scheduling with Testing

Yaron Shaposhnik

Massachusetts Institute of Technology, [email protected]

Advisors: Retsef Levi, Massachusetts Institute of Technology; Thomas Magnanti, Massachusetts Institute of Technology and Singapore University of Technology and Design

We study a new class of scheduling problems that captures common settings in service environments, in which one has to serve a collection of “jobs” that have a priori uncertain attributes, such as their exact processing time and their priority. In many of these settings the service provider has to decide whether to invest resources (people, equipment, time, etc.) to “test” (diagnose) a job and learn more about its respective uncertain attributes, or instead simply use the resources to process the job. The former could inform future decisions, but could delay the service time for other jobs, while the latter directly advances the processing of the jobs. Our approach and analysis provide operational insights about the optimal policy, the value of testing, as well as the effectiveness of several natural heuristics. We believe that our approach will lead to further research to explore this important practical tradeoff.

Optimality Gap of Constant-Order Policies Decays Exponentially in the Lead Time for Lost Sales Models

Linwei Xin

Georgia Institute of Technology, [email protected]

Advisor: David A. Goldberg, Georgia Institute of Technology

Inventory models with lost sales and large lead times have traditionally been considered intractable, due to the curse of dimensionality which arises from having to track the set of orders placed but not yet received (i.e., pipeline vector). Recently, Goldberg et al. (2012) laid the foundations for a new approach to solving these models, by proving that as the lead time grows large (with the other problem parameters fixed), a simple constant-order policy (proposed earlier by Reiman (2004)) is asymptotically optimal. This was quite surprising, as it is exactly this setting (i.e., large lead times) that was previously believed intractable. However, the bounds proven there are impractical, requiring the lead time to be very large before the constant-order policy becomes nearly optimal, e.g., requiring a lead time which is Ω(𝜖⁻²) to ensure a (1 + 𝜖)-approximation guarantee, and involving a massive prefactor. The authors note that numerical experiments of Zipkin (2008) suggest that the constant-order policy performs quite well even for small lead times, and pose closing this gap (thus making the results practical) as an open problem. In this work, we make significant progress towards resolving this open problem and closing this gap. In particular, for the infinite-horizon variant of the finite-horizon problem considered by Goldberg et al. (2012), we prove that the optimality gap of the same constant-order policy actually converges exponentially fast to zero; i.e. we prove that a lead time which is O(log(𝜖⁻¹)) suffices to ensure a (1 + 𝜖)-approximation guarantee. We also derive simple and explicit bounds for the optimality gap, which make the result and methodology practical for realistic lead time values.