[pt] O uso de ferramentas de otimização destaca-se como um relevante diferencial para as empresas no que tange a otimização de processos e melhoria de sistemas e performances. Neste contexto, a busca por modelos de programação simples e eficazes para a resolução dos problemas contribuem para adaptação de modelos existentes a fim de atender a esta crescente demanda. Atualmente, o setor de transporte ferroviário busca otimização de seus processos com o objetivo de aumentar sua competitividade e eficiência frente ao transporte realizado por rodovia. Este estudo, focado na melhoria de processos do setor ferroviário, tem como objetivo realizar o planejamento da distribuição de materiais de manutenção em uma malha ferroviária com o menor custo operacional viável. Para isto, o problema é modelado como um problema de programação inteira mista e busca tornar o processo mais eficiente, com redução de desperdícios e otimização dos recursos. Os resultados obtidos foram comparados ao processo atual de distribuição a fim de medir os ganhos em processo e em redução de custos e recursos. O modelo se mostrou eficiente em tempo e qualidade de solução quando comparado com o atual, apresentando uma redução de 20 por cento a 26 por cento nos custos totais de distribuição, variando de acordo com o almoxarifado analisado. Além disso, o estudo também mostrou uma redução no custo de distribuição para todas as localidades testadas, sendo que, quanto menor a distância destes locais ao almoxarifado, maior a redução dos custos logísticos relacionados. / [en] The use of optimization tools highlights a relevant differential to companies in terms of improving processes, systems and performance. In this context, the search for simple and effective programming models for problem solving contributes to the adaptation of existing models to attend this increasing demand. Currently, the railway transport seeks to optimize its processes in order to increase its competitiveness and efficiency when compared to road transport. This study, focused on improving processes in the railway, aims to realize the distribution planning of maintenance materials in a railway network with the lowest feasible operating cost. For this, the problem is modeled as a mixedinteger programming problem and it aims to make the process more efficient, with waste reduction and resource optimization. The obtained results were compared to the current distribution process in order to measure gains in process and in reducing costs and resources. The model proved to be efficient in both time and solution quality when compared to the current one, presenting a reduction of 20 percent to 26 percent in the distribution costs, depending on the analyzed warehouses. In addition, the study has also indicated a reduction in the distribution costs in all tested locations and the distance among those locations and their warehouses leads to a greater reduction in the logistic costs.

京都大学 / 新制・課程博士 / 博士(工学) / 甲第24219号 / 工博第5047号 / 新制||工||1788(附属図書館) / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 藤井 聡, 教授 山田 忠史, 准教授 QURESHI Ali Gul / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DGAM

No description available.

[pt] A organização da operação do transporte marítimo pode ser descrita dentre três modelos: liner, industrial ou tramp. No setor de tramp, armadores buscam otimizar os lucros através de ganhos de capacidade e redução de custos, ao mesmo tempo em que atendem às demandas e às restrições colocadas pelos clientes, muitas vezes baseadas em contratos. O roteamento de navios se torna um tema relevante dado que disponibilidade e confiabilidade de datas são um grande diferencial, ainda mais no atual contexto de alta oferta de navios tramp no mercado e, consequentemente, fretes mais baixos. Assim, o objetivo desse trabalho é apresentar um modelo de programação inteira mista visando a maximização do lucro de viagens pertencentes a uma específica rota geográfica de uma empresa tramp. O problema trabalhado nessa dissertação é do tipo pick-up e delivery (coleta e entrega) com janelas de tempo, múltiplas cargas a bordo, frota heterogénea, cargas fracionadas entre navios, velocidades de navegação variáveis e termos de tempo de trânsito garantidos. Utilizando-se da otimização Branch-and-Bound, o modelo é comparado com programações mensal real feita de maneira empírica por profissionais experientes dessa empresa em que o modelo matemático gera soluções com reduções de até 7 por cento dos custos totais e desafiando paradigmas estabelecidos pelos programadores quando da realização do roteamento e programação dos navios. Tendo em vista tais resultados, o modelo se apresentou como oportunidade de implementação e melhoria do processo de programação dos navios e do nível de serviço junto aos clientes. / [en] The organization of the maritime transport operation can be defined among three models: liner, industrial or tramp. In the tramp sector, shipowners seek to optimize profits through capacity gains and cost savings, while meeting the demands and constraints placed by customers, often based on contracts. Vessel routing becomes as availability and reliability of dates is a great differential, especially in the current context of a high supply of tramp vessels in the market and, consequently, lower freight rates. Thus, the hereby objective is to present a mixed integer programming model aiming to maximize the profit of all voyages belonging to a specific geographical route of a tramp company. The problem solved with in this work can be defined as of pick-up and delivery with time windows, multiple cargoes on board, heterogeneous fleet, split loads, variable sailing speeds and guaranteed transit time terms. Using Branch-and-Bound optimization, the model is compared to actual monthly routing planning made empirically by experienced professionals of that company and the mathematical model generates solutions with reductions of up to 7 percent of total costs and challenging programmers established paradigms when routing and programming vessels. In view of these results, the model presented itself as an opportunity to be implemented and improve the vessel routing and planning process and level of service to customers.

