[pt] Otimização Robusta é uma das formas mais comuns de considerar in- certeza nos parâmetros de um problema de otimização. A forma tradicional de achar soluções robustas consiste em resolver a contraparte robusta de um problema, o que em muitos casos, na prática, pode ter um custo computacional proibitivo. Neste trabalho, estudamos métodos iterativos para resolver problemas de Otimização Convexa Robusta de forma aproximada, que não exigem a formulação da contraparte robusta. Utilizamos conceitos de Online Learning para propor um novo algoritmo que utiliza agregação de restrições, demonstrando garantias teóricas de convergência. Desenvolvemos ainda uma modificação deste algoritmo que, apesar de não possuir tais garantias, obtém melhor performance prática. Por fim, implementamos outros métodos iterativos conhecidos da literatura de Otimização Robusta e fazemos uma análise computacional de seus desempenhos. / [en] Robust Optimization is a common paradigm to consider uncertainty in the parameters of an optimization problem. The traditional way to find robust solutions requires solving the robust counterpart of an optimiza- tion problem, which, in practice, can often be prohibitively costly. In this work, we study iterative methods to approximately solve Robust Convex Optimization problems, which do not require solving the robust counter- part. We use concepts from the Online Learning framework to propose a new algorithm that performs constraint aggregation, and we demonstrate theoretical convergence guarantees. We then develop a modification of this algorithm that, although without such guarantees, obtains better practical performance. Finally, we implement other classical iterative methods from the Robust Optimization literature and present a computational study of their performances.

[pt] A indústria de transporte marítimo é essencial para o comércio internacional. No entanto, no despertar da crise financeira de 2008, essa indústria foi severamente atingida. Nessas ocasiões, empresas de transporte só são capazes de obter lucro se suas frotas forem roteadas de forma eficaz. Neste trabalho, nós estudamos uma classe de problemas de roteamento de navios relacionados ao Pickup and Delivery Problem with Time Windows. Para resolver esses problemas, nós introduzimos um método heurístico e um exato. O método heurístico é uma meta-heurística híbrida com uma vizinhança larga baseada em set partitioning, enquanto o método exato é um algoritmo de branch-and-price. Nós conduzimos experimentos em um conjunto de instâncias baseadas em rotas de navios reais. Os resultados obtidos mostram que nossos algoritmos superam as metodologias estado da arte. Em seguida, nós adaptamos o conjunto de instâncias para modelar um problema de roteamento de navios no qual a velocidade em cada segmento de rota é uma variável de decisão, e o consumo de combustível por unidade de tempo é uma função convexa da velocidade e carga do navio. A fim de resolver esse novo problema de roteamento de navios com otimização de velocidade, nós estendemos nossa meta-heurística para encontrar decisões de velocidade ótimas em toda avaliação de solução vizinha de uma busca local. Nossos experimentos demonstram que essa abordagem pode ser altamente rentável, e que requer apenas um aumento moderado de recursos computacionais. / [en] The shipping industry is essential for international trade. However, in the wake of the 2008 financial crisis, this industry was severely hit. In these times, transportation companies can only obtain profit if their fleet is routed effectively. In this work, we study a class of ship routing problems related to the Pickup and Delivery Problem with Time Windows. To solve these problems, we introduce a heuristic and an exact method. The heuristic method is a hybrid metaheuristic with a set-partitioning-based large neighborhood, while the exact method is a branch-and-price algorithm. We conduct experiments on a benchmark suite based on real-life shipping segments. The results obtained show that our algorithms largely outperform the state-of-the-art methodologies. Next, we adapt the benchmark suite to model a ship routing problem where the speed on each sailing leg is a decision variable, and fuel consumption per time unit is a convex function of the ship speed and payload. To solve this new ship routing problem with speed optimization, we extend our metaheuristic to find optimal speed decisions on every local search move evaluation. Our computational experiments demonstrate that such approach can be highly profitable, with only a moderate increase in computational effort.

