Thesis. 1977. Ph.D.--Massachusetts Institute of Technology. Dept. of Civil Engineering. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Vita. / Bibliography: leaves 222-226. / Ph.D.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1980. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Bibliography: leaves 157-161. / by Gregory S. Lauer. / Ph.D.

Sequential decision making problems are ubiquitous in a number of research areas such as operations research, finance, engineering and computer science. The main challenge with these problems comes from the fact that, firstly, there is uncertainty about the future. And secondly, decisions have to be made over a period of time, sequentially. These problems, in many cases, are modeled as Markov Decision Process (MDP). Most real-life MDPs are ‘high dimensional’ in nature making them challenging from a numerical point of view. We consider a number of such high dimensional MDPs. In some cases such problems can be approximately solved using Approximate Dynamic Programming. In other cases problem specific analysis can be solved to device tractable policies that are near-optimal. In Chapter 2, we presents a novel and practical non-parametric approximate dynamic programming (ADP) algorithm that enjoys graceful, dimension-independent approximation and sample complexity guarantees. In particular, we establish both theoretically and computationally that our proposal can serve as a viable replacement to state of the art parametric ADP algorithms, freeing the designer from carefully specifying an approximation architecture. We accomplish this by ‘kernelizing’ a recent mathematical program for ADP (the ‘smoothed’ approximate LP) proposed by [Desai et al., 2011]. In Chapter 3, we consider a class of stochastic control problems where the action space at each time can be described by a class of matching or, more generally, network flow polytopes. Special cases of this class of dynamic matching problems include many problems that are well-studied in the literature, such as: (i) online keyword matching in Internet advertising (the adwords problem); (ii) the bipartite matching of donated kidneys from cadavers to recipients; and (iii) the allocation of donated kidneys through exchanges over cycles of live donor-patient pairs. We provide an approximate dynamic program (ADP) algorithm for dynamic matching with stochastic arrivals and departures. Our framework is more general than the methods prevalent in the literature in that it is applicable to a broad range of problems characterized by a variety of action polytopes and generic arrival and departure processes. In Chapter 4, we consider the problem of A-B testing when the impact of the treatment is marred by a large number of covariates. Randomization can be highly inefficient in such settings, and thus we consider the problem of optimally allocating test subjects to either treatment with a view to maximizing the efficiency of our estimate of the treatment effect. Our main contribution is a tractable algorithm for this problem in the online setting, where subjects arrive, and must be assigned, sequentially. We characterize the value of optimized allocations relative to randomized allocations and show that this value grows large as the number of covariates grows. In particular, we show that there is a lot to be gained from ‘optimizing’ the process of A-B testing relative to the simple randomized trials that are the mainstay of A-B testing in the ‘big data’ regime of modern e-commerce applications, where the number of covariates is often comparable to the number of experimental trials.

