Développement d’un algorithme de branch-and-price-and-cut pour le problème de conception de réseau avec coûts fixes et capacités

De nombreux problèmes en transport et en logistique peuvent être formulés comme des modèles de conception de réseau. Ils requièrent généralement de transporter des produits, des passagers ou encore des données dans un réseau afin de satisfaire une certaine demande tout en minimisant les coûts. Dans ce mémoire, nous nous intéressons au problème de conception de réseau avec coûts fixes et capacités. Ce problème consiste à ouvrir un sous-ensemble des liens dans un réseau afin de satisfaire la demande, tout en respectant les contraintes de capacités sur les liens. L'objectif est de minimiser les coûts fixes associés à l'ouverture des liens et les coûts de transport des produits. Nous présentons une méthode exacte pour résoudre ce problème basée sur des techniques utilisées en programmation linéaire en nombres entiers. Notre méthode est une variante de l'algorithme de branch-and-bound, appelée branch-and-price-and-cut, dans laquelle nous exploitons à la fois la génération de colonnes et de coupes pour la résolution d'instances de grande taille, en particulier, celles ayant un grand nombre de produits. En nous comparant à CPLEX, actuellement l'un des meilleurs logiciels d'optimisation mathématique, notre méthode est compétitive sur les instances de taille moyenne et supérieure sur les instances de grande taille ayant un grand nombre de produits, et ce, même si elle n'utilise qu'un seul type d'inégalités valides.

Optimization-Based Robotic Manipulation for Safe Interaction with Human Operators

This thesis investigates a method for human-robot interaction (HRI) in order to uphold productivity of industrial robots like minimization of the shortest operation time, while ensuring human safety like collision avoidance. For solving such problems an online motion planning approach for robotic manipulators with HRI has been proposed. The approach is based on model predictive control (MPC) with embedded mixed integer programming. The planning strategies of the robotic manipulators mainly considered in the thesis are directly performed in the workspace for easy obstacle representation. The non-convex optimization problem is approximated by a mixed-integer program (MIP). It is further effectively reformulated such that the number of binary variables and the number of feasible integer solutions are drastically decreased. Safety-relevant regions, which are potentially occupied by the human operators, can be generated online by a proposed method based on hidden Markov models. In contrast to previous approaches, which derive predictions based on probability density functions in the form of single points, such as most likely or expected human positions, the proposed method computes safety-relevant subsets of the workspace as a region which is possibly occupied by the human at future instances of time. The method is further enhanced by combining reachability analysis to increase the prediction accuracy. These safety-relevant regions can subsequently serve as safety constraints when the motion is planned by optimization. This way one arrives at motion plans that are safe, i.e. plans that avoid collision with a probability not less than a predefined threshold. The developed methods have been successfully applied to a developed demonstrator, where an industrial robot works in the same space as a human operator. The task of the industrial robot is to drive its end-effector according to a nominal sequence of grippingmotion-releasing operations while no collision with a human arm occurs.

Coupled simulations of the Indian monsoon intraseasonal oscillation using a fine-resolution mixed-layer ocean model