[pt] As técnicas de programação genética permitem flexibilidade no processo de otimização, possibilitando sua aplicação em diferentes áreas do conhecimento e fornecendo novas maneiras para que especialistas avancem em suas áreas com mais rapidez. Parameter mapping approach é um método de otimização numérica que utiliza a programação genética para mapear valores iniciais em parâmetros ótimos para um sistema. Embora esta abordagem produza bons resultados para problemas com soluções triviais, o uso de grandes equações/árvores pode ser necessário para tornar este mapeamento apropriado em sistemas mais complexos.A fim de aumentar a flexibilidade e aplicabilidade do método a sistemas de diferentes níveis de complexidade, este trabalho introduz uma generalização utilizando a programação genética multigênica, para realizar um mapeamento multivariado, evitando grandes estruturas complexas. Foram considerados três conjuntos de funções de benchmark, variando em complexidade e dimensionalidade. Análises estatísticas foram realizadas, sugerindo que este novo método é mais flexível e mais eficiente (em média), considerando funções de benchmark complexas e de grande dimensionalidade. Esta tese também apresenta uma abordagem do novo algoritmo para otimização numérica multimodal.Este segundo algoritmo utiliza algumas técnicas de niching, baseadas no procedimento chamado de clearing, para manter a diversidade da população. Um conjunto benchmark de funções multimodais, com diferentes características e níveis de dificuldade,foi utilizado para avaliar esse novo algoritmo. A análise estatística sugeriu que esse novo método multimodal, que também utiliza programação genética multigênica,pode ser aplicado para problemas que requerem mais do que uma única solução. Como forma de testar esses métodos em problemas do mundo real, uma aplicação em nanotecnologia é proposta nesta tese: ao timização estrutural de fotodetectores de infravermelho de poços quânticos a partir de uma energia desejada. Os resultados apresentam novas estruturas melhores do que as conhecidas na literatura (melhoria de 59,09 por cento). / [en] Genetic programming techniques allow flexibility in the optimization process, making it possible to use them in different areas of knowledge and providing new ways for specialists to advance in their areas more quickly and more accurately.Parameter mapping approach is a numerical optimization method that uses genetic programming to find an appropriate mapping scheme among initial guesses to optimal parameters for a system. Although this approach yields good results for problems with trivial solutions, the use of large equations/trees may be required to make this mapping appropriate for more complex systems.In order to increase the flexibility and applicability of the method to systems of different levels of complexity, this thesis introduces a generalization by thus using multi-gene genetic programming to perform a multivariate mapping, avoiding large complex structures.Three sets of benchmark functions, varying in complexity and dimensionality, were considered. Statistical analyses carried out suggest that this new method is more flexible and performs better on average, considering challenging benchmark functions of increasing dimensionality.This thesis also presents an improvement of this new method for multimodal numerical optimization.This second algorithm uses some niching techniques based on the clearing procedure to maintain the population diversity. A multimodal benchmark set with different characteristics and difficulty levels to evaluate this new algorithm is used. Statistical analysis suggested that this new multimodal method using multi-gene genetic programming can be used for problems that requires more than a single solution. As a way of testing real-world problems for these methods, one application in nanotechnology is proposed in this thesis: the structural optimization of quantum well infrared photodetector from a desired energy.The results present new structures better than those known in the literature with improvement of 59.09 percent.

