The application offloading problem for Mobile Cloud Computing aims at improving the mobile user experience by leveraging the resources of the cloud. The execution of the mobile application is offloaded to the cloud, saving energy at the mobile device or speeding up the execution of the application. We improve the accuracy and performance of application offloading solutions in three main directions. First, we propose a novel fine-grained application model that supports complex module dependencies such as sequential, conditional and parallel module executions. The model also allows for multiple offloading decisions that are tailored towards the current application, network, or user contexts. As a result, the model is more precise in capturing the structure of the application and supports more complex offloading solutions. Second, we propose three cost models, namely, average-based, statistics-based and interval-based cost models, defined for the proposed application model. The average-based approach models each module cost by the expected cost value, and the expected cost of the entire application is estimated considering each of the three module dependencies. The novel statistics-based cost model employs Cumulative Distribution Function (CDFs) to represent the costs of the modules and of the mobile application, which is estimated considering the cost and dependencies of the modules. This cost model opens the doors for new statistics-based optimization functions and constraints whereas the state of the art only support optimizations based on the average running cost of the application. Furthermore, this cost model can be used to perform statistical analysis of the performance of the application in different scenarios such as varying network data rates. The last cost model, the interval-based, represents the module costs via intervals in order to addresses the cost uncertainty while having lower requirements and computational complexity than the statistics-based model. The cost of the application is estimated as an expected maximum cost via a linear optimization function. Finally, we present offloading decision algorithms for each cost model. For the average-based model, we present a fast optimal dynamic programming algorithm. For the statistics-based model, we present another fast optimal dynamic programming algorithm for the scenario where the optimization function meets specific properties. Finally, for the interval-based cost model, we present a robust formulation that solves a linear number of linear optimization problems. Our evaluations verify the accuracy of the models and show higher cost savings for our solutions when compared to the state of the art.

O problema abordado nesta pesquisa consiste na distribuição de água em redes urbanas para o atendimento de demandas conhecidas, com o objetivo de minimizar o custo da energia elétrica necessária para o funcionamento de bombas hidráulicas. As bombas hidráulicas são utilizadas para captar água de poços artesianos ou estações de tratamento de água para abastecer reservatários distribuídos por bairros de uma cidade, de onde a população será atendida por força gravitacional. Como o custo da energia elétrica varia ao longo do dia, se faz necessário um planejamento do funcionamento das bombas para que não sejam ligadas nos horários em que a energia elétrica é mais cara. O problema de planejamento de estoque de água em reservatórios (PPEAR) consiste em decidir em quais períodos ou frações dos períodos do horizonte de planejamento as bombas hidráulicas que abastecem os reservatórios devem permanecer ligadas e em quais períodos ou frações dos períodos deve haver transporte de água entre os reservatórios para que a demanda de cada reservatório seja atendida em cada período e sejam respeitados os níveis mínimos e máximos de água nos reservatórios. Uma solução heurística para resolver o PPEAR é proposta e analisada por comparação com as soluções obtidas pelo método de enumeração implícita. Resultados computacionais comprovam a eficiência da abordagem, tanto pela qualidade das soluções como pelo baixo tempo de resposta / The problem focused in this study consists of reducing the eletrical energy cost necessary to the operation of hydraulic pumps. The hydraulic pumps are used to catch water from artesians wells or Water Treatment Station to supply tanks which are located in districts in a city, from which the population will be supplied by gravitational force. As the cost of electrical energy varies along the day, a schedule of the pumps run is necessary to avoid that they are not turned in the periods when the energy cost is more expensive. The problem of water stock schedule in tanks (WSST) consists of deciding in which periods or parts of them of the horizon planning the hydraulic pumps have to put on, and in which periods or parts of them should transfer water among the tanks so that the demand of each tank is met for each period and lower and upper limits of water shouldn\'t be violated. A heuristic solution is proposed and analyzed by comparing its solutions with the solutions obtained by the branch and bound method. Computational experiments show the efficiency of the heuristic

