Neste trabalho, estudamos o problema de corte bidimensional multiperíodo com sobras aproveitáveis, que consiste em cortar objetos grandes visando a produção de um conjunto de itens menores. Supomos um horizonte de planejamento finito com uma quantidade finita de períodos entre os tempos inicial e final. Primeiramente consideramos uma versão determinística em que conhecemos, à priori, os itens solicitados em uma ordem de trabalho e o custo dos objetos a cada período. Algumas das sobras geradas durante o processo de corte dos itens solicitados em um período podem ser utilizadas como objetos no futuro. As sobras que podem ser usadas no futuro são denominadas sobras aproveitáveis. De forma geral, uma sobra é considerada aproveitável se possui dimensões iguais ou superiores as de algum item de uma lista pré-definida para o período. O objetivo é minimizar o custo total dos objetos utilizados para satisfazer a ordem de trabalho dos itens solicitados de todo o horizonte considerado. Havendo soluções com o mesmo custo, desejamos encontrar aquela que, no fim do horizonte de tempo considerado, maximize o valor das sobras aproveitáveis remanescentes. Apresentamos uma modelagem matemática do problema usando uma formulação em dois níveis, que é transformada em um modelo de programação linear inteira mista, devido às características do problema. Considerando a dificuldade em resolver o modelo desenvolvido, apresentamos uma proposta de uma abordagem heurística baseada em Programação Dinâmica Aproximada (PDA) para lidar com o problema proposto. Outras opções baseadas em estratégias do tipo horizonte rolante e relax-and-fix também são consideradas. Consideramos também o cenário onde não conhecemos de antemão os itens da ordem de trabalho e o custo dos objetos, mas temos informações das distribuições de probabilidade de ambos. Nesse caso, apresentamos uma abordagem baseada em programação dinâmica aproximada para estimar a melhor estratégia a ser seguida em cada período. Comparamos os resultados obtidos pela PDA com os resultados encontrados por um método guloso. Em cenários adequados, os resultados mostram que a PDA consegue soluções superiores ao método guloso. / In this research, we study the multi-period two-dimensional cutting problem with usable leftover, which consists of cutting objects to produce a set of items. We assume a finite planning horizon with a finite amount of periods between the initial and final times. First we consider a deterministic version in which we know, a priori, the set of ordered items and the cost of the objects at each period. Some of the leftovers generated during the cutting process of the ordered items in a period may be used as objects in the future. The leftovers that can be used in the future are called usable leftovers. In general, a leftover is considered usable if it has dimensions equal to or greater than that of some item from a predefined list for the period. The goal is to minimize the total cost of the objects used to cut the set of ordered items of the entire considered horizon. If there are solutions with the same cost, we wish to find one that, at the end of the considered time horizon, maximizes the value of the remaining usable leftovers. We present a mathematical model of the problem using a bilevel formulation, which is transformed into a mixed integer linear programming model, due to the characteristics of the problem. Considering the difficulty in solving the developed model, we propose a heuristic approach based on approximate dynamic programming (ADP) to deal with the proposed problem. Other options based on the rolling horizon and relax-and-fix strategies are also considered. We also consider the scenario where we do not know in advance the set of ordered items and the cost of the objects, but we have information about the probability distributions of both. In this case, we present an approach based on approximate dynamic programming to estimate the best strategy to be followed at each period. We compared the results obtained by the ADP with the results found by a greedy method. In suitable scenarios, the results show that the ADP achieves superior solutions to the greedy method.