[pt] O planejamento e a gestão de atividades esportivas é uma área promissora e pouco explorada para aplicações de Pesquisa Operacional. Os problemas nesta área são em geral de formulação simples e alcançam grande difusão nos meios de comunicação. Embora sua formulação seja simples, em geral estes problemas são difíceis de serem resolvidos em termos computacionais. Os resultados de muitos trabalhos acadêmicos nesta área têm sido aceitos como soluções para problemas reais e várias soluções vem sendo implementadas na prática. Esta tese tem como objetivo principal estudar dois tipos de problemas que surgem na área de esportes: a programação de tabelas e os problemas da classificação. A programação de tabelas para competições esportivas é uma tarefa difícil, na qual diversas técnicas de otimização combinatória têm sido aplicadas. Nesta tese, formula-se o Problema do Torneio com Viagens Espelhado como um problema de otimização em grafos. O problema é resolvido utilizando- se algoritmos aproximados. Apresentam-se duas heurísticas para este problema. A primeira é muito rápida e serve para fornecer soluções iniciais para a segunda, que é capaz de obter soluções de boa qualidade em tempos razoáveis. São deduzidos limites duais para um tipo particular de instâncias. Estes limites permitem provar a otimalidade das soluções obtidas heuristicamente para instâncias muito maiores do que as maiores instâncias resolvidas na literatura. Por ultimo, é apresentado um modelo de programação linear inteira para o problema, ao qual são acrescentadas desigualdades válidas. Os problemas da classificação visam obter condições, necessárias e suficientes, para a classificação de uma determinada equipe para as finais de um campeonato em relação ao número de pontos a ser obtido. São apresentados modelos de programação linear inteira que permitem resolver estes problemas no contexto do Campeonato Brasileiro de Futebol. / [en] Sports management is a very attractive and not very explored area for applications of Operations Research. Problems in this area use to have simple formulations and reach a big coveragge by the media. Although their formulations are simple, in general these problems are difficult to be solved in computational terms. The results of many academic works in this area have been accepted as solutions for real problems and some solutions are being implemented. This thesis has the main objective of studying two types of problems that appear in the sports area: the fixture creation and the qualification problems. Fixture creation (also known as sport scheduling) for sport competitions is a difficult task, in which several combinatorial optimization techniques has been applied. In this thesis, the Mirrored Traveling Tournament Problem is formulated as a graph optmization problem. The problem is solved using approximation algorithms. Two heuristics are introduced for this problem. The first one is very fast and is used to supply initial solutions for the second one which is able to obtain high quality solutions in reasonable computation times. Dual limits are deduced for a particular type of instances. These limits allow to prove the optimality of the heuristically abtained solutions for instances that are much bigger than those soved in the literature. Finally, an integer programming model is introduced in wich valid inequalities are added. The qualification problems aim to obtain necessary and sufficient conditions for the playoffs qualification of a given team in terms of the number of points to be obtained. Integer programming models are introduced which allow solving these problems in the context of the Brazilian Football Championship.

[pt] A otimização topológica de estruturas sujeitas a carregamentos que variam ao longo do tempo, costuma ter custos computacionais bastante elevados. Isso acontece devido ao grande número de análises dinâmicas que são necessárias. ALém disso, avaliar os gradientes da resposta, que fazem parte da análise de sensibilidade, também resulta em alto custo de computação e requer um grande espaço de armazenamento. Nesta dissertação, em vez de resolver o problema dinâmico original diretamente, é resolvida uma sequência de problemas de otimização de resposta estática com múltiplos casos de carga. Essa abordagem, chamada de método do carregamento estático equivalente, gera cargas estáticas que produzem uma resposta equivalente à obtida na análise dinâmica. Para avaliar as abordagens presentes na literatura, desenvolveu-se um código MATLAB, e diversos exemplos representativos são apresentados. / [en] Topology optimization in the time domain of structures subjected to time-dependent loads is usually computationally expensive, starting with the large number of time-dependent analyses that are required. Futhermore, the computational cost to evaluate the gradients of the response is significantly high and requires a large storage space. In this paper, instead of solving the original dynamical problem directly, we solve a sequence of static response optimization problems with many load cases. This approach, called the equivalent static loads method, generates static loads that produce a similar response in comparison to the same response that the dynamic analysis does. In order to verify the approaches present in the literature, a MATLAB code was developed, and several representatives examples are presented.