The intraseasonal variability (ISV) of the Indian summer monsoon is dominated by a 30–50 day oscillation between “active” and “break” events of enhanced and reduced rainfall over the subcontinent, respectively. These organized convective events form in the equatorial Indian Ocean and propagate north to India. Atmosphere–ocean coupled processes are thought to play a key role the intensity and propagation of these events. A high-resolution, coupled atmosphere–mixed-layer-oceanmodel is assembled: HadKPP. HadKPP comprises the Hadley Centre Atmospheric Model (HadAM3) and the K Profile Parameterization (KPP) mixed-layer ocean model. Following studies that upper-ocean vertical resolution and sub-diurnal coupling frequencies improve the simulation of ISV in SSTs, KPP is run at 1 m vertical resolution near the surface; the atmosphere and ocean are coupled every three hours. HadKPP accurately simulates the 30–50 day ISV in rainfall and SSTs over India and the Bay of Bengal, respectively, but suffers from low ISV on the equator. This is due to the HadAM3 convection scheme producing limited ISV in surface fluxes. HadKPP demonstrates little of the observed northward propagation of intraseasonal events, producing instead a standing oscillation. The lack of equatorial ISV in convection in HadAM3 constrains the ability of KPP to produce equatorial SST anomalies, which further weakens the ISV of convection. It is concluded that while atmosphere–ocean interactions are undoubtedly essential to an accurate simulation of ISV, they are not a panacea for model deficiencies. In regions where the atmospheric forcing is adequate, such as the Bay of Bengal, KPP produces SST anomalies that are comparable to the Tropical Rainfall Measuring Mission Microwave Imager (TMI) SST analyses in both their magnitude and their timing with respect to rainfall anomalies over India. HadKPP also displays a much-improved phase relationship between rainfall and SSTs over a HadAM3 ensemble forced by observed SSTs, when both are compared to observations. Coupling to mixed-layer models such as KPP has the potential to improve operational predictions of ISV, particularly when the persistence time of SST anomalies is shorter than the forecast lead time.

Mixed Logit Model Performance and Distributional Assumptions: Preferences and GM foods

Using mixed logit models to analyse choice data is common but requires ex ante specification of the functional forms of preference distributions. We make the case for greater use of bounded functional forms and propose the use of the Marginal Likelihood, calculated using Bayesian techniques, as a single measure of model performance across non nested mixed logit specifications. Using this measure leads to very different rankings of model specifications compared to alternative rule of thumb measures. The approach is illustrated using data from a choice experiment regarding GM food types which provides insights regarding the recent WTO dispute between the EU and the US, Canada and Argentina and whether labelling and trade regimes should be based on the production process or product composition.

Orthogonal packing of identical rectangles within isotropic convex regions

A mixed integer continuous nonlinear model and a solution method for the problem of orthogonally packing identical rectangles within an arbitrary convex region are introduced in the present work. The convex region is assumed to be made of an isotropic material in such a way that arbitrary rotations of the items, preserving the orthogonality constraint, are allowed. The solution method is based on a combination of branch and bound and active-set strategies for bound-constrained minimization of smooth functions. Numerical results show the reliability of the presented approach. (C) 2010 Elsevier Ltd. All rights reserved.

Programação estocástica para fundos de pensão

Nesta dissertação discutiremos modelos e métodos de soluções de programação estocástica para resolver problemas de ALM em fundos de pensão. Apresentaremos o modelo de (Drijver et al.), baseado na programação estocástica multiestágios inteira-mista. Um estudo de caso para um problema de ALM será apresentado usando simulação de cenários.

Reactive power dispatch and planning using a non-linear branch-and-bound algorithm

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Imposing Radiality Constraints in Distribution System Optimization Problems

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Uma abordagem fuzzy para a avaliação técnico-econômica de redes de acesso

O surgimento de novas tecnologias e serviços vem impondo mudanças substanciais ao tradicional sistema de telecomunicações. Múltiplas possibilidades de evolução do sistema fazem da etapa de planejamento um procedimento não só desejável como necessário, principalmente num ambiente de competitividade. A utilização de metodologias abrangentes e flexíveis que possam auxiliar no processo de decisão, fundadas em modelos de otimização, parece um caminho inevitável. Este artigo propõe um modelo de programação linear inteiro misto para ajudar no planejamento estratégico de sistemas de telecomunicações, e em particular da rede de acesso. Os principais componentes de custo e receita são identificados e o modelo é desenvolvido para determinar a configuração da rede (serviços, tecnologias, etc) que maximize a receita esperada pelo operador do sistema. O conceito de números fuzzy é adotado para avaliar o risco técnico-econômico em situações de imprecisão nos dados de demanda. Resultados de experimentos computacionais são apresentados e discutidos.

Um modelo de otimização inteira mista e heurísticas relax and fix para a programação da produção de fábricas de refrigerantes de pequeno porte

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Procedimento MIXED do SAS® para análise de modelos mistos