[pt] Em infecções bacterianas, a rapidez no resultado e acurácia do teste diagnóstico é imprescindível para o tratamento direcionado da doença. O tempo sem tratamento agrava a infecção e o uso inadequado de antibióticos pode acarretar o desenvolvimento de bactérias multirresistentes. Um sistema otimizado de análise microbiológica pode garantir menores custos de funcionamento, além de elevado nível de serviço. Este trabalho apresenta um modelo matemático de localização de instalações para criação de uma rede de diagnóstico microbiológico formada a partir de estratégias de identificação bacteriana e/ou da presença de resistência antimicrobiana em populações com suspeita de infecção sanguínea. São objetivos do modelo de programação inteira mista: minimizar custos logísticos da rede, diminuir tempos de coletas e transporte de amostras assim como maximizar o benefício decorrente de um diagnóstico rápido e eficiente. O modelo proposto foi aplicado a dados reais de demanda de procedimentos microbiológicos do Estado de São Paulo. Dentre as tecnologias elegíveis, a solução ótima sugere a instalação de 12 laboratórios centralizados para o atendimento de testes. O tempo total médio de diagnóstico, desconsiderando os tempos de cultura, é de 10,3 horas. A estimativa de economia anual com medicamentos representa 98.498.965,70 de reais do valor orçamentário dedicado a aquisição de medicamentos. Comparados a uma rede de diagnóstico descentralizada, os resultados apontam redução média de tempo de identificação microbiana e economia 48 por cento maior. As análises também evidenciam o impacto do custo de tratamento sobre os tempos de diagnóstico. Os resultados indicam a eficácia do modelo como ferramenta de suporte à tomada de decisão e auxílio a instituições provedoras de saúde podendo ser aplicado a outras regiões administrativas e em diferentes níveis de formação de rede. / [en] In bacterial infections the speed in results and accuracy of the diagnostic test is essential for the targeted treatment of the disease. Untreated time aggravates infection and inappropriate use of antibiotics can lead to the development of multidrug-resistant bacteria. An optimized microbiological analysis system can guarantee lower running costs as well as a higher service level. This work presents a mathematical model of location of facilities to create a microbiological diagnostic network formed from bacterial identification strategies and/or the presence of antimicrobial resistance in populations with suspected blood infection. The objectives of the mixed integer programming model are minimizing network logistics costs, shorten sample collection and transport times as well as maximizing the benefits from rapid and efficient diagnostics. The proposed model was applied to real demand data of microbiological procedures of the State of São Paulo. Among the eligible technologies, the optimal solution suggests the installation of 12 centralized testing laboratories. The average total time of diagnosis, excluding culture times, is 10.3 hours. The estimated annual savings on medicines represents BRL 98,498,965.70 of the budget amount dedicated to drug procurement. Compared to a decentralized diagnostic network, the results show an average reduction in microbial identification time and an economy 48 percent higher. The analyzes also highlight the impact of treatment cost on diagnostic times. The results indicate the effectiveness of the model as a tool to support decision making and aid to health care institutions and can be applied to other administrative regions and at different levels of network formation.

This dissertation is organized into three independent chapters. In Chapter 1, I consider the selection of weights for averaging a set of threshold models. Existing model averaging literature primarily focuses on averaging linear models, I consider threshold regression models. The theory I developed in that chapter demonstrates that the proposed jackknife model averaging estimator achieves asymptotic optimality when the set of candidate models are all misspecified threshold models. The simulations study demonstrates that the jackknife model averaging estimator achieves the lowest mean squared error when contrasted against other model selection and model averaging methods. In Chapter 2, I propose a model averaging framework for the synthetic control method of Abadie and Gardeazabal (2003) and Abadie et al. (2010). The proposed estimator serves a twofold purpose. First, it reduces the bias in estimating the weights each member of the donor pool receives. Secondly, it accounts for model uncertainty for the program evaluation estimation. I study two variations of the model, one where model weights are derived by solving a cross-validation quadratic program and another where each candidate model receives equal weights. Next, I show how to apply the placebo study and the conformal inference procedure for both versions of my estimator. With a simulation study, I reveal that the superior performance of the proposed procedure. In Chapter 3, which is co-authored with my advisor Professor Youngki Shin, we provide an exact computation algorithm for the maximum rank correlation estimator using the mixed integer programming (MIP) approach. We construct a new constrained optimization problem by transforming all indicator functions into binary parameters to be estimated and show that the transformation is equivalent to the original problem. Using a modern MIP solver, we apply the proposed method to an empirical example and Monte Carlo simulations. The results show that the proposed algorithm performs better than the existing alternatives. / Dissertation / Doctor of Philosophy (PhD)