[pt] Com o objetivo de desenvolver um sistema de apoio à decisão na área de manutenção embarcada, este trabalho apresenta um modelo para problemas de ordem com restrições: CPSO(mais). Este modelo é a combinação de dois modelos da literatura, o PSO(mais), que apresenta bons resultados em problemas com restrições, e o CPSO, que introduz as modificações necessárias para aplicar o PSO em problemas de ordem. O modelo proposto foi adaptado para resolver o complexo problema de definir a melhor sequência de atividades embarcadas e funcionários alocados, de forma a maximizar o lucro da prestadora de serviço no período de três meses respeitando todas as restrições de prazo de conclusão dos serviços e restrições específicas do segmento offshore. Para avaliar o desempenho deste novo modelo na resolução do problema proposto, duas variantes do CPSO(mais) foram avaliadas frente ao modelo da literatura, CPSO, em seis casos de simulação propostos. Conclui-se pelos resultados das simulações que o modelo CPSO(mais) com inicialização reduzida destaca-se dos demais avaliados por apresentar um tempo de execução moderado e com soluções melhores que as dos demais. / [en] In order to develop an offshore maintenance support system, this work presents a model for constrained combinatorial problems: CPSO(plus). This model is a combination of two models, the PSO(plus), which presented good results in problems with constrains, and the CPSO, which is an adaptation of PSO for application in combinatorial problems. The proposed model has been adapted to solve the complex problem of defining the best sequence of offshore activities and allocated staff so as to maximize service provider profitability within three months while respecting all service completion time constraints and specific offshore work constraints. To evaluate the performance of this new model in solving the proposed problem, two CPSO(plus) variants were evaluated against the literature model, CPSO, in six proposed simulation cases. It is concluded from the results of the simulations that the CPSO(plus) model with reduced initialization outperforms other evaluated models with respect to execution time and solutions to given problem.

[pt] A otimização de binível é uma ferramenta extremamente poderosa para modelar problemas realistas em várias áreas. Por outro lado, sabe-se que a otimização de dois níveis frequentemente leva a problemas complexos ou intratáveis. Nesta tese, apresentamos três trabalhos que expandem o estado da arte da otimização de dois níveis e sua interseção com sistemas de potência. Primeiro, apresentamos BilevelJuMP, um novo pacote de código aberto para otimização de dois níveis na linguagem Julia. O pacote é uma extensão da linguagem de modelagem de programação matemática JuMP, é muito geral, completo e apresenta funcionalidades únicas, como a modelagem de programas cônicos no nível inferior. O software permite aos usuários modelar diversos problemas de dois níveis e resolvê-los com técnicas avançadas. Como consequência, torna a otimização de dois níveis amplamente acessível a um público muito mais amplo. Nos dois trabalhos seguintes, desenvolvemos métodos especializados para lidar com modelos complexos e programas de dois níveis de grande escala decorrentes de aplicações de sistemas de potência. Em segundo lugar, usamos a programação de dois níveis como base para desenvolver o Aprendizado Dirigido pela Aplicação, uma nova estrutura de ciclo fechado na qual os processos de previsão e tomada de decisão são mesclados e co-otimizados. Descrevemos o modelo matematicamente como um programa de dois níveis, provamos resultados de convergência e descrevemos métodos de solução heurísticos e exatos para lidar com sistemas de grande escala. O método é aplicado para previsão de demanda e alocação de reservas na operação de sistemas de potência. Estudos de caso mostram resultados muito promissores com soluções de boa qualidade em sistemas realistas com milhares de barras. Em terceiro lugar, propomos um simulador para modelar mercados de energia hidrotérmica de longo prazo baseados em ofertas. Um problema de otimização estocástica multi-estágio é formulado para acomodar a dinâmica inerente aos sistemas hidrelétricos. No entanto, os subproblemas de cada etapa são programas de dois níveis para modelar agentes estratégicos. O simulador é escalável em termos de dados do sistema, agentes, cenários e estágios considerados. Concluímos o terceiro trabalho com simulações em grande porte com dados realistas do sistema elétrico brasileiro com 3 agentes formadores de preço, 1000 cenários e 60 estágios mensais. Esses três trabalhos mostram que, embora a otimização de dois níveis seja uma classe extremamente desafiadora de problemas NP-difíceis, é possível desenvolver algoritmos eficazes que levam a soluções de boa qualidade. / [en] Bilevel Optimization is an extremely powerful tool for modeling realistic problems in multiple areas. On the other hand, Bilevel Optimization is known to frequently lead to complex or intractable problems. In this thesis, we present three works expanding the state of the art of bilevel optimization and its intersection with power systems. First, we present BilevelJuMP, a novel open-source package for bilevel optimization in the Julia language. The package is an extension of the JuMP mathematical programming modeling language, is very general, feature-complete, and presents unique functionality, such as the modeling of lower-level cone programs. The software enables users to model a variety of bilevel problems and solve them with advanced techniques. As a consequence, it makes bilevel optimization widely accessible to a much broader public. In the following two works, we develop specialized methods to handle much model complex and very large-scale bilevel programs arising from power systems applications. Second, we use bilevel programming as the foundation to develop Application-Driven Learning, a new closed-loop framework in which the processes of forecasting and decision-making are merged and co-optimized. We describe the model mathematically as a bilevel program, prove convergence results and describe exact and tailor-made heuristic solution methods to handle very large-scale systems. The method is applied to demand forecast and reserve allocation in power systems operation. Case studies show very promising results with good quality solutions on realistic systems with thousands of buses. Third, we propose a simulator to model long-term bid-based hydro-thermal power markets. A multi-stage stochastic program is formulated to accommodate the dynamics inherent to hydropower systems. However, the subproblems of each stage are bilevel programs in order to model strategic agents. The simulator is scalable in terms of system data, agents, scenarios, and stages being considered. We conclude the third work with large-scale simulations with realistic data from the Brazilian power system with 3 price maker agents, 1000 scenarios, and 60 monthly stages. These three works show that although bilevel optimization is an extremely challenging class of NP-hard problems, it is possible to develop effective algorithms that lead to good-quality solutions.

