Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2000. / Includes bibliographical references (leaves 181-189). / We develop Approximate Dynamic Programming (ADP) methods to integer programming problems. We describe and investigate parametric, nonparametric and base-heuristic learning approaches to approximate the value function in order to break the curse of dimensionality. Through an extensive computational study we illustrate that our ADP approach to integer programming competes successfully with existing methodologies including state of art commercial packages like CPLEX. Our benchmarks for comparison are solution quality, running time and robustness (i.e., small deviations in the computational resources such as running time for varying instances of same size). In this thesis, we particularly focus on knapsack problems and the binary integer programming problem. We explore an integrated approach to solve discrete optimization problems by unifying optimization techniques with statistical learning. Overall, this research illustrates that the ADP is a promising technique by providing near-optimal solutions within reasonable amount of computation time especially for large scale problems with thousands of variables and constraints. Thus, Approximate Dynamic Programming can be considered as a new alternative to existing approximate methods for discrete optimization problems. / by Ramazan Demir. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2009. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Includes bibliographical references (leaves 157-165). / Efficient allocation of scarce resources in networks is an important problem worldwide. In this thesis, we focus on resource allocation problems in a network of congested airports. The increasing demand for access to the world's major commercial airports combined with the limited operational capacity at many of these airports have led to growing air traffic congestion resulting in several billion dollars of delay cost every year. In this thesis, we study two demand-management techniques -- strategic and operational approaches -- to mitigate airport congestion. As a strategic initiative, auctions have been proposed to allocate runway slot capacity. We focus on two elements in the design of such slot auctions -- airline valuations and activity rules. An aspect of airport slot market environments, which we argue must be considered in auction design, is the fact that the participating airlines are budget-constrained. -- The problem of finding the best bundle of slots on which to bid in an iterative combinatorial auction, also called the preference elicitation problem, is a particularly hard problem, even more in the case of airlines in a slot auction. We propose a valuation model, called the Aggregated Integrated Airline Scheduling and Fleet Assignment Model, to help airlines understand the true value of the different bundles of slots in the auction. This model is efficient and was found to be robust to data uncertainty in our experimental simulations. / (cont.) -- Activity rules are checks made by the auctioneer at the end of every round to suppress strategic behavior by bidders and to promote consistent, continual preference elicitation. These rules find applications in several real world scenarios including slot auctions. We show that the commonly used activity rules are not applicable for slot auctions as they prevent straightforward behavior by budget-constrained bidders. We propose the notion of a strong activity rule which characterizes straightforward bidding strategies. We then show how a strong activity rule in the context of budget-constrained bidders (and quasilinear bidders) can be expressed as a linear feasibility problem. This work on activity rules also applies to more general iterative combinatorial auctions.We also study operational (real-time) demand-management initiatives that are used when there are sudden drops in capacity at airports due to various uncertainties, such as bad-weather. We propose a system design that integrates the capacity allocation, airline recovery and inter-airline slot exchange procedures, and suggest metrics to evaluate the different approaches to fair allocations. / by Pavithra Harsha. / Ph.D.