Orientador: Aluir Porfírio Dal Poz / Resumo: A aquisição de informações espaciais é uma das tarefas mais dispendiosa e morosa na implantação e na manutenção de Sistemas de informação Geográfica (SIG's). Nos últimos 30 anos, inúmeras pesquisas foram realizadas objetivando o melhoramento do tempo e custo da aquisição de dados espaciais. No que se refere a aquisição de dados espaciais a partir de imagens digitais, é possível notar que os métodos desenvolvidos até então estão mais próximos desta meta quando os respectivos níveis de automação são mais altos. Como as soluções totalmente automáticas não estão ainda no mesmo nível de confiabilidade dos métodos manuais, soluções semi-automáticas combinando a habilidade natural de operadores humanos em tarefas de reconhecimento e a capacidade de algoritmos computacionais em realizar tarefas de medidas precisas e morosas, têm sido propostas. Seguindo esta tendência, este trabalho propõe uma metodologia semi-automática para a extração de rodovias em imagens digitais de média e alta resolução baseada no algoritmo de otimização global de programação dinâmica. É importante enfatizar que os trabalhos relacionados com extração de feições através de programação dinâmica sempre usam imagens de baixa resolução, na qual as rodovias manifestam-se como estruturas lineares. Ao contrário, rodovias em imagens de média e alta resolução se manifestam como faixas alongadas. Assim, como neste caso o objetivo básico é extrair o eixo da rodovia, este trabalho propõe uma modificação na função custo usada numa metodologia preexistente baseada em programação dinâmica, permitindo que o eixo central da rodovia seja precisamente extraído pela metodologia modificada. A diferença básica entre este método modificado e o original é uma função de injunção, proposta com o objetivo de incorporar características de bordas de rodovia...(Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The acquisition of spatial information is one of most expensive and time consuming tasks in developing and maintaining Geographical Information Systems (GIS's). In the last 30 years, countless researches have been accomplished aiming at improvement of spatial data acquisition time and cost. Related to the spatial data acquisition from digital images, it is possible to notice that the methods developed until now are closer to that goal when the respective levels of automation are higher. As fully automatic solutions are not in same level of reliability of manual procedures, semi-automatic solutions combining the natural skill of humans operators in recognizing tasks and the power of computational algorithm in carrying out precise and time consuming measurement tasks, have been proposed. Following this trend, this work proposes a semi-automatic methodology for road extraction from mediumand high-resolution digital images based on the global optimization algorithm of dynamic programming. It is important to emphasize that related works on feature extraction by dynamic programming always use low-resolution images, in which roads manifest as linear structures. As opposed to this, roads in medium- and high-resolution manifest as elongated regions. Thus, as in this case the basic objective is to extract the road centerline, this work proposes a modification of cost function used in a preexisting dynamic programming approach, allowing the road centerline to be precisely extracted by the modified method. The basic difference between this modified method and the original one is the proposed constraint function embodying some road edge characteristics, as e.g. the anti-parallelism of gradient vectors at two pixels situated on opposite road edges and belonged to the same road crosssection...(Complete abstract click electronic access below) / Mestre

Esta tese é dedicada ao estudo de modelos de otimização de carteiras de investimento multi-período. Daremos ênfase a um modelo com restrições intermediárias formulado como um problema de controle ótimo e resolvido utilizando técnicas de programação dinâmica. Serão tratados aspectos teóricos e práticos desta classe de problemas. Primeiramente faremos uma revisão das principais hipóteses dos modelos de otimização de carteiras e o caso uni-período. Analisaremos a seguir as generalizações para o caso multi-período, onde os modelos utilizam apenas restrições para o valor esperado e/ou para a variância da carteira no instante final do período analisado. Apresentaremos então o principal resultado proposto neste trabalho onde consideramos o problema de seleção ótima de ativos multi-período no qual podemos incorporar ao modelo restrições intermediárias para o valor esperado e variância da carteira durante o período de análise. A grande vantagem desta técnica é permitir o controle do valor esperado e/ou da variância da carteira ao longo de todo o horizonte de análise. Faremos uma comparação o entre as formulações apresentadas e realizaremos experimentos numéricos com o modelo proposta nesta tese. Os principais resultados originais desta tese encontram-se no Capítulo 5. No Capítulo 6 apresentamos as simulações numéricas realizadas com o modelo proposto. / The subject of this thesis is the study of multi-period portfolio optimization problems. We focus on a model with intermediate constraints formulated as an optimal control problem and solved by using dynamic programming techniques. Both theoretical and practical issues are addressed. Firstly we will analyze the main hypothesis of portfolio optimization models and the single period case. Then we will present the generalization for the multi-period case, where the models use only constraints for the expected value and variance at the final period. The main result proposed in this work considers the multi-period portfolio selection problem with intermediate constraints on the expected value and variance of the portfolio taken into account in the optimization problem. The main advantage of this technique is that it is possible to control the intermediate expected value or variance of the portfolio during the time horizon considered. Comparison between the presented formulations and numerical experiments of the proposed model will be exposed. The main original results of this thesis can be found in Chapter 5. In Chapter 6 we present numerical simulations with the proposed model.