[pt] PolieDRO é um novo framework com aplicações tanto no âmbito preditivo quanto prescritivo. Ela aproveita o poder e a flexibilidade da Otimização Robusta a Distribuições (DRO) orientada por dados para evitar a necessidade de hiperparâmetros de regularização, ao mesmo tempo em que extrai estrutura dos dados subjacentes. No âmbito preditivo, a literatura recente mostra que métodos tradicionais de aprendizado de máquina, como SVM e (square-root) LASSO, podem ser formulados como problemas de DRO baseados em métricas de distância de Wasserstein. Inspirados por esses resultados, propomos um conjunto de ambiguidades sem hiperparâmetros que explora a estrutura poliédrica de invólucros convexos orientados por dados, gerando métodos de regressão e classificação computacionalmente viáveis para qualquer função de perda convexa. Resultados numéricos baseados em 100 bancos de dados do mundo real e um extenso experimento com dados gerados sinteticamente mostram que nossos métodos superam consistentemente seus equivalentes tradicionais. No âmbito prescritivo, desenvolvemos um modelo de otimização de portfólio no qual a abordagem DRO é empregada simultaneamente nos níveis de risco e retorno. Aplicando este modelo a dados financeiros reais que abrangem várias décadas, alcançamos um desempenho consistentemente superior em comparação com um benchmark tradicional. / [en] PolieDRO is a novel analytics framework with applications to both predictive and prescriptive realms. It harnesses the power and flexibility of Data-Driven Distributionally Robust Optimization (DRO) to circumvent the need for regularization hyperparameters, while extracting structure from the underlying data. In the field of predictive modeling, recent literature shows that traditional machine learning methods such as SVM and (square-root) LASSO can be written as Wasserstein-based DRO problems. Inspired by those results we propose a hyperparameter-free ambiguity set that explores the polyhedral structure of data-driven convex hulls, generating computationally tractable regression and classification methods for any convex loss function. Numerical results based on 100 real-world databases and an extensive experiment with synthetically generated data show that our methods consistently outperform their traditional counterparts. In the prescriptive realm, we develop a portfolio optimization model that employs the DRO approach simultaneously at the risk and return levels. Applying this model to real financial data spanning several decades, we achieve consistent superior performance compared to a benchmark.