Thesis: S.M., 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 90-95). / We present work in identifying, modeling, and predicting the structure of influence in a communication network. We focus on cellular phone data, which provides a near-global population sample (in contrast to the relatively limited scope of social media and other internet-based datasets) at the expense of losing any knowledge of the content of the communications themselves. First, using inexact tree matching and hierarchical clustering, we propose a novel method for extracting persistent patterns of communication among individuals, which we term persistent cascades. We find the cascades are short in duration ('bursty'), exhibit habitual hierarchy and long-term persistence, and reveal new roles in weekday vs. weekend spreading. We show that the persistent cascades in the data are significantly different than what is found in a random network, which we illustrate both analytically and through simulation. We show that persistent cascade membership increases the likelihood of receiving information spreading through the network, even after controlling for overall call activity. Finally, we show that the method is extensible to other communication datasets by applying it to an email dataset. In this case study, we find our approach correctly identifies key individuals, ignores noise, and identifies several interesting email chains. Second, we propose a probabilistic model for the influence structure of a network, based on a multivariate stochastic process called a Hawkes process. We develop a novel approach for parameter estimation in this model that uses a Bayesian expectation-maximization (EM) scheme with a network prior. We first apply the model in the univariate case to the group conversations identified using the persistent cascades methodology. We find that the model performs well as a predictor, and also that the estimated parameter values reveal two types of persistent cascades: low-activity conversations with high temporal clustering, and high activity conversations with moderate temporal clustering. We then apply the model in the multivariate case to samples of the cell phone data, finding that the resulting estimate of the influence matrix extends our findings with the persistent cascades. / by Steven T. Morse. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2008. / Includes bibliographical references (leaf 91). / In this thesis we study modifications of the classical Mean-Variance Portfolio Optimization model. Our objective is to identify an optimal subset of assets from all available assets to maximize the expected return while incurring the minimum risk. In addition, we test several approaches to measuring the effect of the variance of the portfolio on the optimal asset allocation. We have developed a mixed integer formulation to solve the well known Markowitz portfolio model. Our model captures and solves the certain practical drawbacks that a real investor would face with the Markowitz approach. For example, by selecting a limited number of assets our procedure tends to prevent small allocations of assets. In addition, we find that in most cases, the maximum drawdown increases as a function of the upper bound on the variance of the portfolio and that this result is consistent with intuition, since portfolio risk increases as the chance that a drawdown event occurs also increases. However, we have observed that altering the composition of the portfolio can mitigate the risk of a drawdown event. / by Martin Quinteros. / S.M.