This dissertation develops efficient solution techniques for general and problem-specific applications within nonconvex optimization, exploiting the constructs of the Reformulation-Linearization Technique (RLT). We begin by developing a technique to enhance general problems in nonconvex optimization through the use of a new class of RLT cuts, called semidefinite cuts. While these cuts are valid for any general problem for which RLT is applicable, we demonstrate their effectiveness in optimizing a nonconvex quadratic objective function over a simplex. Computational results indicate that on average, the semidefinite cuts have reduced the number of nodes in the branch-and-bound tree by a factor of 37.6, while decreasing solution time by a factor of 3.4. The semidefinite cuts have also led to a significant reduction in the optimality gap at termination, in some cases producing optimal solutions for problems that could not be solved using RLT alone. We then narrow our focus to the class of mixed-integer programming (MIP) problems, and develop a modification of Benders' decomposition method using concepts from RLT and lift-and-project cuts. This method is particularly motivated by the class of two-stage stochastic programs with integer recourse. The key idea is to design an RLT or lift-and-project cutting plane scheme for solving the subproblems where the cuts generated have right-hand sides that are functions of the first-stage variables. An illustrative example is provided to elucidate the proposed approach. The focus is on developing a first comprehensive finitely convergent extension of Benders' methodology for problems having 0-1 mixed-integer subproblems. We next address a specific challenging MIP application known as the facility layout problem, and we significantly improve its formulation through outer-linearization techniques and concepts from disjunctive programming. The enhancements produce a substantial increase in the accuracy of the layout produced, while at the same time, providing a dramatic reduction in computational effort. Overall, the maximum error in department size was reduced from about 6% to nearly zero, while solution time decreased by a factor of 110. Previously unsolved test problems from the literature that had defied even approximate solution methods have been solved to exact optimality using our proposed approach. / Ph. D.

With the advent of distributed energy resources (DERs), electric vehicles, and demand-response programs, grid operators are in dire need of new monitoring and design tools that help improve efficiency, reliability, and stability of modern power networks. To this end, the work in this thesis explores a generalized modeling and analysis framework for two pertinent tasks: i) learning loads via grid probing, and; ii) optimizing power grid topologies for stability. Distribution grids currently lack comprehensive real-time metering. Nevertheless, grid operators require precise knowledge of loads and renewable generation to accomplish any feeder optimization task. At the same time, new grid technologies, such as solar panels and energy storage units are interfaced via inverters with advanced sensing and actuation capabilities. In this context, we first put forth the idea of engaging power electronics to probe an electric grid and record its voltage response at actuated and metered buses to infer non-metered loads. Probing can be accomplished by commanding inverters to momentarily perturb their power injections. Multiple probing actions can be induced within a few tens of seconds. Load inference via grid probing is formulated as an implicit nonlinear system identification task, which is shown to be topologically observable under certain conditions. The analysis holds for single- and multi-phase grids, radial or meshed, and applies to phasor or magnitude-only voltage data. Using probing to learn non-constant-power loads is also analyzed as a special case. Once a probing setup is deemed topologically observable, a methodology for designing probing injections abiding by inverter and network constraints to improve load estimates is provided. The probing task under noisy phasor and non-phasor data is tackled using a semidefinite-program relaxation. As a second contribution, we also study the effect of topology on the linear time-invariant dynamics of power networks. For a variety of stability metrics, a unified framework based on the H2-norm of the system is presented. The proposed framework assesses the robustness of power grids to small disturbances and is used to study the optimal placement of new lines on existing networks as well as the design of radial topologies for new networks. / Doctor of Philosophy / Increased penetration of distributed energy resources such as solar panels, wind farms, and energy storage systems is forcing utilities to rethink how they design and operate their power networks. To ensure efficient and reliable operation of distribution networks and to perform any grid-wide optimization or dispatch tasks, the system operator needs to precisely know the net load (energy output) of every customer. However, due to the sheer extent of distribution networks (millions of customers) and low investment interest in the past, distribution grids have limited metering infrastructure. Nevertheless, data from grid sensors comprised of voltage and load measurements are readily available from a subset of customers at high temporal resolution. In addition, the smart inverters found in solar panels, energy storage units, and electric vehicles can be controlled within microseconds. The work in this thesis explores how the proliferation of grid sensors together with the controllability of smart inverters can be leveraged for inferring the non-metered loads i.e., energy output of customers that are not equipped with smart inverters/sensors. In addition to the load learning task, this thesis also presents a modeling and analysis framework to study the optimal design of topologies (how customers are electrically inter-connected) for improving stability of our power networks.