Activity retrieval is a growing field in electrical engineering that specializes in the search and retrieval of relevant activities and events in video corpora. With the affordability and popularity of cameras for government, personal and retail use, the quantity of available video data is rapidly outscaling our ability to reason over it. Towards the end of empowering users to navigate and interact with the contents of these video corpora, we propose a framework for exploratory search that emphasizes activity structure and search space reduction over complex feature representations. Exploratory search is a user driven process wherein a person provides a system with a query describing the activity, event, or object he is interested in finding. Typically, this description takes the implicit form of one or more exemplar videos, but it can also involve an explicit description. The system returns candidate matches, followed by query refinement and iteration. System performance is judged by the run-time of the system and the precision/recall curve of of the query matches returned. Scaling is one of the primary challenges in video search. From vast web-video archives like youtube (1 billion videos and counting) to the 30 million active surveillance cameras shooting an estimated 4 billion hours of footage every week in the United States, trying to find a set of matches can be like looking for a needle in a haystack. Our goal is to create an efficient archival representation of video corpora that can be calculated in real-time as video streams in, and then enables a user to quickly get a set of results that match. First, we design a system for rapidly identifying simple queries in large-scale video corpora. Instead of focusing on feature design, our system focuses on the spatiotemporal relationships between those features as a means of disambiguating an activity of interest from background. We define a semantic feature vocabulary of concepts that are both readily extracted from video and easily understood by an operator. As data streams in, features are hashed to an inverted index and retrieved in constant time after the system is presented with a user's query. We take a zero-shot approach to exploratory search: the user manually assembles vocabulary elements like color, speed, size and type into a graph. Given that information, we perform an initial downsampling of the archived data, and design a novel dynamic programming approach based on genome-sequencing to search for similar patterns. Experimental results indicate that this approach outperforms other methods for detecting activities in surveillance video datasets. Second, we address the problem of representing complex activities that take place over long spans of space and time. Subgraph and graph matching methods have seen limited use in exploratory search because both problems are provably NP-hard. In this work, we render these problems computationally tractable by identifying the maximally discriminative spanning tree (MDST), and using dynamic programming to optimally reduce the archive data based on a custom algorithm for tree-matching in attributed relational graphs. We demonstrate the efficacy of this approach on popular surveillance video datasets in several modalities. Finally, we design an approach for successive search space reduction in subgraph matching problems. Given a query graph and archival data, our algorithm iteratively selects spanning trees from the query graph that optimize the expected search space reduction at each step until the archive converges. We use this approach to efficiently reason over video surveillance datasets, simulated data, as well as large graphs of protein data.

Les préoccupations environnementales grandissantes nous ont conduits à faire des efforts pour réduire les émissions de gaz à effet de serre, notamment dans le domaine de la production de l’énergie électrique. C’est dans ce contexte que Leroy Somer a lancé des recherches sur les groupes électrogènes hybrides afin de minimiser la consommation de carburant et les coûts d’exploitations. Pour aborder les questions du dimensionnement des ressources matérielles et de leur utilisation optimale, une méthodologie est développée dans cette thèse. La recherche de la stratégie de gestion de l’énergie optimale est basée sur l’algorithme de programmation dynamique de Bellman. Elle sera associée à un algorithme d’optimisation à évolution différentielle pour optimiser le dimensionnement de la structure hybride. Les fonctions de coûts des optimisations sont obtenues par le développement de modèles énergétiques et économiques. Grâce à cette méthode, nous montrons que les gains d’un groupe électrogène hybride sont fortement liés à l’utilisation que l’on aura de celui-ci. Dans les cas où le groupe électrogène est utilisé sur des profils avec de faibles facteurs de charge, les gains pourront être conséquents. Il sera donc primordial de bien connaitre les profils de charge de l’application avant de dimensionner la structure tout entière du groupe électrogène hybride. Les travaux ont également débouché sur une mise en œuvre expérimentale qui a pu valider les premiers résultats obtenu lors des simulations. / Growing environmental issues and concerns have led to efforts to reduce CO2 and greenhouse effect pollutant emissions in the field of electric power generation. This has led Leroy Somer to investigate systems based on hybrid technologies to reduce genset fuel consumption and operating costs. A methodology is developed in this thesis to address issues of sizing hardware resources and their optimal use. The optimum energy management strategy is based on the dynamic programming algorithm of Bellman. It will be associated to a differential evolution optimization algorithm to optimize the design of the hybrid structure. The objective functions are obtained by developing energetic and economic models. Through this method, we show that the benefits of a hybrid generator are strongly related to its use. In cases where the generator is used on profiles with low load factors, the benefits will be significant. It will be very important to have good knowledge of load profiles applications before sizing the whole structure of the hybrid generator. A prototype of this system has been developed and has confirmed simulation results.