[pt] A maioria das pesquisas científicas publicadas sobre sequenciamento da produção na indústria automobilística consideram os pedidos já alocados em um dia ou turno de trabalho, desconsiderando especificidades do planejamento da cadeia de suprimentos. Esta dissertação procura contribuir no campo do planejamento da produção, propondo um modelo matemático de programação inteira mista que aborda de maneira integrada dois problemas de otimização fundamentais da cadeia: o problema de seleção de pedidos e o problema de sequenciamento de carros em uma única linha de montagem. A fim de abordar questões bem próximas a realidade, incluindo apresentação de experimentos numéricos com o modelo proposto, utilizou-se como cenário o segmento de caminhões, dentro da indústria automotiva. Considerou-se, como objetivo no modelo, além das abordagens tradicionais (minimizar sobrecarga de trabalho, troca de cores e violação de restrições), a demanda dos clientes com relação a prazos de entrega do pedido – principal reforço para uma indústria que pretende cada vez mais migrar para um ambiente de produção orientado pela demanda. / [en] Most published scientific research on production sequencing in the automotive industry consider orders already allocated in a day or shift, disregarding specificities of supply chain planning. This paper aims to contribute in production planning field, proposing a mathematical model of mixed-integer programming that addresses in a integrated way two fundamental problems from chain: the problem of order selection and car sequencing problem on a single assembly line. In order to approach practical issues, including presentation of numerical experiments from proposed model, the truck segment within the automotive industry was used as scenario. It was considered as objective in the model, beyond traditional approaches (minimize work overload, color changing and violation of restrictions), customer demand with respect promised due dates, the main reinforcement for an industry that increasingly want migrate to a production environment driven by demand.

[pt] O Sistema Interligado Nacional Brasileiro (SIN) é um sistema hidrotérmico com forte predominância de geração hidráulica, caracterizado pela existência de reservatórios de grande porte com regularização plurianual. Contudo, com a perspectiva da entrada em operação na região Amazônica de novas usinas de grande porte quanto à capacidade de geração, mas de pequena capacidade de regularização, tem-se a perspectiva de mudanças no atual perfil de operação do SIN em função da região Amazônica possuir um forte ciclo sazonal e baixa complementaridade com as demais regiões do Brasil. Com isto, a metodologia atualmente utilizada, que minimiza o valor esperado do custo total de operação, tende a elevar o risco dos reservatórios do subsistema Sudeste atingirem níveis baixos no fim do período seco, supondo que com a importação de energia da região Amazônica no período úmido o armazenamento, em média, possa ser recuperado. O deplecionamento a níveis baixos dos reservatórios do subsistema Sudeste pode significar um aumento no risco de atendimento à demanda energética, caso venha a se configurar um cenário de afluência desfavorável no período úmido. Isso requer aprimoramentos metodológicos a fim de considerar este novo perfil de operação do SIN. Neste contexto, este trabalho propõe o desenvolvimento de uma modelagem utilizando métodos de apoio multicritério à decisão, que permite a consideração de múltiplos objetivos, para definição do nível mínimo de armazenamento do subsistema Sudeste ao final do período seco de forma a minimizar o valor esperado do custo, dado que se garanta a segurança energética do SIN. O desempenho da metodologia proposta foi avaliado por meio de estudos de casos aplicados ao SIN, para a condição atual e futura, nas quais as novas usinas da região Amazônica estão totalmente motorizadas, e os resultados obtidos, assim como as vantagens observadas ao se utilizar a metodologia multicritério, são discutidos ao longo do texto. / [en] The Brazilian National Interconnected System (SIN) is a large scale hydrothermal system with a strong predominance of hydro generation, characterized by large reservoirs with multi-annual regularization capabilities. However, with the prospect of entry in operation in the Amazon region of new large plants with high generation capacity but low inflows regularization capacity, methodological changes in the energy planning operations are expected due to Amazon’s region strong seasonal cycle and low complementarity with other regions of Brazil. This way, the current methodology, which minimizes the expected value of the total operations cost, tends to raise the risk of the drawdown of the Southeast subsystem reservoirs reaching low levels at the end of the dry season, with the assumption that the reservoirs, on average, will be recovered by the energy imported from Amazon during the wet season. The low drawdown of Southeast subsystem reservoirs can pose a risk for dry scenarios, which may not be able to meet the energy demand. In this context, this work proposes the development of a model using multicriteria decision support methods, which allows consideration of multiple objectives, to define the minimum level of storage of the Southeast subsystem at the end of the dry season to minimize the expected value of cost, provided that it guarantees the energy security of the SIN during the next year. The performance of the proposed methodology has been evaluated by means of case studies applied to SIN, for both the current conditions and the expected future conditions. The results obtained, as well as the advantages observed when using the multicriteria methodology, are discussed throughout the text.