Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2007. / Includes bibliographical references (p. 129-134). / With recent advances in research and technology, autonomous surface vessel capabilities have steadily increased. These autonomous surface vessel technologies enable missions and tasks to be performed without the direction of human operators, and have changed the way scientists and engineers approach problems. Because these robotic devices can work without manned guidance, they can execute missions that are too difficult, dangerous, expensive, or tedious for human operators to attempt. The United States government is currently expanding the use of autonomous surface vessel technologies through the United States Navy's Spartan Scout unmanned surface vessel (USV) and NASA's Ocean-Atmosphere Sensor Integration System (OASIS) USV. These USVs are well-suited to complete monotonous, dangerous, and time-consuming missions. The USVs provide better performance, lower cost, and reduced risk to human life than manned systems. In this thesis, we explore how to plan multiple USV observation schedules for two significant notional observation scenarios, collecting water temperatures ahead of the path of a hurricane, and collecting fluorometer readings to observe and track a harmful algal bloom. / (cont.) A control system must be in place that coordinates a fleet of USVs to targets in an efficient manner. We develop three algorithms to solve the unmanned surface vehicle observation-planning problem. A greedy construction heuristic runs fastest, but produces suboptimal plans; a 3-phase algorithm which combines a greedy construction heuristic with an improvement phase and an insertion phase, requires more execution time, but generates significantly better plans; an optimal mixed integer programming algorithm produces optimal plans, but can only solve small problem instances. / by John V. Miller. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2007. / Includes bibliographical references (p. 227-229). / By combining the strengths of human and computers, Human Machine Collaborative Decision Making has been shown to generate higher quality solutions in less time than conventional computerized methods. In many cases, it is difficult to model continually changing problems and incorporate human objectives into the solution. Human-guided algorithms (HGAs) harness the power of sophisticated algorithms and computers to provide flexibility to the human decision maker to model correctly and dynamically the problem and steer the algorithm to solutions that match his/her objectives for the given problem. HGAs are designed to make the power of Operations Research accessible to problem domain experts and decision makers, and incorporate their expert knowledge into every solution. In order to appropriately utilize algorithms during a planner's decision making, HGA operators must appropriately trust the HGA and the final solution. Through the use of trust-based design (TBD), it was hypothesized that users of the HGA will gain better insight into the solution process, improve their calibration of trust, and generate superior solutions. The application of TBD requires the consideration of algorithms, solution steering methods, and displays required to best match human and computer complimentary strengths and to generate solutions that can be appropriately trusted. / (cont.) Abstract hierarchy, Ecological Interface Design, and various trust models are used to ensure that the HGA operators' evaluation of trust can be correctly calibrated to all necessary HGA trust attributes. A human-subject evaluation was used to test the effectiveness of the TBD design approach for HGAs. An HGA, including the appropriate controls and displays, was designed and developed using the described TBD approach. The participants were presented with the task of using the HGA to develop a routing plan for military aircraft to prosecute enemy targets. The results showed that TBD had a significant effect on trust, HGA performance, and in some cases the quality of final solutions. Another finding was that, HGA operators must be provided with additional trust related information to improve their understanding of the HGA, the solution process, and the final solution in order to calibrate properly their trust in the system. / by Joseph L. Thomer. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2007. / Includes bibliographical references (p. 137-138). / More than four years after the end of major combat operations in the 2003 Iraq War, the United States military continues to sustain casualties at rates higher than those during the ground campaign. Combat service support soldiers conducting daily convoy operations on the Iraqi road network account for a large number of these casualties. One reason for this is the threat's affinity to targeting soft, vulnerable, high-payoff targets through the use of roadside bombs, otherwise known as improvised explosive devices. This enemy tactic is characteristic of asymmetric warfare, in which a lesser opponent opposes a force far superior in numbers, equipment, and technology. In an asymmetric operating environment, threats blend in with the local populace making them hard to detect and are easily capable of multi-directional attacks; absent are the linear battlefields of past wars where logistical soldiers operated in the relative safety of the rear battlefield. This thesis explores a mathematical approach to decide how to use available resources to best protect logistical convoys. To achieve this we first model the threat using probabilistic models and identify input data requirements associated with the operating environment and other relevant factors. / (cont.) Second, we identify a set of force protection resources and model their counter-effects on the threat. Next, we develop a binary integer program to optimally allocate the force protection resources to a set of planned logistical convoys. Our model uses an algorithm that assigns resources to either fixed areas or individual convoys in a way that minimizes overall threat effects to the convoys. The algorithm provides lower-risk plans yielding a lower expected number of casualties. We propose integrating this force protection algorithm in conjunction with convoy planning software that optimally builds and routes convoys based on minimizing exposure to the threat to achieve even better plans. We test the performance of a system that accomplishes this by comparing its resulting plans to human-generated plans in a controlled experiment. Additionally, we conduct Monte Carlo simulations to statistically analyze the system's performance. We find that the system produces lower-risk plans in less time than human planners. We describe future development of this methodology to reducing soldier casualties, and a proposed approach for its integration into existing Army systems and processes. / by Keith W. DeGregory. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2008. / Includes bibliographical references (p. 179-180). / In this thesis, we investigate the batch sizing problem for a custom-job production facility. More specifically, given a production system that has been assigned several different types of custom jobs, we try to derive batching policies to minimize the expected total time that a job spends in the system. Custom-job production brings a host of challenges that makes batch sizing very difficult - production can only begin when the order arrives, the yield uncertainty probabilities are fairly large, and the production quantities are typically small. Furthermore, deriving an optimal batch sizing policy is difficult due to the heterogeneity of the job types; each job type has a different demand, batch setup time, unit production rate, unit defective probability, and job arrival rate. In addition, further complexity stems from the fact that the batch sizing decisions for each job type are coupled, and cannot be made independently. Given the difficulties in selecting the batch sizes, we propose an alternative batching method that minimizes the system utilization instead of the expected total job time. The main advantage of this approach is that is allows us to choose the batch size of each job type individually. First, we model the system as an M/G/l queue, and obtain a closed-form expression for the expected total job time when the demand is restricted to be a single unit. Following which, we show empirically that the minimum utilization heuristic attains near-optimal performance under the unit demand restriction. We then build on this analysis, and extend the heuristic to the general case in which the demand of each job is allowed to be more than a single unit. Finally, we use simulations to compare our heuristic against other alternative batching policies, and the results indicate that our heuristic is indeed an effective strategy. / by Christopher Siow. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2008. / 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. 143-146). / In this thesis, we develop a pricing strategy that enables a firm to learn the behavior of its customers as well as optimize its profit in a monopolistic setting. The single product case as well as the multi product case are considered under different parametric forms of demand, whose parameters are unknown to the manager. For the linear demand case in the single product setting, our main contribution is an algorithm that guarantees almost sure convergence of the estimated demand parameters to the true parameters. Moreover, the pricing strategy is also asymptotically optimal. Simulations are run to study the sensitivity to different parameters.Using our results on the single product case, we extend the approach to the multi product case with linear demand. The pricing strategy we introduce is easy to implement and guarantees not only learning of the demand parameters but also maximization of the profit. Finally, other parametric forms of the demand are considered. A heuristic that can be used for many parametric forms of the demand is introduced, and is shown to have good performance in practice. / by Thibault Le Guen. / S.M.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, February, 2021 / Cataloged from the official PDF of thesis. / Includes bibliographical references (pages 179-189). / In the last decade, there has been a surge in online platforms for providing a wide variety of services. These platforms face an array of challenges that can be mitigated with appropriate modeling and the use of optimization tools. In this thesis, we examine, model, and provide solutions to some of the key challenges. First, we focus on the problem of intelligent SMS routing faced by several online platforms today. In a dynamically changing environment, platforms need to carefully choose SMS aggregators to have a high number of text messages being delivered to users at a low cost. To model this problem, we consider a novel variant of the multi-armed bandit (MAB) problem, MAB with cost subsidy, which models many real-life applications where the learning agent has to pay to select an arm and is concerned about optimizing cumulative costs and rewards. / We show that naive generalizations of existing MAB algorithms like Upper Confidence Bound and Thompson Sampling do not perform well for the SMS routing problem. For an instance with K arms and time horizon T, we then establish a fundamental lower bound of [omega](K¹/³T²/³) on the performance of any online learning algorithm for this problem, highlighting the hardness of our problem in comparison to the classical MAB problem. We also present a simple variant of explore-then-commit and establish near-optimal regret bounds for this algorithm. Lastly, we perform numerical simulations to understand the behavior of a suite of algorithms for various instances and recommend a practical guide to employ different algorithms. Second, we focus on the problem of making real-time personalized recommendations which are now needed in just about every online setting, ranging from media platforms to e-commerce to social networks. / While the challenge of estimating user preferences has garnered significant attention, the operational problem of using such preferences to construct personalized offer sets to users is still a challenge, particularly in modern settings with a massive number of items and a millisecond response time requirement. Thus motivated, we propose an algorithm for personalized offer set optimization that runs in time sub-linear in the number of items while enjoying a uniform performance guarantee. Our algorithm works for an extremely general class of problems and models of user choice that includes the mixed multinomial logit model as a special case. Our algorithm can be entirely data-driven and empirical evaluation on a massive content discovery dataset shows that our implementation indeed runs fast and with increased performance relative to existing fast heuristics. / Third, we study the problem of modeling purchase of multiple items (in online and offline settings) and utilizing it to display optimized recommendations, which can lead to significantly higher revenues as compared to capturing purchase of only a single product in each transaction. We present a parsimonious multi-purchase family of choice models called the BundleMVL-K family, and develop a binary search based iterative strategy that efficiently computes optimized recommendations for this model. We establish the hardness of computing optimal recommendation sets and characterize structural properties of the optimal solution. The efficacy of our modeling and optimization techniques compared to competing solutions is shown using several real-world datasets on multiple metrics such as model fit, expected revenue gains, and run-time reductions. Fourth, we study the problem of A-B testing for online platforms. / Unlike traditional offline A-B testing, online platforms face some unique challenges such as sequential allocation of users into treatment groups, large number of user covariates to balance, and limited number of users available for each experiment, making randomization inefficient. We consider the problem of optimally allocating test subjects to either treatment with a view to maximize the precision of our estimate of the treatment effect. Our main contribution is a tractable algorithm for this problem in the online setting, where subjects must be assigned as they arrive, with covariates drawn from an elliptical distribution with finite second moment. We further characterize the gain in precision afforded by optimized allocations relative to randomized allocations and show that this gain grows large as the number of covariates grows. / by Deeksha Sinha. / Ph. D. / Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, February, 2021 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 119-122). / Modern retail has been significantly affected by the surge in online platforms and product options. Customers have comfortably settled into an omni-channel model, in which they buy different products through different channels. While customers expect a seamless process in getting the products they are looking for, they are also more influenced by the selection offered when unsure of what to buy. For retailers, the transition to omnichannel means more complex problems of inventory positioning and demand fulfillment, but also an opportunity to influence their customers through the assortments they offer, especially online. In this thesis, we study two main challenges related to inventory positioning in omni-channel and provide new models and algorithms. First, we study the problem of choice modeling and assortment optimization. Choice models aim to capture customer preferences across products and have been extensively studied. / Whereas numerous models have been proposed, few are tractable, and many have been shown to be limited in capturing customer preferences, due to their underlying assumptions on consumer behavior. In the first part of this thesis, we introduce a new class of models, which we call synergistic, and show both theoretically and empirically, that these models dominate all existing ones in capturing consumer preferences. We show the associated optimization problems for the synergistic models are NP-hard, but provide IP-based algorithms, which are reasonably tractable in practice. Finally, we show that these models can be represented as ReLU activated neural networks. Therefore, state of the art methods in the neural networks field can be leveraged to efficiently estimate these models and optimize over them, to inform assortment optimization decisions. / In the second part of the thesis, we focus on inventory planning for a physical retailer, considering the complex dynamics in the store involving the backroom, and the need to minimize its use. The question is motivated by our collaborator, a large US retail chain, striving to leverage their store assets as shipping hubs. We present a case study of working with real data to understand the complexities of this question and identify steps a retailer can take to become leaner. / by Andreea Georgescu. / S.M. / S.M. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, September, 2020 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 167-170). / Linear inequality systems play a foundational role in Operations Research, but many fundamental structural and algorithmic questions about linear inequality systems remain unanswered. This thesis considers and addresses some of these questions. In the first chapter, we reconsider the ellipsoid algorithm applied to solving a system of linear inequalities. Unlike the simplex method and interior point methods, the ellipsoid algorithm has no mechanism for proving that a system is infeasible (in the real model of computation). Motivated by this, we develop an ellipsoid algorithm that produces a solution to a system or provides a simple proof that no solution exists. Depending on the dimensions and on other natural condition measures, the computational complexity of our algorithm may be worse than, the same as, or better than that of the standard ellipsoid algorithm.. In the second chapter, we reduce the problem of solving a homogeneous linear inequality system to the problem of finding the unique sink of a unique sink orientation (USO) in the vertex evaluation model of computation. We show the USOs of interest satisfy a local property that is not satisfied by all USOs that satisfy the Holt-Klee property. This addresses an open question that is motivated by the idea that such local structure could be leveraged algorithmically to develop faster algorithms or a strongly polynomial algorithm. In the third chapter, we make progress on a conjecture about a particular class of linear inequality systems that have balanced constraint matrices. A balanced matrix is a 0-1 matrix that does not contain a square submatrix of odd order with two ones per row and column. The conjecture asserts that every nonzero balanced matrix contains an entry equal to 1, which upon setting to 0, leaves the matrix balanced. / by Jourdain Bernard Lamperski. / Ph. D. / Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2009. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 133-135). / Unmanned aerial vehicles are being incorporated in an increasing variety of operations. To take full advantage of the vehicles, the plans for the operations should integrate each vehicle's capabilities when planning the operations. This thesis focuses on planning operations for multiple, heterogeneous UAVs for the purpose of monitoring Earth's phenomena through data collection. The planning is done for flight in three dimensions. The problem also includes time window constraints for data collection and incorporates human input in the planning process. Two solution methods are presented: (1) a mixed-integer program, and (2) an algorithm that utilizes a meta-heuristic to generate composite variables for a linear program, called the Composite Operations Planning Algorithm. The suitability of the two methods to solve the operations planning problem is compared based on the ability of each of the methods to find high-value, feasible solutions for large-scale, operationally sized problems in a reasonable amount of time. The analysis shows that the Composite Operations Planning Algorithm can develop operations plans for problems including 15 UAVs and 5000 nodes in less than 25 minutes using a desktop computer. / by Blair Ellen Leake Negron. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2010. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 189-194). / Recent decades have seen the development of more advanced sensor and communication systems, with the future certainly holding more innovation in these areas. However, current operations involve "stovepipe" systems in which inefficiencies are inherent. In this thesis, we examine how to increase the value of Earth observations made by coordinating across multiple collection systems. We consider both air and space assets in an asynchronous and distributed environment. We consider requests with time windows and priority levels, some of which require simultaneous observations by different sensors. We consider how these improvements could impact Earth observing sensors in two use areas; climate studies and intelligence collection operations. The primary contributions of this thesis include our approach to the asynchronous and distributed nature of the problem and the development of a value function to facilitate the coordination of the observations with multiple surveillance assets. We embed a carefully constructed value function in a simple optimization problem that we prove can be solved as a Linear Programming (LP) problem. We solve the optimization problem repeatedly over time to intelligently allocate requests to single-mission planners, or "sub-planners." We then show that the value function performs as we intend through empirical and statistical analysis. To test our methodologies, we integrate the coordination planner with two types of sub-planners, an Unmanned Aerial Vehicle (UAV) sub-planner, and a satellite sub-planner. We use the coordinator to generate observation plans for two notional operational Earth Science scenarios. Specifically, we show that coordination offers improvements in the priority of the requests serviced, the quality of those observations, and the ability to take dual collections. We conclude that a coordinated planning framework provides clear benefits. / by Thomas Michael Herold. / S.M.