Heap models in the max-plus algebra are interesting dynamical systems that can be used to model a variety of tetris-like systems, such as batch flow shops for manufacturing models. Each heap in the model can be identified with a single product to manufacture. The objective is to manufacture a group of products in such an order so as to minimize the total manufacturing time. Because this scheduling problem reduces to a variation of the Traveling Salesman Problem (known to be NP-complete), the optimal solution is computationally infeasible for many real-world systems. Thus, a feasible approximation method is needed. This work builds on and expands the existing heap model in order to more effectively solve the scheduling problems. Specifically, this work:1. Further characterizes the admissible products to these systems.2. Further characterizes sets of admissible products. 3. Presents a novel algorithm, the asynchronous $t$-step approximation, to approximate these systems.4. Proves error bounds for the system approximation, and show why these error bounds are better than the existing approximation.

In the first chapter, I consider the institutional structures as well as the doctrines typically encountered in the surface water sector. To investigate the sources and methods of government support in the water sector, I categorize different sorts of government support according to the location of water along the water cycle. I conclude the section with examples of observed water markets. In the second chapter, I consider the problem of water usage, developing a model to analyze the optimal pricing of water within a second-best economy. As a water supplier, the local government may price discriminate across consumers and farmers. I introduce the second-best pricing scheme, derive conditions for the marginal-cost pricing and inverse-elasticity rules, and analyze when the government optimally deviates from these two pricing schemes. In the third chapter, I provide an analysis of the data I collected from Turkey. First, I examine the data on reservoir flows, including service share and fixed costs of the reservoirs. Then, I provide details about the relationship between the quantity and price of irrigation and of tap water. Finally, in the fourth chapter, I apply the theoretical framework to the data from Turkey. In Turkey, the current water-pricing policy is dictated by the sole objective of breaking-even in each period. This results in large withdrawals, which is not sustainable in the long-run, hence not optimal. I analyze the dynamic optimal water resource management problem of a benevolent government. I compare the implications of the current and the optimal pricing policies.

Motivated by the management of sales representatives who visit customers to develop customer relationships, we present a stochastic orienteering problem on a network of queues, in which a hard time window is associated with each customer and the representative may experience uncertain wait time resulting from a queueing process at the customer. In general, given a list of potential customers and a time horizon consisting of several periods, the sales representative needs to decide which customers to visit in each period and how to visit customers within the period, with an objective to maximize the total reward collected by the end of the horizon. We start our study with a daily orienteering problem, which is a subproblem of the general problem. We focus on developing a priori and dynamic routing strategies for the salesperson to implement during a day. In the a priori routing case, the salesperson visits customers in a pre-planned order, and we seek to construct a static sequence of customers that maximizes the expected value collected. We consider two types of recourse actions. One is to skip a customer specified by an a priori route if the representative will arrive late in the customer's time window. The other type is to leave a customer immediately after arriving if observing a sufficiently long queue (balking) or to leave after waiting in queue for a period of time without meeting with the customer (reneging). We propose customer-specific decision rules to facilitate the execution of recourse actions and derive an analytical formula to compute the expected sales from the a priori route. We tailor a variable neighborhood search (VNS) heuristic to find a priori routes. In the dynamic routing case, the salesperson decides which customer to visit and how long to wait at each customer based on realized events. To seek dynamic routing policies, we propose an approximate dynamic programming approach based on rollout algorithms. The method introduces a two-stage heuristic estimation that we refer to as compound rollout. In the first stage, the algorithm decides whether to stay at the current customer or go to another customer. If departing the current customer, it chooses the customer to whom to go in the second stage. We demonstrate the value of our modeling and solution approaches by comparing the dynamic policies to a priori solutions with recourse actions. Finally, we address the multi-period orienteering problem. We consider that each customer's likelihood of adopting the representative's product stochastically evolves over time and is not fully observed by the representative. The representative can only estimate the adoption likelihood by meeting with the customer and the estimation may not be accurate. We model the problem as a partially observed Markov decision process with an objective to maximize the expected sales at the end of the horizon. We propose a heuristic that decomposes the problem into an assignment problem to schedule customers for a period and a routing problem to decide how to visit the scheduled customers within the period.