La chaine d’approvisionnement énergétique a fortement évolué aux cours des 20 dernières années. La libéralisation des marchés de l’électricité et les nouvelles technologies ont fortement influencé la manière d’envisager la production et la transmission d’électricité. Les modèles mathématiques classiques utilisés dans les problèmes lié à l’énergie ont besoin d’être revus pour intégrer les contraintes pratiques modernes.Un problème classique pour un Compagnie Génératrice (CG) est le problème de Unit Commitment (UC) qui consiste à établir un plan de production pour une demande en électricité connue. Lorsque ce problème fut considéré, le prix de l’électricité et la demande étaient relativement simple à estimer comme une seule CG nationale avait le monopole du marché. Ce problème a été étudié de manière extensive en utilisant de la Programmation Mathématique (PM). Aujourd’hui, le prix de l’électricité est relativement volatile à cause de l’introduction de marchés dérégulés et la demande du marché est répartie entre plusieurs CGs en compétition sur divers marchés. Une CG ne peut se limiter à considérer un problème de UC seul pour envisager sa production. Il y a un besoin d’intégrer les incertitudes liées au marché de l’électricité et aux quantités à produire aux modèles utilisés pour qu’une CG puisse établir un plan de production rentable.La technologie a aussi permis d’envisager de nouveaux concept tel que les Micro-Grilles (MGs). Une MG est composée d’un ensemble de consommateurs reliés à travers un réseau de transmission, possédant des générateurs d’électricité et optimisant leur consommation interne. Ce concept est possible grâce à l’utilisation croissante d’énergies renouvelables locales ainsi que l’utilisant croissante d’appareils interconnectés. Cependant, étant donné que les énergies renouvelables ont un faible rendement, sont intermittentes et que les appareils de stockage d’énergie sont encore peu efficaces, les MGs ne peuvent pas envisager d’être pleinement autonome en électricité. Il y a donc une nécessité d’avoir un fournisseur d’électricité externe pour avoir suffisamment d’électricité disponible à tout moment. Une CG jouant le rôle de fournisseur auprès d’une MG fait face énormément d’incertitude concernant la demande à cause de la gestion interne de la MG sur laquelle elle n’a pas de contrôle.Dans cette thèse, des problèmes d’optimisation intégrant de nouvelles contraintes modernes liés à l’approvisionnement énergétique sont étudiés via la PM. Plusieurs problèmes considèrant des interactions entre plusieurs acteurs sont modélisés via des formulations bi-niveau. Nous illustrons comment les difficultés liées aux contraintes modernes peuvent être exploitées pour obtenir des propriétés permettant de reformuler les problèmes étudiés en formulation linéaire en nombre entiers. Des heuristiques performantes sont obtenus à partir des formulations exactes dont certaines sont applicables à des problèmes plus généraux. Une analyse extensive de la performance des méthodes de résolution ainsi que de l’influence des contraintes modernes sont présentées dans diverses expériences numériques. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

A multi-commodity flow problem consists of moving several commodities from their respective sources to their sinks through a network where each edge has different costs and capacity constraints. This paper explores different linear programming algorithms and their performance regarding finding an optimal solution for multi-commodity flow problems. By testing several of different network constraints, we examine which algorithms are most suitable for specific network and problem structures. Furthermore, we implement our own multi-commodity solver and compare its performance against state-of-the-art linear programming solvers. The results show that for the methods we tested it is difficult to discern which class of linear programming methods are optimal solvers for multi-commodity flow problems and that their performance depends on how the network and commodities are structured.

No description available.

No description available.

