This paper aims to present the thesis developed in the Doctoral Programin Computer Science and Computational Mathematics of the ICMC/USP. The thesis theme seeks to advance the state of the art by solving the problems of scalability and representation present in mission planning algorithms for Unmanned Aerial Vehicle (UAV). Techniques based on mathematical programming and evolutionary computation are proposed. Articles have been published, submitted or they are in final stages of preparation.These studies report the most significant advances in the representation and scalability of this problem. Mission planners worked on the thesis deal with stochastic problems in non-convex environments,where collision risks or failures in mission planning are treated and limited to a tolerated value. The advances in the representation allowed to solve violations in the risks present in the original literature modeling, besides making the models more realistic when incorporating aspects such as effects of the air resistance. Efficient mathematical modeling techniques allowed to advance from a Mixed Integer Nonlinear Programming (MINLP) model, originally proposed in the literature, to a Mixed Integer Linear Programming (MILP) problem. Modeling as a MILP led to problem solving more efficiently through the branch-and-algorithm. The proposed new representations resulted in improvements from scalability, solving more complex problems within a shorter computational time. In addition, advances in scalability are even more effective when techniques combining mathematical programming and metaheuristics have been applied to the problem. / O presente documento tem por objetivo apresentar a tese desenvolvida no Programade Doutorado em Ciência da Computação e Matemática Computacional do ICMC/USP. O tema da tese busca avançar o estado da arte ao resolver os problemas de escalabilidade e representação presentes em algoritmos de planejamento para missões com Veículos Aéreos Não Tripulados (VANTs). Técnicas baseadas em programação matemática e computação evolutiva são propostas. Artigos foram publicados, submetidos ou se encontram em fase final de elaboração. Esses trabalhos reportamos avanços mais significativos obtidos na representação e escalabilidade deste problema.Os planejadores de missão trabalhados na tese lidam com problemas estocásticos em ambientes não convexos, onde os riscos de colisão ou falhas no planejamento da missão são tratados e limitados a um valor tolerado. Os avanços na representação permitiram solucionar violações nos riscos presentes na modelagem original, além de tornar os modelos mais realistas ao incorporar aspectos como efeitos da resistência do ar. Para isso, técnicas eficientes de modelagem matemática permitiram avançar de um modelo de Programação Não-Linear Inteira Mista(PNLIM), originalmente proposto na literatura, para um problema de Programação Linear Inteira Mista (PLIM). A modelagem como um PLIM levou à resolução do problema de forma mais eficiente através do algoritmo branch-and-cut. As novas representações propostas resultaram em melhorias na escalabilidade, solucionando problemas mais complexos em um tempo computacional menor.Além disso,os avanços em escalabilidade mostraram-se mais efetivos quando técnicas combinando programação matemática e metaheurísticas foram aplicadas ao problema.

In this research, the focus is on improving a designer's capability to determine near-optimal sizes of components for a given system architecture. Component sizing is a hard problem to solve because of the presence of competing objectives, requirements from multiple disciplines, and the need for finding a solution quickly for the architecture being considered. In current approaches, designers rely on heuristics and iterate over the multiple objectives and requirements until a satisfactory solution is found. To improve on this state of practice, this research introduces advances in the following two areas: a.) Formulating a component sizing problem in a manner that is convenient to designers and b.) Solving the component sizing problem in an efficient manner so that all of the imposed requirements are satisfied simultaneously and the solution obtained is mathematically optimal. In particular, an acausal, algebraic, equation-based, declarative modeling approach is taken to solve component sizing problems efficiently. This is because global optimization algorithms exist for algebraic models and the computation time is considerably less as compared to the optimization of dynamic simulations. In this thesis, the mathematical programming language known as GAMS (General Algebraic Modeling System) and its associated global optimization solvers are used to solve component sizing problems efficiently. Mathematical programming languages such as GAMS are not convenient for formulating component sizing problems and therefore the Systems Modeling Language developed by the Object Management Group (OMG SysML ) is used to formally capture and organize models related to component sizing into libraries that can be reused to compose new models quickly by connecting them together. Model-transformations are then used to generate low-level mathematical programming models in GAMS that can be solved using commercial off-the-shelf solvers such as BARON (Branch and Reduce Optimization Navigator) to determine the component sizes that satisfy the requirements and objectives imposed on the system. This framework is illustrated by applying it to an example application for sizing a hydraulic log splitter.