O modelo misto consiste numa importante classe de modelos que tem sido tradicionalmente analisada por meio de procedimentos da análise de variância. Nos modelos mistos, três aspectos são fundamentais: estimação e testes de hipóteses dos efeitos fixos, predição dos efeitos aleatórios e estimação dos componentes de variância. Na análise de modelos lineares mistos desbalanceados, a estimação dos componentes de variância é de fundamental importância e depende da estrutura de covariâncias e dos métodos de estimação utilizados. Nesse contexto, este artigo pretende apresentar os principais métodos de estimação e de análise utilizados no estudo de modelos lineares mistos com estruturas gerais de covariâncias nos efeitos aleatórios, disponíveis no procedimento MIXED, do SAS (Statistical Analysis System).

A constructive heuristic algorithm to Short Term Transmission Network Expansion Planning

In this paper a method for solving the Short Term Transmission Network Expansion Planning (STTNEP) problem is presented. The STTNEP is a very complex mixed integer nonlinear programming problem that presents a combinatorial explosion in the search space. In this work we present a constructive heuristic algorithm to find a solution of the STTNEP of excellent quality. In each step of the algorithm a sensitivity index is used to add a circuit (transmission line or transformer) to the system. This sensitivity index is obtained solving the STTNEP problem considering as a continuous variable the number of circuits to be added (relaxed problem). The relaxed problem is a large and complex nonlinear programming and was solved through an interior points method that uses a combination of the multiple predictor corrector and multiple centrality corrections methods, both belonging to the family of higher order interior points method (HOIPM). Tests were carried out using a modified Carver system and the results presented show the good performance of both the constructive heuristic algorithm to solve the STTNEP problem and the HOIPM used in each step.

Heuristic algorithm to solve the short term transmission network expansion planning

In this paper, a method for solving the short term transmission network expansion planning problem is presented. This is a very complex mixed integer nonlinear programming problem that presents a combinatorial explosion in the search space. In order to And a solution of excellent quality for this problem, a constructive heuristic algorithm is presented in this paper. In each step of the algorithm, a sensitivity index is used to add a circuit (transmission line or transformer) or a capacitor bank (fixed or variable) to the system. This sensitivity index is obtained solving the problem considering the numbers of circuits and capacitors banks to be added (relaxed problem), as continuous variables. The relaxed problem is a large and complex nonlinear programming and was solved through a higher order interior point method. The paper shows results of several tests that were performed using three well-known electric energy systems in order to show the possibility and the advantages of using the AC model. ©2007 IEEE.

Specialized genetic algorithm for transmission network expansion planning considering reliability

This paper presents a methodology to solve the transmission network expansion planning problem (TNEP) considering reliability and uncertainty in the demand. The proposed methodology provides an optimal expansion plan that allows the power system to operate adequately with an acceptable level of reliability and in an enviroment with uncertainness. The reliability criterion limits the expected value of the reliability index (LOLE - Loss Of Load Expectation) of the expanded system. The reliability is evaluated for the transmission system using an analytical technique based in enumeration. The mathematical model is solved, in a efficient way, using a specialized genetic algorithm of Chu-Beasley modified. Detailed results from an illustrative example are presented and discussed. © 2009 IEEE.

Transmission network expansion planning considering phase-shifter transformers

This paper presents a novel mathematical model for the transmission network expansion planning problem. Main idea is to consider phase-shifter (PS) transformers as a new element of the transmission system expansion together with other traditional components such as transmission lines and conventional transformers. In this way, PS are added in order to redistribute active power flows in the system and, consequently, to diminish the total investment costs due to new transmission lines. Proposed mathematical model presents the structure of a mixed-integer nonlinear programming (MINLP) problem and is based on the standard DC model. In this paper, there is also applied a specialized genetic algorithm aimed at optimizing the allocation of candidate components in the network. Results obtained from computational simulations carried out with IEEE-24 bus system show an outstanding performance of the proposed methodology and model, indicating the technical viability of using these nonconventional devices during the planning process. Copyright © 2012 Celso T. Miasaki et al.