The first part of this research program concerns the development of customized and easily implementable Probably Approximately Correct (PAC)-learning algorithms for episodic tasks over acyclic state spaces. The defining characteristic of our algorithms is that they take explicitly into consideration the acyclic structure of the underlying state space and the episodic nature of the considered learning task. The first of the above two attributes enables a very straightforward and efficient resolution of the ``exploration vs exploitation' dilemma, while the second provides a natural regenerating mechanism that is instrumental in the dynamics of our algorithms. Some additional characteristics that distinguish our algorithms from those developed in the past literature are (i) their direct nature, that eliminates the need of a complete specification of the underlying MDP model and reduces their execution to a very simple computation, and (ii) the unique emphasis that they place in the efficient implementation of the sampling process that is defined by their PAC property. More specifically, the aforementioned PAC-learning algorithms complete their learning task by implementing a systematic episodic sampling schedule on the underlying acyclic state space. This sampling schedule combined with the stochastic nature of the transitions taking place, define the need for efficient routing policies that will help the algorithms complete their exploration program while minimizing, in expectation, the number of executed episodes. The design of an optimal policy that will satisfy a specified pattern of arc visitation requirements in an acyclic stochastic graph, while minimizing the expected number of required episodes, is a challenging problem, even under the assumption that all the branching probabilities involved are known a priori. Hence, the sampling process that takes place in the proposed PAC-learning algorithms gives rise to a novel, very interesting stochastic control/scheduling problem, that is characterized as the problem of the Optimal Node Visitation (ONV) in acyclic stochastic digraphs. The second part of the work presented herein seeks the systematic modelling and analysis of the ONV problem. The last part of this research program explores the computational merits obtained by heuristical implementations that result from the integration of the ONV problem developments into the PAC-algorithms developed in the first part of this work. We study, through numerical experimentation, the relative performance of these resulting heuristical implementations in comparison to (i) the initial version of the PAC-learning algorithms, presented in the first part of the research program, and (ii) standard Q-learning algorithm variations provided in the RL literature. The work presented in this last part reinforces and confirms the driving assumption of this research, i.e., that one can design customized RL algorithms of enhanced performance if the underlying problem structure is taken into account.

[Truncated abstract. Please see the pdf version for the complete text. Also, formulae and special characters can only be approximated here. Please see the pdf version of this abstract for an accurate reproduction.] This thesis treats two aspects of intelligent control: The first part is about long-term optimization by approximating dynamic programming and in the second part a specific class of a fast neural network, related to support vector machines (SVMs), is considered. The first part relates to approximate dynamic programming, especially in the framework of adaptive critic designs (ACDs). Dynamic programming can be used to find an optimal decision or control policy over a long-term period. However, in practice it is difficult, and often impossible, to calculate a dynamic programming solution, due to the 'curse of dimensionality'. The adaptive critic design framework addresses this issue and tries to find a good solution by approximating the dynamic programming process for a stationary environment. In an adaptive critic design there are three modules, the plant or environment to be controlled, a critic to estimate the long-term cost and an action or controller module to produce the decision or control strategy. Even though there have been many publications on the subject over the past two decades, there are some points that have had less attention. While most of the publications address the training of the critic, one of the points that has not received systematic attention is training of the action module.¹ Normally, training starts with an arbitrary, hopefully stable, decision policy and its long-term cost is then estimated by the critic. Often the critic is a neural network that has to be trained, using a temporal difference and Bellman's principle of optimality. Once the critic network has converged, a policy improvement step is carried out by gradient descent to adjust the parameters of the controller network. Then the critic is retrained again to give the new long-term cost estimate. However, it would be preferable to focus more on extremal policies earlier in the training. Therefore, the Calculus of Variations is investigated to discard the idea of using the Euler equations to train the actor. However, an adaptive critic formulation for a continuous plant with a short-term cost as an integral cost density is made and the chain rule is applied to calculate the total derivative of the short-term cost with respect to the actor weights. This is different from the discrete systems, usually used in adaptive critics, which are used in conjunction with total ordered derivatives. This idea is then extended to second order derivatives such that Newton's method can be applied to speed up convergence. Based on this, an almost concurrent actor and critic training was proposed. The equations are developed for any non-linear system and short-term cost density function and these were tested on a linear quadratic regulator (LQR) setup. With this approach the solution to the actor and critic weights can be achieved in only a few actor-critic training cycles. Some other, more minor issues, in the adaptive critic framework are investigated, such as the influence of the discounting factor in the Bellman equation on total ordered derivatives, the target interpretation in backpropagation through time as moving and fixed targets, the relation between simultaneous recurrent networks and dynamic programming is stated and a reinterpretation of the recurrent generalized multilayer perceptron (GMLP) as a recurrent generalized finite impulse MLP (GFIR-MLP) is made. Another subject in this area that is investigated, is that of a hybrid dynamical system, characterized as a continuous plant and a set of basic feedback controllers, which are used to control the plant by finding a switching sequence to select one basic controller at a time. The special but important case is considered when the plant is linear but with some uncertainty in the state space and in the observation vector, and a quadratic cost function. This is a form of robust control, where a dynamic programming solution has to be calculated. &sup1Werbos comments that most treatment of action nets or policies either assume enumerative maximization, which is good only for small problems, except for the games of Backgammon or Go [1], or, gradient-based training. The latter is prone to difficulties with local minima due to the non-convex nature of the cost-to-go function. With incremental methods, such as backpropagation through time, calculus of variations and model-predictive control, the dangers of non-convexity of the cost-to-go function with respect to the control is much less than the with respect to the critic parameters, when the sampling times are small. Therefore, getting the critic right has priority. But with larger sampling times, when the control represents a more complex plan, non-convexity becomes more serious.