By the emergence of electronic commerce and low transaction costs on the Internet, an interest in the design of new auction mechanisms has been arisen. Recently many researchers in computer science, economics, business, and game theory have presented many valuable studies on the subject of online auctions, and auctions theory. When faced from a computational perspective, combinatorial auctions are perhaps the most challenging ones. Combinatorial auctions, that is, auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auction mechanisms in multi-item multi-unit situations where the agents&rsquo / valuations of the items are not additive. However, determining the winners to maximize the revenue is NP-complete. In this study, we first analyze the existing approaches for combinatorial auction problem. Based on this analysis, we then choose three different approaches, which are search approach, descending simultaneous auctions approach, and IP (Integer Programming) formulation approach to build our models. The performances of the models are compared using computer simulations, where we model bandwidth allocation system. Finally a combinatorial auction tool is built which can be used for online auctions and e-procurement systems.

The objective of this project is to develop an operational scheduling model for Sasol Mining’s coal handling facility, Sasol Coal Supply (referred to as SCS), to optimise daily operations. In this document, the specific scheduling problem at SCS is presented and solved using Mixed Integer Non-Linear Programming (MINLP) continuous time representation techniques. The most recent MINLP scheduling techniques are presented and applied to an example problem. The assumption is made that the results from the example problem will display trends which will apply to the SCS scheduling problem as well. Based on this assumption, the unit-specific event based continuous time formulation is chosen to apply to the SCS scheduling problem. The detail mathematical formulation of the SCS scheduling problem, based on the chosen technique, is discussed and the necessary changes presented to customise the formulation for the SCS situation. The results presented show that the first phase model does not solve within 72 hours. A solution time of more than three days is not acceptable for an operational scheduling model in a dynamic system like SCS. Various improvement approaches are applied during the second phase of the model development. Special Ordered Sets of Type 1 (SOS1) variables are successfully applied in the model to reduce the amount of binary variables. The time and duration constraints are restructured to simplify the structure of the model. A specific linearization and solution technique is applied to the non-linear equations to ensure reduced model solution times and reliable results. The improved model for one period solves to optimality within two minutes. This dramatic improvement ensures that the model will be used operationally at SCS to optimise daily operations. The scheduling model is currently being implemented at SCS. Examples of the input variables and output results are presented. It is concluded that the unit-specific event based MINLP continuous time formulation method, as presented in the literature, is not robust enough to be applied to an operational industrial-sized scheduling problem such as the SCS problem. Customised modifications to the formulation are necessary to ensure that the model solves in a time acceptable for operational use. However, it is proved that Mixed Integer Non-linear Programming (MINLP) can successfully be applied to optimise the scheduling of an industrial-sized plant such as SCS. Although more research is required to derive robust formulation techniques, the principle of using mathematical methods to optimise operational scheduling in industry can dramatically impact the way plants are operated. The optimisation of daily schedules at SCS by applying the MINLP continuous time scheduling technique, has made a significant contribution to the coal handling industry. Finally, it can be concluded that the SCS scheduling problem was successfully modelled and the operational scheduling model will add significant value to the Sasol Group. / Dissertation (MEng (Industrial Engineering))--University of Pretoria, 2006. / Industrial and Systems Engineering / unrestricted

This paper aims to present the thesis developed in the Doctoral Programin Computer Science and Computational Mathematics of the ICMC/USP. The thesis theme seeks to advance the state of the art by solving the problems of scalability and representation present in mission planning algorithms for Unmanned Aerial Vehicle (UAV). Techniques based on mathematical programming and evolutionary computation are proposed. Articles have been published, submitted or they are in final stages of preparation.These studies report the most significant advances in the representation and scalability of this problem. Mission planners worked on the thesis deal with stochastic problems in non-convex environments,where collision risks or failures in mission planning are treated and limited to a tolerated value. The advances in the representation allowed to solve violations in the risks present in the original literature modeling, besides making the models more realistic when incorporating aspects such as effects of the air resistance. Efficient mathematical modeling techniques allowed to advance from a Mixed Integer Nonlinear Programming (MINLP) model, originally proposed in the literature, to a Mixed Integer Linear Programming (MILP) problem. Modeling as a MILP led to problem solving more efficiently through the branch-and-algorithm. The proposed new representations resulted in improvements from scalability, solving more complex problems within a shorter computational time. In addition, advances in scalability are even more effective when techniques combining mathematical programming and metaheuristics have been applied to the problem. / O presente documento tem por objetivo apresentar a tese desenvolvida no Programade Doutorado em Ciência da Computação e Matemática Computacional do ICMC/USP. O tema da tese busca avançar o estado da arte ao resolver os problemas de escalabilidade e representação presentes em algoritmos de planejamento para missões com Veículos Aéreos Não Tripulados (VANTs). Técnicas baseadas em programação matemática e computação evolutiva são propostas. Artigos foram publicados, submetidos ou se encontram em fase final de elaboração. Esses trabalhos reportamos avanços mais significativos obtidos na representação e escalabilidade deste problema.Os planejadores de missão trabalhados na tese lidam com problemas estocásticos em ambientes não convexos, onde os riscos de colisão ou falhas no planejamento da missão são tratados e limitados a um valor tolerado. Os avanços na representação permitiram solucionar violações nos riscos presentes na modelagem original, além de tornar os modelos mais realistas ao incorporar aspectos como efeitos da resistência do ar. Para isso, técnicas eficientes de modelagem matemática permitiram avançar de um modelo de Programação Não-Linear Inteira Mista(PNLIM), originalmente proposto na literatura, para um problema de Programação Linear Inteira Mista (PLIM). A modelagem como um PLIM levou à resolução do problema de forma mais eficiente através do algoritmo branch-and-cut. As novas representações propostas resultaram em melhorias na escalabilidade, solucionando problemas mais complexos em um tempo computacional menor.Além disso,os avanços em escalabilidade mostraram-se mais efetivos quando técnicas combinando programação matemática e metaheurísticas foram aplicadas ao problema.