Thesis: S.M., 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 95-97). / In this thesis, we introduce and analyze models for air asset scheduling within a military theater. Specifically, we seek to create models that generate aircraft-specific schedules for Air Tasking Orders (ATOs) within a Joint Aerospace Operations Center (JAOC). A JAOC provides command and control of all air and space assets tasked to a particular region/area of responsibility (AOR) or strategic command. Scheduling these assets requires a high level of unified effort whereby centralized planning must be handled in a decentralized fashion and is known as the Air Tasking Cycle. Given the complexity of this process, subject matter experts from diverse backgrounds are required to design and plan missions for most operations. In addition, the difficulty of the process dictates that mission prioritization and aircraft/munitions allocation are separated in the cycle, sacrificing some global perspective for the sake of efficiency in the scheduling process. We present a modeling framework that allows planners to simultaneously select missions and assign aircraft/munitions to the missions, allowing for the optimal air asset scheduling toward the pursuit of theater-level objectives. This flexible framework takes into account air refueling considerations as well as the need for certain missions to be completed by "packages" of particular aircraft types. We submit heuristic, mixed integer optimization (MIO), and hybrid models within this structure and analyze the value of their schedules and the corresponding trade-offs with computational solve time.0 / by Kevin Joseph Rossillon. / S.M.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 1999. / Includes bibliographical references (p. 152-158). / Queueing networks serve a& useful models for a variety of problems arising in modern communications, computer, and manufacturing systems. Since the optimal control problem for queueing networks is well-known to be intractable, an important theme of research during the last two decades has been the development of tractable approximations, and the use of these approximations to determine optimal controls. Fluid relaxations are an important class of such approximations that have received much attention in recent years. The central aim of this dissertation is to demonstrate the usefulness of fluid relaxations in solving a variety of scheduling problems. In the first part of this dissertation, we explore the role of fluid relaxations in solving traditional job shop problems. For the job shop problem with the objective of minimizing makespan, we construct a schedule that is guaranteed to be within a constant of the optimal. In particular, our schedule is asymptotically optimal. We prove an analogous asymptoticoptimality result for the objective of minimizing holding costs. For both objectives, we report impressive computational results on benchmark instances chosen from the OR library. Our algorithms use fluid relaxations in two different ways: first, the optimal fluid cost is used as a lower bound for the original problem; and second, a discrete schedule is constructed by appropriately rounding an optimal fluid solution. In the second part of this dissertation we study the optimal control problem for multiclass queueing networks in steady-state. A key difficulty is that the fluid relaxation, being transient in nature, does not readily yield a lower bound for the steady-state problem. For this reason, we use a class of lower bounds, based on semidefinite relaxations, first proposed by Bertsimas and Niiio-Mora. Interestingly, one of the shortcomings of these relaxations is that there is no natural way to derive policies based on them. Thus, while our lower bounds are based on semidefinite relaxations, our policies are based on a heuristic interpretation of optimal fluid solutions. We consider objective functions involving both first and second moments of queue-lengths (equivalently, delays). Our computational results show the effectiveness of this approach in obtaining good policies for multiclass queueing networks. Finally, we turn our attention to the problem of computing the optimal fluid solution efficiently. We develop a general method to solve the optimal control problem for fluid tandem networks, and identify ... solvable special cases. / by Jayachandran Sethuraman. / Ph.D.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2017. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 121-123). / Combining social media posts with known user locations can lead to unique insights with applications ranging from tracking diffusion of sentiment to earthquake detection. One approach used to determine a user's home location is to examine the timing of their posts, but the precision of existing time-based location predictors is limited to discrimination among time zones. In this thesis, we formulate a general time-based geolocation algorithm that has greater precision, using knowledge of a social media user's real world activities derived from his or her membership in a particular class. Our activity-based model discriminates among locations within a time zone, with city-level accuracy. We also develop methods to solve two related inference tasks. The first method detects when a user travels, allowing us to exclude posts when a user is away from his or her home location. Our other method classifies an account as belonging to a particular user group based on the time series of posts and a known user location. Finally, we test the performance of our geolocation model and related methods using Twitter accounts belonging to Muslims. Using Islamic prayer activity to inform our model, we are able to infer the locations of Muslim accounts. We are also able to accurately determine if an account belongs to a Muslim or non-Muslim using their activity patterns and location. Our work challenges the accepted practices used to protect online privacy by demonstrating that timing of user activity can provide specific location or group membership information. / by Matthew Robert Webb. / S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2010. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 160-165). / This thesis studies optimal stopping problems for strategic agents in the context of two economic applications: experimentation in a competitive market and information exchange in social networks. The economic agents (firms in the first application, individuals in the second) take actions, whose payoffs depend on an unknown underlying state. Our framework is characterized by the following key feature: agents time their actions to take advantage of either the outcome of the actions of others (experimentation model) or information obtained over time by their peers (information exchange model). Equilibria in both environments are typically inefficient, since information is imperfect and, thus, there is a benefit in being a late mover, but delaying is costly. More specifically, in the first part of the thesis, we develop a model of experimentation and innovation in a competitive multi-firm environment. Each firm receives a private signal on the success probability of a research project and decides when and which project to implement. A successful innovation can be copied by other firms. We start the analysis by considering the symmetric environment, where the signal quality is the same for all firms. Symmetric equilibria (where actions do not depend on the identity of the firm) always involve delayed and staggered experimentation, whereas the optimal allocation never involves delays and may involve simultaneous rather than staggered experimentation. The social cost of insufficient experimentation can be arbitrarily large. Then, we study the role of simple instruments in improving over equilibrium outcomes. We show that appropriately-designed patents can implement the socially optimal allocation (in all equilibria) by encouraging rapid experimentation and efficient ex post transfer of knowledge across firms. In contrast to patents, subsidies to experimentation, research, or innovation cannot typically achieve this objective. We also discuss the case when signal quality is private information and differs across firms. We show that in this more general environment patents again encourage experimentation and reduce delays. In the second part, we study a model of information exchange among rational individuals through communication and investigate its implications for information aggregation in large societies. An underlying state (of the world) determines which action has higher payoff. Agents receive a private signal correlated with the underlying state. They then exchange information over their social network until taking an (irreversible) action. We define asymptotic learning as the fraction of agents taking an action that is close to optimal converging to one in probability as a society grows large. Under truthful communication, we show that asymptotic learning occurs if (and under some additional conditions, also only if) in the social network most agents are a short distance away from "information hubs", which receive and distribute a large amount of information. Asymptotic learning therefore requires information to be aggregated in the hands of a few agents. We also show that while truthful communication is not always optimal, when the communication network induces asymptotic learning (in a large society), truthful communication is an equilibrium. Then, we discuss the welfare implications of equilibrium behavior. In particular, we compare the aggregate welfare at equilibrium with that of the optimal allocation, which is defined as the strategy profile a social planner would choose, so as to maximize the expected aggregate welfare. We show that when asymptotic learning occurs all equilibria are efficient. A partial converse is also true: if asymptotic learning does not occur at the optimal allocation and an additional mild condition holds at an equilibrium, then the equilibrium is inefficient. Furthermore, we discuss how our learning results can be applied to several commonly studied random graph models, such as preferential attachment and Erdos-Renyi graphs. In the final part, we study strategic network formation in the context of information exchange. In particular, we relax the assumption that the social network over which agents communicate is fixed, and we let agents decide which agents to form a communication link with incurring an associated cost. We provide a systematic investigation of what types of cost structures and associated social cliques (consisting of groups of individuals linked to each other at zero cost, such as friendship networks) ensure the emergence of communication networks that lead to asymptotic learning. Our result shows that societies with too many and sufficiently large social cliques do not induce asymptotic learning, because each social clique would have sufficient information by itself, making communication with others relatively unattractive. Asymptotic learning results if social cliques are neither too numerous nor too large, in which case communication across cliques is encouraged. / by Kostas Bimpikis. / Ph.D.