Les travaux de cette thèse concernent la conception et l’optimisation de lignes de transfert reconfigurables. L’objectif principal est de concevoir une ligne d’usinage à moindre coût tout en respectant les contraintes techniques, technologiques et économiques du problème. Le problème d’optimisation correspondant est un problème d’équilibrage de lignes d’usinage sujet à des contraintes spécifiques. Il consiste à affecter les opérations aux stations de travail en minimisant les coûts d’installation. En plus des contraintes habituelles de ce type de problème, à savoir, les contraintes de précédence, d’inclusion et d’exclusion, nous avons dû considérer des contraintes d’accessibilité. De plus, la spécificité principale des lignes reconfigurables par rapport aux lignes de transfert dédiées, vient de la réalisation en série des opérations. Celle-ci rend souvent nécessaire la mise en place de stations équipées de plusieurs centres d’usinage travaillant en parallèle pour obtenir les volumes de production souhaités. Enfin, l’utilisation d’une tête d’usinage mono-broche induit la prise en compte de temps inter-opératoire de déplacements et de changement d’outils qui dépendent de la séquence d’opérations. Dans un premier temps, nous avons proposé une modélisation mathématique du problème à l’aide d’un programme linéaire en nombres mixtes. Nous avons aussi développé des méthodes de calcul de bornes inférieures ainsi qu’une procédure de prétraitement. Cependant, les contraintes additionnelles rendent la résolution du problème d’équilibrage plus difficile que dans le cas des lignes dédiées, et l’approche proposée ne permet généralement pas de résoudre des instances de taille industrielle. Pour répondre à ce besoin, nous avons donc développé plusieurs méthodes de résolution approchées du problème en nous inspirant de métaheuristiques efficaces sur des problèmes d’optimisation combinatoire. / This work concerns the design and the optimization of reconfigurable transfer lines. The principle objective is to design a machining line with less cost while respecting the technological and economic constraints of the problem. The corresponding optimization problem is a transfer lines balancing problem subject to specific constraints. It consists to affect operations to workstations minimizing the installations cost. In addition to the habitual constraints of the transfer balancing problem, i.e. precedence, inclusion and exclusion constraints, we consider accessibility constraints. In addition, the principal specificity of reconfigurable lines compared to the dedicated transfer lines, comes from the sequential execution of operations. This often makes it necessary to set up stations with several machining centers working in parallel to achieve desired production volumes. Finally, the utilization of mono-spindle head machining center induces the inclusion of setup times between operations. This setup time is due to the time of displacement and change of tools which it depends of the operational sequence. We proposed firstly a mathematical formalization of the problem using a mixed integer program. We developed also several methods to calculate lower bounds and a pretreatment procedure. However, the additional constraints make the resolution of the considered balancing problem very difficult and the proposed approach generally does not solve instances of industrial size. To meet this need, we have developed several approximate resolution methods of the problem taking inspiration from effective Metaheuristics on combinatorial optimization problems.

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques. / Integer linear programming is a robust and efficient approach to solve large-scale instances of combinatorial problems. However, problems constantly gain in complexity and sometimes impose strong constraints on computation times. We must then develop specialised methods to compute heuristic primal solutions to the problem and derive lower bounds on the optimal value, and thus prove the quality of our primal solutions. We propose to guide a reformulation approach for mixed integer programs with Lagrangian relaxations. After the identification of a strong relaxation, a mechanical process leads to a second integer formulation. This reformulation is equivalent to the initial one, but its linear relaxation is equivalent to the strong Lagrangian dual. We will show that the reformulation approach unifies and generalises prior formulations and lower bounding approaches, and that it exposes a simple mechanism to reduce the size of reformulations in return for weaker bounds. Nevertheless, our reformulations are large. We address this issue by solving their linear relaxations with specialised methods. Finally, we apply the reformulation approach to two location problems. This yields novel formulations for both problems; some are very large but, thanks to the aforementioned specialised methods, still practical.