This thesis explores ideas from transport theory and optimal control to develop novel Monte Carlo methods to perform efficient statistical computation. The first project considers the problem of constructing a transport map between two given probability measures. In the Bayesian formalism, this approach is natural when one introduces a curve of probability measures connecting the prior to posterior by tempering the likelihood function. The main idea is to move samples from the prior using an ordinary differential equation (ODE), constructed by solving the Liouville partial differential equation (PDE) which governs the time evolution of measures along the curve. In this work, we first study the regularity solutions of Liouville equation should satisfy to guarantee validity of this construction. We place an emphasis on understanding these issues as it explains the difficulties associated with solutions that have been previously reported. After ensuring that the flow transport problem is well-defined, we give a constructive solution. However, this result is only formal as the representation is given in terms of integrals which are intractable. For computational tractability, we proposed a novel approximation of the PDE which yields an ODE whose drift depends on the full conditional distributions of the intermediate distributions. Even when the ODE is time-discretized and the full conditional distributions are approximated numerically, the resulting distribution of mapped samples can be evaluated and used as a proposal within Markov chain Monte Carlo and sequential Monte Carlo (SMC) schemes. We then illustrate experimentally that the resulting algorithm can outperform state-of-the-art SMC methods at a fixed computational complexity. The second project aims to exploit ideas from optimal control to design more efficient SMC methods. The key idea is to control the proposal distribution induced by a time-discretized Langevin dynamics so as to minimize the Kullback-Leibler divergence of the extended target distribution from the proposal. The optimal value functions of the resulting optimal control problem can then be approximated using algorithms developed in the approximate dynamic programming (ADP) literature. We introduce a novel iterative scheme to perform ADP, provide a theoretical analysis of the proposed algorithm and demonstrate that the latter can provide significant gains over state-of-the-art methods at a fixed computational complexity.