L’objectif de ces travaux est de développer une méthode d’aide à la conception des réseaux de chaleur urbains (RCU). Cette méthode utilise un modèle de type MINLP (Mixed Integer Non Linear Programming) pour l’optimisation simultanée de la configuration et du dimensionnement d’un RCU. Aux variables continues pour l’aide au dimensionnement (température, vitesse, diamètre, aire des échangeurs), s’ajoutent des variables binaires aidant à définir la configuration du réseau (maillage et choix des technologies). La fonction objectif à minimiser est le coût total (capex et opex), qui est soumise à un ensemble de contraintes non linéaires (p. ex. pertes thermiques et de charge, bilans). La méthode développée dans ce manuscrit offre la possibilité de connecter en cascade des consommateurs n’ayant pas les mêmes besoins en température, et de réaliser des réseaux bouclés (une canalisation par tranchée). Elle permet aussi de choisir : les consommateurs à connecter au RCU, le ou les sites de production ainsi que le type de technologie utilisée. Enfin la bonne prise en compte de la physique permet de choisir le meilleur compromis entre pertes thermiques et pertes de charge, sur une large gamme de température. Cette formulation permet donc d’optimiser des réseaux de 4éme génération et de démontrer la rentabilité de l’intégration d’EnR&R sur le long terme (30 ans). Un premier travail est réalisé afin de proposer une méthodologie de résolution en plusieurs étapes permettant l’obtention de l’optimum global. Différents cas d’études académiques sont utilisés pour présenter les intérêts multiples de cette formulation. Enfin la comparaison avec un réseau existant a permis de démontrer la cohérence des résultats du modèle et a servi de base pour l’optimisation d’un cas d’étude de grande dimension. Plusieurs études de sensibilité post-optimale sont réalisées afin de démontrer l’intérêt de cet outil pour l’aide à la conception initiale ou l’extension de RCU existants. / The aim of this thesis is to develop a method that provides design assistance for District Heating Network (DHN). This tool allows simultaneously the optimization of the configuration and its sizing, thanks to an MINLP formulation (Mixed Integer Non-Linear Programming). Binary variables help to choose the optimal configuration (network layout and technologies of production), whereas continuous variables help DHN sizing (temperature, diameter, velocity, heat exchanger area, thermal generating capacity …). The objective function to minimize is the total cost (capex and opex), subjected to numerous nonlinear constraints (e.g. thermal losses, pressure drop, energy balance).This method enables to design temperature cascade between consumers, when consumer temperature requirements are different, and also looped network (only one pipe in one trench). It helps also the decision to connect (or not) consumers to the main network and also the location(s) and type(s) of the heating plant. Moreover, the arbitrage between heat losses and pressure drops is taken into account thanks to physical considerations (non-linear equations). Eventually, it is possible to design 4th generation DHN and prove their financial profitability over the long terms (30 years). First a multi-step resolution strategy is proposed to ensure finding global optimum of the complex MINLP problem. Then academic study cases are analyzed to underline the numerous assets of the formulation. Finally, the optimal design compared to an existing DHN ensures the consistency of the method and allows to build a study case at a wider scale, which can be solved thanks to the comprehensive strategy developed. The design assistance method is available for initial design as well as for extension of existing DHN.