Thesis: S.M., 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 61-62). / A fully polynomial time approximation scheme (FPTAS) is an algorithm that returns ... -optimal solution to a maximization problem of size n, which runs in polynomial time in both ... We develop faster FPTASs for several classes of knapsack problems. In this thesis, we will first survey the relevant literature in FPTASs for knapsack problems. We propose the use of floating point arithmetic rather than the use of geometric rounding in order to simplify analysis. Given a knapsack problem that yield an ... -optimal solution for disjoint subsets S and T of decision variables, we show how to attain ... -optimal solution for the knapsack problem for the set ... We use this procedure to speed up the run-time of FPTASs for: 1. The Integer Knapsack Problem, 2. The Unbounded Integer Knapsack Problem, 3. The Multiple-Choice Knapsack Problem, and, 4. The Nonlinear Integer Knapsack Problem, Using addition ideas, we develop a fast fully polynomial time randomized approximation scheme (FPTAS) for the 0-1 Knapsack Problem, which has the run-time of ... / by Donguk Rhee. / S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2004. / Includes bibliographical references (p. 235-239). / Traditionally, industrial buyers have focused on long-term contracts for many of their purchasing needs. Recently, however, some high-tech manufacturers have started looking at more flexible contracts for non-strategic components, which enables them to buy from a variety of suppliers and the spot market. We study this type of strategies in a general framework for supply contracts, in which portfolios of contracts can be analyzed and optimized. We examine a multi-period model where expected profit is optimized, and a single-period model where a mean-variance objective is considered. In addition, we investigate what the consequences of such purchasing behavior might be. For this purpose, we study the game where suppliers compete on price and flexibility for the buyer's orders. We characterize the suppliers' Nash equilibria in pure strategies and show that, when demand is log-concave, there exists one or multiple equilibria, and that in any of these, suppliers bid in clusters against other suppliers with similar technologies. / by Victor Martínez-de-Albéniz. / Ph.D.