Student Number : 0214677F - PhD thesis - School of Camputational and Applied Mathematics - Faculty of Science / Many real-life problems are formulated as global optimization problems with continuous variables. These problems are in most cases nonsmooth, nonconvex and often simulation based, making gradient based methods impossible to be used to solve them. Therefore, ef#2;cient, reliable and derivative-free global optimization methods for solving such problems are needed. In this thesis, we focus on improving the ef#2;ciency and reliability of some global optimization methods. In particular, we concentrate on improving some population set-based methods for unconstrained global optimization, mainly through hybridization. Hybridization has widely been recognized to be one of the most attractive areas of unconstrained global optimization. Experiments have shown that through hybridization, new methods that inherit the strength of the original elements but not their weakness can be formed. We suggest a number of new hybridized population set-based methods based on differential evolution (de), controlled random search (crs2) and real coded genetic algorithm (ga). We propose #2;ve new versions of de. In the #2;rst version, we introduce a localization, called random localization, in the mutation phase of de. In the second version, we propose a localization in the acceptance phase of de. In the third version, we form a de hybrid algorithm by probabilistically combining the point generation scheme of crs2 with that of de in the de algorithm. The fourth and #2;fth versions are also de hybrids. These versions hybridize the mutation of de with the point generation rule of the electromagnetism-like (em) algorithm. We also propose #2;ve new versions of crs2. The #2;rst version modi#2;es the point generation scheme of crs2 by introducing a local mutation technique. In the second and third modi#2;cations, we probabilistically combine the point generation scheme of crs2 with the linear interpolation scheme of a trust-region based method. The fourth version is a crs hybrid that probabilistically combines the quadratic interpolation scheme with the linear interpolation scheme in crs2. In the #2;fth version, we form a crs2 hybrid algorithm by probabilistically combining the point generation scheme of crs2 with that of de in the crs2 algorithm. Finally, we propose #2;ve new versions of the real coded genetic algorithm (ga) with arithmetic crossover. In the #2;rst version of ga, we introduce a local technique. We propose, in the second version, an integrated crossover rule that generates two children at a time using two different crossover rules. We introduce a local technique in the second version to obtain the third version. The fourth and #2;fth versions are based on the probabilistic adaptation of crossover rules. The ef#2;ciency and reliability of the new methods are evaluated through numerical experiments using a large test suite of both simple and dif#2;cult problems from the literature. Results indicate that the new hybrids are much better than their original counterparts both in reliability and ef#2;ciency. Therefore, the new hybrids proposed in this study offer an alternative to many currently available stochastic algorithms for solving global optimization problems in which the gradient information is not readily available.

Este trabalho tem como objetivo principal o desenvolvimento de uma estratégia de integração da otimização com o controle preditivo multivariável em uma camada. Os problemas de controle e otimização econômica são resolvidos simultaneamente em um mesmo algoritmo. A função objetivo econômica foi inserida no controlador na sua forma diferencial, ou seja, o gradiente da função objetivo econômica. O método foi testado por simulação para o caso do sistema reator regenerador da UFCC (Unit of Fluid Catalytic Cracker). Esta dissertação descreve a estratégia de otimização integrada ao controlador preditivo cuja função objetivo incorpora componentes dinâmicos e estáticos. Para a determinação das condições ótimas do processo no estado estacionário do conversor (unidade de craqueamento catalítico) foi utilizado um modelo empírico do processo. A melhor trajetória para conduzir o processo para o seu ponto ótimo de operação, maximizando lucro ou produto de maior valor agregado, desde que não sejam violadas as restrições de processo, é predita utilizando um modelo dinâmico, obtido através de dados de testes em degrau em um modelo rigoroso. Este modelo linear possibilitou a obtenção das funções de transferência do processo e o modelo em variáveis de estado. O ponto ótimo que é obtido na execução deste algoritmo, leva em consideração a não violação das restrições das variáveis manipuladas e controladas do processo, tanto para o estado estacionário como para o transiente do problema. O problema de otimização não linear resultante é resolvido através de uma rotina de programação quadrática da biblioteca do Matlab. Uma segunda alternativa apresentada para a estratégia de otimização deste trabalho, é a inclusão do gradiente reduzido na função objetivo do controlador quando são observadas violações das restrições das variáveis controladas. Os resultados simulados através de um modelo não linear rigoroso (Moro&Odloak,1995) mostram um bom desempenho dos algoritmos aqui desenvolvidos tanto com relação aos benefícios econômicos como na estabilização da unidade. / This dissertation aims to develop a strategy to integrate the optimization problem of the plant into the model predictive controller in a one layer strategy, for the real time optimization or online optimization. The control and the optimization of the process are computed simultaneously in the same algorithm. The gradient of the economic objective function is included in the cost function of the controller instead of in its regular form. Thereby, this work describes a predictive control strategy, which can be classified as a one layer strategy and whose objective function has to be optimized obeying constraints, which incorporates dynamic and static components. The optimal conditions of the process in the steady state are defined through the use of an empirical process model. Furthermore, the best trajectory to be followed in order to reach the optimal conditions, without violating the constraints, maximizing profit or the production of its more valuable product, is predicted through the use of the dynamic model, that can be obtained through a plant step test. As a result transfer function and state space models are obtained. The optimal operation point is achieved through the execution of the proposed algorithm. Therefore, the solution to the optimization/control problem will always be in a feasible region, in other words, without violating the process manipulated or controlled variable constraints for both stationary and transient states of the problem. The non-linear optimization problem resulted from the implementation of the proposed algorithm is solved through the quadratic programming routine from the Matlab library. The second online optimization strategy proposed in this work is one that considers the reduced gradient method algorithm modified to evaluate the predicted trajectory. As a result, any violation of the manipulated or controlled variable constraints is prevented and this variable is not considered in the next step of the calculation of the predicted trajectory or even in the search direction of the optimization. Finally the simulations results obtained through the use of a nonlinear rigorous model (Moro&Odloak,1995) presents good performance for the algorithms here proposed, not only related to economic benefits, but also in order to stabilize the unit.