O planejamento operacional de um sistema de transporte de longa distância implica resolver um problema de otimização de rede dinâmica, visando a efetuar, de forma eficaz e eficiente, o atendimento às demandas de cargas, utilizando a capacidade de transporte disponível. A metodologia de solução proposta utiliza a abordagem de Rede de Filas Logísticas, a qual substitui o processo de otimização global da rede (usualmente utilizando Programação Linear Inteira) por um modelo de Programação Dinâmica Estocástica, Aproximada e Adaptativa, que permite a resolução de uma série de subproblemas delimitados no tempo, reduzindo sensivelmente a quantidade de variáveis envolvidas. Este método permite a utilização de modelos matemáticos mais realistas em horizontes de planejamento mais amplos. O presente trabalho estende os modelos encontrados na Literatura, aplicando o método a problemas de maior complexidade, incluindo a consideração de frotas heterogêneas de veículos, janelas de início de atendimento, utilização de terceiros transportadores e penalidades pelo não atendimento das demandas. São apresentados exemplos de problemas experimentais submetidos com sucesso à técnica desenvolvida. O trabalho inclui ainda o delineamento de um Sistema de Apoio à Decisão incorporando a metodologia proposta. / Operational planning of a long haul transportation system implies to solve a dynamic network optimization problem, aiming to perform the freight movements in an efficient and effective way, while utilizing the available transportation capacity. The proposed solution methodology utilizes the Logistic Queueing Network approach, replacing the network global optimization process through Integer Linear Programming by a model of Stochastic, Approximate and Adaptive Dynamic Programming, which allows the resolution of a sequence of sub- problems delimited in time, strongly reducing the quantity of variables involved. This method allows the utilization of more realistic mathematical models in a broader planning horizon. The research extends models found in the literature to solve more complex problems, including the consideration of heterogeneous fleet of vehicles, time windows, third party vehicles and penalties for not attendance of demands. Experimental problems solved successfully with the developed technique are presented. The work also presents the delineation of a Decision Support System incorporating the proposed methodology.

Neste trabalho, estudamos o problema de corte bidimensional multiperíodo com sobras aproveitáveis, que consiste em cortar objetos grandes visando a produção de um conjunto de itens menores. Supomos um horizonte de planejamento finito com uma quantidade finita de períodos entre os tempos inicial e final. Primeiramente consideramos uma versão determinística em que conhecemos, à priori, os itens solicitados em uma ordem de trabalho e o custo dos objetos a cada período. Algumas das sobras geradas durante o processo de corte dos itens solicitados em um período podem ser utilizadas como objetos no futuro. As sobras que podem ser usadas no futuro são denominadas sobras aproveitáveis. De forma geral, uma sobra é considerada aproveitável se possui dimensões iguais ou superiores as de algum item de uma lista pré-definida para o período. O objetivo é minimizar o custo total dos objetos utilizados para satisfazer a ordem de trabalho dos itens solicitados de todo o horizonte considerado. Havendo soluções com o mesmo custo, desejamos encontrar aquela que, no fim do horizonte de tempo considerado, maximize o valor das sobras aproveitáveis remanescentes. Apresentamos uma modelagem matemática do problema usando uma formulação em dois níveis, que é transformada em um modelo de programação linear inteira mista, devido às características do problema. Considerando a dificuldade em resolver o modelo desenvolvido, apresentamos uma proposta de uma abordagem heurística baseada em Programação Dinâmica Aproximada (PDA) para lidar com o problema proposto. Outras opções baseadas em estratégias do tipo horizonte rolante e relax-and-fix também são consideradas. Consideramos também o cenário onde não conhecemos de antemão os itens da ordem de trabalho e o custo dos objetos, mas temos informações das distribuições de probabilidade de ambos. Nesse caso, apresentamos uma abordagem baseada em programação dinâmica aproximada para estimar a melhor estratégia a ser seguida em cada período. Comparamos os resultados obtidos pela PDA com os resultados encontrados por um método guloso. Em cenários adequados, os resultados mostram que a PDA consegue soluções superiores ao método guloso. / In this research, we study the multi-period two-dimensional cutting problem with usable leftover, which consists of cutting objects to produce a set of items. We assume a finite planning horizon with a finite amount of periods between the initial and final times. First we consider a deterministic version in which we know, a priori, the set of ordered items and the cost of the objects at each period. Some of the leftovers generated during the cutting process of the ordered items in a period may be used as objects in the future. The leftovers that can be used in the future are called usable leftovers. In general, a leftover is considered usable if it has dimensions equal to or greater than that of some item from a predefined list for the period. The goal is to minimize the total cost of the objects used to cut the set of ordered items of the entire considered horizon. If there are solutions with the same cost, we wish to find one that, at the end of the considered time horizon, maximizes the value of the remaining usable leftovers. We present a mathematical model of the problem using a bilevel formulation, which is transformed into a mixed integer linear programming model, due to the characteristics of the problem. Considering the difficulty in solving the developed model, we propose a heuristic approach based on approximate dynamic programming (ADP) to deal with the proposed problem. Other options based on the rolling horizon and relax-and-fix strategies are also considered. We also consider the scenario where we do not know in advance the set of ordered items and the cost of the objects, but we have information about the probability distributions of both. In this case, we present an approach based on approximate dynamic programming to estimate the best strategy to be followed at each period. We compared the results obtained by the ADP with the results found by a greedy method. In suitable scenarios, the results show that the ADP achieves superior solutions to the greedy method.

