Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2012. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 155-156). / The U.S. military considers Unmanned Underwater Vehicles (UUVs) a critical component of the future for two primary reasons - they are effective force multipliers and a significant risk-reducing agent. As the military's technology improves and UUVs become a reliable mission asset, the vehicle's ability to make intelligent decisions will be crucial to future operations. The thesis develops various algorithms to solve the UUV Mission-Planning Problem (UUVMPP), where the UUV must choose which tasks to perform in which sequence in a stochastic mission environment. The objective is to find the most profitable way to execute tasks with restrictions of total mission time, energy, time-restricted areas, and weather conditions. Since the UUV accumulates navigation error over time while maneuvering underwater, the UUV must occasionally halt operations to re-orient itself via a navigation fix. While a navigation fix takes time and increases the likelihood of exposing the vehicle's position to potential adversaries, a reduction in navigation error allows the UUV to perform tasks and navigate with a greater amount of certainty. The algorithms presented in this thesis successfully incorporate navigation fixes into the mission-planning process. The thesis considers Mixed-Integer Programming, Exact Dynamic Programming, and an Approximate Dynamic Programming technique known as Rollout to determine the optimal a priori route that meets operational constraints with a specified probability. The thesis then shows how these formulations can solve and re-solve the UUVMPP on-line. In particular, the Rollout Algorithm finds task route solutions on average 96% of the optimal solution a priori and 98% of the optimal solution on-line compared to exact algorithms; with a significant reduction in computation run time, the Rollout Algorithm permits the solving of increasingly complex mission scenarios. / by Brian A. Crimmel. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2008. / Includes bibliographical references (p. 79-80). / This thesis describes the design and implementation of an optimization model to manage inventory at Dell's American factories. Specifically, the model is a mixed integer program which makes routing decisions on incoming monitors (a bulky item which incurs great shipping costs) from Asia to Dell's factories in America as well as inventory transfer decisions from factory to factory. The optimization model approaches the inventory allocation problem by minimizing inventory routing costs plus shortage costs across all sites subject to constraints which define the specifics of Dell's supply chain. Shortage costs are assessed using a per part per day back order penalty, however a more precise assessment of shortage costs using actual costs from a combined MIT/Dell study is also presented. The software implementation of the optimization model has been field tested and validated and is now being adopted on a global level for use in balancing supply to all of Dell's factories worldwide. The software design as well as the implementation results are discussed within this thesis. Also, an adaptation of the model to a global scale is presented. This extension of the model, which assumes a "global warehouse" upstream in the supply chain, allocates inventory from the China to regional facilities throughout the world subject to supply chain constraints and the understanding that regional teams will tend to balance out their own region's inventory using intraregional balancing decisions. / by John William Foreman. / S.M.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2014. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 73-74). / In the face of large increases in the number of passengers and flights, busy airports worldwide have been trying to optimize operating efficiency and throughput and minimize congestion on a daily basis. In the case of departures, measures can be taken at the gate, on the taxiway system or at the runway queue to minimize departure delays and/or the cost of unavoidable delays. This cost includes needless fuel consumption and noxious emissions. In this thesis, we focus primarily on runway queue optimization. The first part of this work consists of designing a generic simulation which models specific days of operations at an airport. Using as input the schedule of operations specific to the modeled airport, the simulation processes all departures and stores the characteristic times of the process for each departing aircraft. The quantities of interest are either incrementally computed by the simulation or modeled using probability distributions derived from airport-specific data. We then present a dynamic programming approach to sequencing departing aircraft at the runway queue. Two algorithms are presented based on the idea of Constrained Position Shifting, which maintains a high level of fairness in the order in which aircraft gain access to runways, while also improving efficiency by comparison to First Come First Served sequencing. The objective of the first algorithm is to minimize makespan, and that of the second to minimize delays. We then focus on a specific airport, which has been experiencing one of the fastest growth rates in the industry. We analyze the output of our simulation as applied to this airport and accumulate insights about congestion at the departure runways. We next apply this sequencing algorithm to this specific airport using multiple demand profiles that represent both the current traffic levels, as well as anticipated future ones that would result in more congestion. We give quantitative arguments to confirm the positive impact of the optimization on the airport's operations. We also emphasize the importance of the aircraft mix on the techniques' performance and show that the sequencing algorithms provide higher benefits (in terms of reducing delays) as the mix becomes more heterogeneous. / by Alexandre Paul Sahyoun. / S.M.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2018. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 175-182). / Container terminals, where containers are transferred between different modes of transportation both on the seaside and landside, are crucial links in intercontinental supply chains. The rapid growth of container shipping and the increasing competitive pressure to lower rates result in demand for higher productivity. In this thesis, we design new models and methods for the combinatorial optimization problems representing storage yard operations in maritime container terminals. The goal is to increase the efficiency of yard cranes by decreasing unproductive container moves (also called relocations). We consider three problems with applicability to real-time operations. First, we study the container relocation problem that involves finding a sequence of container moves that minimizes the number of relocations needed to retrieve all containers, while respecting a given order of retrieval. We propose a new binary integer program model, perform an asymptotic average case analysis, and show that our methods can apply to other storage systems where stacking occurs. Second, we relax the assumption that the full retrieval order of containers is known in advance and study the stochastic container relocation problem. We introduce a new model, compare it with an existing one, and develop two new algorithms for both models based on decision trees and new heuristics. We show that techniques in this chapter apply more generally to finite horizon stochastic optimization problems with bounded cost functions. Third, we consider the integrated container relocation problem and yard crane scheduling problem to find an optimal sequence of scheduled crane moves that perform the required container movements. Taking into account practical constraints, we present a new model, propose a binary integer program using a network flow-type formulation, and design an efficient heuristic procedure for real-time operations based on properties of our mathematical formulation. We relate this problem to pick-up and delivery problems with a single vehicle and capacities at every node. In all three chapters, the efficiency of all our algorithms are shown through extensive computational experiments on available problem instances from the literature and/or on real data. / by Virgile Galle. / Ph. D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2007. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Includes bibliographical references (p. 175-182). / In the context of patient care for life-threatening illnesses, the presence of uncertainty may compromise the quality of a treatment. In this thesis, we investigate robust approaches to managing uncertainty in radiation therapy treatments for cancer. In the first part of the thesis, we study the effect of breathing motion uncertainty on intensity-modulated radiation therapy treatments of a lung tumor. We construct a robust framework that generalizes current mathematical programming formulations that account for motion. This framework gives insight into the trade-off between sparing the healthy tissues and ensuring that the tumor receives sufficient dose. With this trade-off in mind, we show that our robust solution outperforms a nominal (no uncertainty) solution and a margin (worst-case) solution on a clinical case. Next, we perform an in-depth study into the structure of different intensity maps that were witnessed in the first part of the thesis. We consider parameterized intensity maps and investigate their ability to deliver a sufficient dose to the tumor in the presence of motion that follows a Gaussian distribution. We characterize the structure of optimal intensity maps in terms of certain conditions on the problem parameters. / (cont.) Finally, in the last part of the thesis, we study intensity-modulated proton therapy under uncertainty in the location of maximum dose deposited by the beamlets of radiation. We provide a robust formulation for the optimization of proton-based treatments and show that it outperforms traditional formulations in the face of uncertainty. In our computational experiments, we see evidence that optimal robust solutions use the physical characteristics of the proton beam to create dose distributions that are far less sensitive to the underlying uncertainty. / by Timothy Ching-Yee Chan. / Ph.D.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2001. / Includes bibliographical references (leaves 141-146). / Can airline Yield Management strategies be used to generate additional revenue from spare capacity in telecom networks? Pundits believe "yes", based on several analogies between the industries such as, for instance, perishable inventory and negligible marginal cost of usage. However, no one has yet described how, one of the chief difficulties being the vastly different nature of airlines products and telecom services. Motivated to show how Operations Research can play a role in structuring this area, we: (i) argue that telecom Yield Management should be based on 'innovative' services explicitly designed to use only spare capacity, (ii) propose, borrowing from airlines, a framework to simplify related decision modeling, and (iii) demonstrate both our argument and the framework by articulating several 'innovative' telecom services and modeling them to varying degrees of depth. This thesis focuses only on the decision-making that will be required within a large infrastructure for operating new 'Yield Management' services. For each service, several decision variables can be considered to maximize revenue from available capacity, e.g. pricing, capacity limits and admission control, among others. Incorporating all such decisions in a single model usually leads to complicated formulations. A framework that decouples the decisions from each other to obtain simpler, more insightful models is therefore immensely helpful. We propose using the airlines modeling framework to separate the decisions involved in the operation of each new service. This framework classifies models into forecasting, over-booking, seat-inventory control, pricing and market segmentation to reduce the complexity of the system-wide problem. To make this framework useful for telecom, we provide a detailed interpretation of each category in the telecom context. . Finally, the majority of this thesis is the six service ideas that illustrate our argument and the models that demonstrate how the framework might be used. For each service we propose, we discuss possible markets and practical issues. We then formulate a model for one of the decisions resulting from the framework. These models are analyzed to varying depths to demonstrate the operating rules one can discover for revenue maximization. The contributions of this work are at multiple levels. In addition to our argument and examples of services proposed for telecom Yield Management, it structures the modeling questions in a coherent manner, exploiting more than only the high-level connections between airlines and telecom. Finally, the models themselves are useful and their contributions are at the analytical level. This thesis makes clear several connections between airline and telecom Yield Management that people have found difficult to establish in the past. / by Salal Humair. / Ph.D.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2014. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / 36 / "June 2014." Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 95-97). / In this thesis, we develop methods to address airlift scheduling, and in particular the problem of scheduling military aircraft capacity to meet ad hoc demand. Network optimization methods typically applied to scheduling problems do not sufficiently capture all necessary characteristics of this problem. Thus, we develop a new method that uses integer linear programming (IP) with column generation to make the problem more tractable while incorporating the relevant characteristics. In our method, we decompose the problem into two steps: generating feasible aircraft routes, and solving the optimization model. By ensuring that routes are feasible with respect to travel time, ground time, crew rest, and requirement restrictions when we build them, we do not need to encode these characteristics within the IP optimization model, thus reducing the number of constraints. Further, we reduce the number of decision variables by generating only the fraction of feasible aircraft routes needed to find near-optimal solutions. We propose two methods for generating routes to include in the IP model: explicit column generation and selective column generation. In explicit column generation, all aircraft routes that we could potentially consider including in the model are generated first. Starting with a subset of these routes, we iteratively use reduced cost information obtained by solving a relaxed version of the IP model to choose more routes to add from the original set of routes. In selective column generation, we first generate a small set of feasible aircraft routes. Starting with this set of routes, we iteratively generate more routes by solving a relaxed version of the IP model and then combine routes in the solution together and add those that are feasible to the route set. In both methods, we iterate until there are either no other routes to include or the solution stops improving. Last, we solve the IP model with the final set of routes to obtain an integer solution. We test the two approaches by varying the number of locations in the network, the number of locations that are wings, and the number of requirements. We show that selective column generation produces a solution with an objective value similar to that of explicit column generation in a fraction of the time. In our experiments, we solve problems with up to 100 requirements using selective column generation. In addition, we test the impact of integrating lines of business while scheduling airlift and show a significant improvement over the current process. / by Mark J. Williams. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2004. / Includes bibliographical references (p. 117-121). / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Stem (cell research is one of the most promising and cutting-edge fields i the miedical sciences. It is believed that this innovative research will lead to life-saving treatments in the coming years. As part of their work, stem cell researchers must first determine which of their stem cell colonies are of sufficiently high quality to be suitable for experimental studies and therapeutic treatments. Since colony texture is a major discriminating feature in determining quality. we introduce a non-invasive, semi-automated texture-based stem cell colony classification methodology to aid researchers in colony quality control. We first consider the general problem of textural image segmentation. In a new approach to this problem. we characterize image texture by the subband energies of the image's wavelet decomposition, and we employ a non-parametric support vector machine to perform the classification that yields the segmentation. We also adapt a parametric wavelet-based classifier that utilizes the Kullback-Leibler distance. We apply both methods to a set of benchmark textural images, report low segmentation error rates and comment on the applicability of and tradeoffs between the non-parametric and parametric segmentation methods. / (cont.) We then apply the two classifiers to the segmentation of stem cell colony images into regions of varying quality. This provides stem cell researchers with a rich set of descriptive graphical representations of their colonies to aid in quality control. From these graphical representatiolns, we extract colony-wise textural features to which we add colony-wise border features. Taken together, these features characterize overall colony quality. Using these features as inputs to a multiclass support vector machine, we successfully categorize full stem cell colonies into several quality categories. This methodology provides stem cell researchers with a novel, non-invasive quantitative quality control tool. / by Christopher G. Jeffreys. / S.M.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2017. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 137-143). / In this thesis, we study mixed-integer convex optimization, or mixed-integer convex programming (MICP), the class of optimization problems where one seeks to minimize a convex objective function subject to convex constraints and integrality restrictions on a subset of the variables. We focus on two broad and complementary questions on MICP. The first question we address is, "what are efficient methods for solving MICP problems?" The methodology we develop is based on outer approximation, which allows us, for example, to reduce MICP to a sequence of mixed-integer linear programming (MILP) problems. By viewing MICP from the conic perspective of modern convex optimization as defined by Ben-Tal and Nemirovski, we obtain significant computational advances over the state of the art, e.g., by automating extended formulations by using disciplined convex programming. We develop the first finite-time outer approximation methods for problems in general mixed-integer conic form (which includes mixed-integer second-order-cone programming and mixed-integer semidefinite programming) and implement them in an open-source solver, Pajarito, obtaining competitive performance with the state of the art. The second question we address is, "which nonconvex constraints can be modeled with MICP?" This question is important for understanding both the modeling power gained in generalizing from MILP to MICP and the potential applicability of MICP to nonconvex optimization problems that may not be naturally represented with integer variables. Among our contributions, we completely characterize the case where the number of integer assignments is bounded (e.g., mixed-binary), and to address the more general case we develop the concept of "rationally unbounded" convex sets. We show that under this natural restriction, the projections of MICP feasible sets are well behaved and can be completely characterized in some settings. / by Miles Lubin. / Ph. D.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2015. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 147-153). / Online markets are becoming increasingly important in today's world as more people gain access to the internet. Furthermore, the explosion of data that is collected via these online markets provides us with new opportunities to use analytics techniques to design markets and optimize tactical decisions. In this thesis, we focus on two types of online markets -- peer-to-peer networks and online retail markets -- to show how using analytics can make a valuable impact. We first study scrip systems which provide a non-monetary trade economy for exchange of resources; their most common application is in governing online peer-to-peer networks. We model a scrip system as a stochastic game and study system design issues on selection rules to match trade partners over time. We show the optimality of one particular rule in terms of maximizing social welfare for a given scrip system that guarantees players' incentives to participate, and we investigate the optimal number of scrips to issue under this rule. In the second part, we partner with Rue La La, an online retailer in the online flash sales industry where they offer extremely limited-time discounts on designer apparel and accessories. One of Rue La La's main challenges is pricing and predicting demand for products that it has never sold before. To tackle this challenge, we use machine learning techniques to predict demand of new products and develop an algorithm to efficiently solve the subsequent multi-product price optimization. We then create and implement this algorithm into a pricing decision support tool for Rue La La's daily use. We conduct a controlled field experiment which estimates an increase in revenue of the test group by approximately 10%. Finally, we extend our work with Rue La La to address a more dynamic setting where a retailer may choose to change the price of a product throughout the course of the selling season. We have developed an algorithm that extends the well-known multi-armed bandit algorithm called Thompson Sampling to consider a retailer's limited inventory constraints. Our algorithm has promising numerical performance results when compared to other algorithms developed for the same setting. / by Kris Johnson. / Ph. D.