Linear optimization tools are used to solve many problems that arise in our day-to-day lives. The linear optimization models and methodologies help to find, for example, the best amount of ingredients in our food, the most suitable routes and timetables for the buses and trains we take, and the right way to invest our savings. We would cite many other situations that involves linear optimization, since a large number of companies around the world base their decisions in solutions which are provided by the linear optimization methodologies. In this thesis, we propose theoretical and computational developments to improve the performance of important linear optimization methods. Namely, we address simplex type methods, interior point methods, the column generation technique and the branch-and-price method. In simplex-type methods, we investigate a variant which exploits special features of problems which are formulated in the general form. We present a novel theoretical description of the method and propose how to efficiently implement this method in practice. Furthermore, we propose how to use the primal-dual interior point method to improve the column generation technique. This results in the primal-dual column generation method, which is more stable in practice and has a better overall performance in relation to other column generation strategies. The primal-dual interior point method also oers advantageous features which can be exploited in the context of the branch-and-price method. We show that these features improves the branching operation and the generation of columns and valid inequalities. For all the strategies which are proposed in this thesis, we present the results of computational experiments which involves publicly available, well-known instances from the literature. The results indicate that these strategies help to improve the performance of the linear optimization methodologies. In particular for a class of problems, namely the vehicle routing problem with time windows, the interior point branch-and-price method proposed in this study was up to 33 times faster than a state-of-the-art implementation available in the literature / Ferramentas de otimização linear são usadas para resolver diversos problemas do nosso dia-a- dia. Os modelos e as metodologias de otimização linear ajudam a obter, por exemplo, a melhor quantidade de ingredientes na nossa alimentação, os horários e as rotas de ônibus e trens que tomamos, e a maneira certa para investir nossas economias. Muitas outras situações que envolvem otimização linear poderiam ser aqui citadas, já que um grande número de empresas em todo o mundo baseia suas decisões em soluções obtidas pelos métodos de otimização linear. Nesta tese, são propostos desenvolvimentos teóricos e computacionais para melhorar o desempenho de métodos de otimização linear. Em particular, serão abordados métodos tipo simplex, métodos de pontos interiores, a técnica de geração de colunas e o método branch-and-price. Em métodos tipo simplex, é investigada uma variante que explora as características especiais de problemas formulados na forma geral. Uma nova descrição teórica do método é apresentada e, também, são propostas técnicas computacionais para a implementação eciente do método. Além disso, propõe-se como utilizar o método primal-dual de pontos interiores para melhorar a técnica de geração de colunas. Isto resulta no método primal-dual de geração de colunas, que é mais estável na prática e tem melhor desempenho geral em relação a outras estratégias de geração de colunas. O método primal-dual de pontos interiores também oferece características vantajosas que podem ser exploradas em conjunto com o método branch-and-price. De acordo com a investigação realizada, estas características melhoram a operação de ramificação e a geração de colunas e de desigualdades válidas. Para todas as estratégias propostas neste trabalho, são apresentados os resultados de experimentos computacionais envolvendo problemas de teste bem conhecidos e disponíveis publicamente. Os resultados indicam que as estratégias propostas ajudam a melhorar o desempenho das metodologias de otimização linear. Em particular para uma classe de problemas, o problema de roteamento de veículos com janelas de tempo, o método branch-and-price de pontos interiores proposto neste estudo foi até 33 vezes mais rápido que uma implementação estado-da-arte disponível na literatura