abstract: The use of Red Blood Cells (RBCs) is a pillar of modern health care. Annually, the lives of hundreds of thousands of patients are saved through ready access to safe, fresh, blood-type compatible RBCs. Worldwide, hospitals have the common goal to better utilize available blood units by maximizing patients served and reducing blood wastage. Managing blood is challenging because blood is perishable, its supply is stochastic and its demand pattern is highly uncertain. Additionally, RBCs are typed and patient compatibility is required. This research focuses on improving blood inventory management at the hospital level. It explores the importance of hospital characteristics, such as demand rate and blood-type distribution in supply and demand, for improving RBC inventory management. Available inventory models make simplifying assumptions; they tend to be general and do not utilize available data that could improve blood delivery. This dissertation develops useful and realistic models that incorporate data characterizing the hospital inventory position, distribution of blood types of donors and the population being served. The dissertation contributions can be grouped into three areas. First, simulations are used to characterize the benefits of demand forecasting. In addition to forecast accuracy, it shows that characteristics such as forecast horizon, the age of replenishment units, and the percentage of demand that is forecastable influence the benefits resulting from demand variability reduction. Second, it develops Markov decision models for improved allocation policies under emergency conditions, where only the units on the shelf are available for dispensing. In this situation the RBC perishability has no impact due to the short timeline for decision making. Improved location-specific policies are demonstrated via simulation models for two emergency event types: mass casualty events and pandemic influenza. Third, improved allocation policies under normal conditions are found using Markov decision models that incorporate temporal dynamics. In this case, hospitals receive replenishment and units age and outdate. The models are solved using Approximate Dynamic Programming with model-free approximate policy iteration, using machine learning algorithms to approximate value or policy functions. These are the first stock- and age-dependent allocation policies that engage substitution between blood type groups to improve inventory performance. / Dissertation/Thesis / Doctoral Dissertation Industrial Engineering 2020

No description available.

Dans les études sur le transport, les modèles de choix de route décrivent la sélection par un utilisateur d’un chemin, depuis son origine jusqu’à sa destination. Plus précisément, il s’agit de trouver dans un réseau composé d’arcs et de sommets la suite d’arcs reliant deux sommets, suivant des critères donnés. Nous considérons dans le présent travail l’application de la programmation dynamique pour représenter le processus de choix, en considérant le choix d’un chemin comme une séquence de choix d’arcs. De plus, nous mettons en œuvre les techniques d’approximation en programmation dynamique afin de représenter la connaissance imparfaite de l’état réseau, en particulier pour les arcs éloignés du point actuel. Plus précisément, à chaque fois qu’un utilisateur atteint une intersection, il considère l’utilité d’un certain nombre d’arcs futurs, puis une estimation est faite pour le restant du chemin jusqu’à la destination. Le modèle de choix de route est implanté dans le cadre d’un modèle de simulation de trafic par événements discrets. Le modèle ainsi construit est testé sur un modèle de réseau routier réel afin d’étudier sa performance. / In transportation modeling, a route choice is a model describing the selection of a route between a given origin and a given destination. More specifically, it consists of determining the sequence of arcs leading to the destination in a network composed of vertices and arcs, according to some selection criteria. We propose a novel route choice model, based on approximate dynamic programming. The technique is applied sequentially, as every time a user reaches an intersection, he/she is supposed to consider the utility of a certain number of future arcs, followed by an approximation for the rest of the path leading up to the destination. The route choice model is implemented as a component of a traffic simulation model, in a discrete event framework. We conduct a numerical experiment on a real traffic network model in order to analyze its performance.