Em diversas indústrias de manufatura (por exemplo, papeleira, moveleira, metalúrgica, têxtil) as decisões do dimensionamento de lotes interagem com outras decisões do planejamento e programação da produção, tais como, a distribuição, o processo de corte, entre outros. Porém, usualmente, essas decisões são tratadas de forma isolada, reduzindo o espaço de soluções e a interdependência entre as decisões, elevando assim os custos totais. Nesta tese, estudamos o processo produtivo de indústrias de móveis de pequeno porte, que consiste em cortar placas grandes disponíveis em estoque para obter diversos tipos de peças que são processadas posteriormente em outros estágios e equipamentos com capacidades limitadas para, finalmente, comporem os produtos demandados. Os problemas de dimensionamento de lotes e corte de estoque são acoplados em um modelo de otimização linear inteiro cujo objetivo é minimizar os custos de produção, estoque de produtos, preparação de máquinas e perda de matéria-prima. Esse modelo mostra o compromisso existente entre antecipar ou não a fabricação de certos produtos aumentando os custos de estoque, mas reduzindo a perda de matéria-prima ao obter melhores combinações entre as peças. O impacto da incerteza da demanda (composta pela carteira de pedidos e mais uma quantidade extra estimada) foi amortizado pela estratégia de horizonte de planejamento rolante e por variáveis de decisão que representam uma produção extra para a demanda esperada no melhor momento, visando a minimização dos custos totais. Dois métodos heurísticos são desenvolvidos para resolver uma simplificação do modelo matemático proposto, o qual possui um alto grau de complexidade. Os experimentos computacionais realizados com exemplares gerados a partir de dados reais coletados em uma indústria de móveis de pequeno porte, uma análise dos resultados, as conclusões e perspectivas para este trabalho são apresentados / In the many manufacturing industries (e.g., paper industry, furniture, steel, textile), lot-sizing decisions generally arise together with other decisions of planning production, such as distribution, cutting, scheduling and others. However, usually, these decisions are dealt with separately, which reduce the solution space and break dependence on decisions, increasing the total costs. In this thesis, we study the production process that arises in small scale furniture industries, which consists basically of cutting large plates available in stock into several thicknesses to obtain different types of pieces required to manufacture lots of ordered products. The cutting and drilling machines are possibly bottlenecks and their capacities have to be taken into account. The lot-sizing and cutting stock problems are coupled with each other in a large scale linear integer optimization model, whose objective function consists in minimizing different costs simultaneously, production, inventory, raw material waste and setup costs. The proposed model captures the tradeoff between making inventory and reducing losses. The impact of the uncertainty of the demand, which is composed with ordered and forecasting products) was smoothed down by a rolling horizon strategy and by new decision variables that represent extra production to meet forecasting demands at the best moment, aiming at total cost minimization. Two heuristic methods are proposed to solve relaxation of the mathematical model. Randomly generated instances based on real world life data were used for the computational experiments for empirical analyses of the model and the proposed solution methods