La régulation adaptative des feux de signalisation est un problème très important. Beaucoup de chercheurs travaillent continuellement afin de résoudre les problémes liés à l’embouteillage dans les intersections urbaines. Il devient par conséquent très utile d’employer des algorithmes intelligents afin d’améliorer les performances de régulation et la qualité du service. Dans cette thèse, nous essayons d'étudier ce problème d’une part à travers une modèlisation microscopique et dynamique en temps discret, et d’autre part en explorant plusieurs approches de résoltion pour une intersection isolée ainsi que pour un réseau distribué d'intersections.La première partie se concentre sur la modélisation dynamique des problèmes des feux de signalisation ainsi que de la charge du réseau d’intersections. Le mode de la “séquence de phase adaptative” (APS) dans un plan de feux est d'abord considéré. Quant à la modélisation du contrôle des feux aux intersections, elle est formulée grâce à un processus décisionnel de markov (MDP). En particulier, la notion de “l'état du système accordable” est alors proposée pour la coordination du réseau de trafic. En outre, un nouveau modèle de “véhicule-suiveur” est proposé pour l'environnement de trafic. En se basant sur la modélisation proposée, les méthodes de contrôle des feux dans cette thèse comportent des algorithmes optimaux et quasi-optimaux. Deux algorithmes exacts de résolution basées sur la programmation dynamique (DP) sont alors étudiés et les résultats montrent certaines limites de cette solution DP surtout dans quelques cas complexes où l'espace d'états est assez important. En raison de l’importance du temps d’execution de l'algorithme DP et du manque d'information du modèle (notamment l’information exacte relative à l’arrivée des véhicules à l’intersection), nous avons opté pour un algorithme de programmation dynamique approximative (ADP). Enfin, un algorithme quasi-optimal utilisant l'ADP combinée à la méthode d’amélioration RLS-TD (λ) est choisi. Dans les simulations, en particulier avec l'intégration du mode de phase APS, l'algorithme proposé montre de bons résultats notamment en terme de performance et d'efficacité de calcul. / Adaptive traffic signal control is a decision making optimization problem. People address this crucial problem constantly in order to solve the traffic congestion at urban intersections. It is very popular to use intelligent algorithms to improve control performances, such as traffic delay. In the thesis, we try to study this problem comprehensively with a microscopic and dynamic model in discrete-time, and investigate the related algorithms both for isolated intersection and distributed network control. At first, we focus on dynamic modeling for adaptive traffic signal control and network loading problems. The proposed adaptive phase sequence (APS) mode is highlighted as one of the signal phase control mechanisms. As for the modeling of signal control at intersections, problems are fundamentally formulated by Markov decision process (MDP), especially the concept of tunable system state is proposed for the traffic network coordination. Moreover, a new vehicle-following model supports for the network loading environment.Based on the model, signal control methods in the thesis are studied by optimal and near-optimal algorithms in turn. Two exact DP algorithms are investigated and results show some limitations of DP solution when large state space appears in complex cases. Because of the computational burden and unknown model information in dynamic programming (DP), it is suggested to use an approximate dynamic programming (ADP). Finally, the online near-optimal algorithm using ADP with RLS-TD(λ) is confirmed. In simulation experiments, especially with the integration of APS, the proposed algorithm indicates a great advantage in performance measures and computation efficiency.