Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T04:31:47Z (GMT). No. of bitstreams: 1 Braga_AndreideAlmeidaSampaio_M.pdf: 1060769 bytes, checksum: 789d9000e49ebe5d5a54a275c6018cb6 (MD5) Previous issue date: 2011 / Resumo: O problema de particionamento de conjuntos (SPP, do inglês set partitioning problem) é considerado um dos problemas de otimização combinatória com mais vasta gama de aplicações. Para solucioná-lo, utilizam-se comumente métodos tradicionais para a resolução de problemas NP - Difíceis. Nesta dissertação, estuda-se o uso da combinação de relaxação Lagrangiana com planos de corte. Relaxação Lagrangiana é uma técnica que tem sido usada com bastante sucesso para atacar vários problemas NP-Difíceis. Os algoritmos relax-and-cut, em especial, onde se adicionam dinamicamente planos de corte a relaxações Lagrangianas, têm ganhado bastante destaque nas últimas décadas. Em [15], Cavalcante et al. aplicam um algoritmo relax-and-cut ao SPP e obtém ótimos resultados. No entanto, tal algoritmo, bem como implementações em geral da citada combinação, são ainda passíveis de refinamentos e extensões. O estudo proposto aqui é realizado por meio das seguintes extensões do referido algoritmo: a implementação de uma partida quente para o multiplicador de uma inequação adicionada; a incorporação do algoritmo a uma enumeração, gerando, assim, um branch-and-cut baseado em relaxação Lagrangiana para o SPP; a implementação do citado branch-and-cut com o emprego de relaxações alternativas e a implementação de uma versão distribuída do algoritmo / Abstract: The set partitioning problem (SPP) is considered one of the combinatorial optimization problems with the widest range of applications. To solve the SPP, one commonly uses traditional methods for NP-Hard problem solving. In this dissertation, we study the use of the combination of Lagrangean relaxation with cutting planes. Lagrangean relaxation is a technique that has been used quite successfully to tackle several NP-Hard problems. In particular, relax-and-cut algorithms, in which cutting planes are added dynamically to Lagrangean relaxations, have gained much importance in the last decades. In [15], Cavalcante et al. applied a relax-and-cut algorithm to the SPP and obtained promising results. However, that algorithm, as well as implementations of the mentioned combination in general, are still subject to refinements and extensions. The study proposed here is carried out through the following extensions of that algorithm: the implementation of a warm start to the multiplier of an added inequality; the incorporation of the algorithm to an enumeration, thus generating a Lagrangean relaxation based branch-and-cut for the SPP; the implementation of that branch-and-cut with the use of alternative relaxations and the implementation of a distributed version of the algorithm / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T17:20:46Z (GMT). No. of bitstreams: 1 Silva_FabricioLuisSantosda_M.pdf: 657410 bytes, checksum: 65ac7a297f6547a9ac70dfa42604f1ce (MD5) Previous issue date: 2010 / Resumo: Neste trabalho lidamos com o problema de Empacotamento em Faixa Bidimensional considerando o caso em que os itens devem ser dispostos de forma a manter o empacotamento estável e satisfazer uma ordem de descarregamento imposta. Consideramos o caso em que a orientação dos itens é fixa. Definimos uma metodologia para analisar a estabilidade do empacotamento observando as condições de equilíbrio estático para corpos rígidos. Desenvolvemos heurísticas e formulamos um programa linear inteiro para o problema de Empacotamento em Faixa sujeito a tais restrições. A resolução da formulação inteira ocorre através de uma estratégia do tipo branch-and-cut. As restrições de estabilidade foram inseridas como planos de corte de maneira a remover empacotamentos que não são estáveis. Em nossos experimentos computacionais, vemos que o modelo proposto é adequado para lidar com instâncias de pequeno até médio porte, dentro de um tempo computacional razoável / Abstract: This paper investigates the Two-Dimensional Strip Packing Problem considering the case in which the items should be arranged to form a stable packing and satisfy an order of unloading, so that after unloading, the packing is still stable. We consider the case where the items are oriented and rotations are not allowed. We present a methodology to analyze the stability of the packing observing the conditions for static equilibrium of rigid bodies. We present heuristics and formulate an integer linear programming model for the Strip Packing problem considering such constraints. To solve the integer formulation, we develop a branch-and-cut approach. For each integer solution obtained during the branch-and-cut algorithm, corresponding to a non-stable packing, we insert a cutting plane for which this integer solution is not satisfied. In our computational experiments, we see that the proposed model is suitable to deal with small and mid-sized instances. Some optimal solutions were obtained after few hours of CPU processing / Mestrado / Mestre em Ciência da Computação

Concerns about energy supply and climate change have been driving companies towards more sustainable manufacturing while they are looking on the economic side as well. One practicable task to achieve sustainability in manufacturing is choosing more sustainable technologies among available technologies. Combination of two functions of ‘Technology Selection’ and ‘Capacity Planning’ is not usually addressed in the research literature. The importance of integrated decisions on technology selection and capacity planning at such strategic level is therefore essentially important. This is supported by justifications in some selected manufacturing areas particularly concerning economies of the scale and accumulated knowledge. Furthermore, manufacturing firms are working in a global competitive environment that is changing in a continuous way. Strategic design of systems under such circumstances requires a carefully modelled approach to deal with the complexity of uncertainties. The overall project aims are to develop an integrated methodological approach to solving the combined ‘technology selection’ and ‘capacity planning’ problems in manufacturing sector. The approach will also incorporate the multi-perspective concept of sustainability, while taking uncertainties into account. A framework consisting of four modules is proposed. Problem structuring module adopts an Ontology method to map the technology mix combinations and to capture input data. ‘Optimisation for Sustainable Manufacturing’ module addresses the optimisation of technology selection and capacity planning decisions in an integrated way using Goal, Mixed Integer Programming method. The model developed takes the multi-criteria aspect of sustainability development into account. Three criteria, namely a) Environmental (e.g. Energy consumption and Emissions), b) Economics, and c) Technical (e.g. Quality) are involved. ‘Normalisation algorithm by comparison with the best value’ method is adopted in this research in order to facilitate a systematic comparison among various criteria. The economic evaluation is based on ‘Life-Cycle Analysis’ approach. The ‘Present Value (PV)’ method is adopted to address ‘Time Value of Money’, while taking both ‘Inflation’ and ‘Market Return’ into account in order to make the proposed model more realistic. A mathematical model to represent the total PV of each technology investment, including both capital and running costs, is developed. ‘Sensitivity Analysis’ module addresses the uncertainty element of the problem. A controlled set of re-optimisation runs, which is guided by a tool coded in Visual Basic for Applications (VBA), is developed to perform intensive sensitivity analyses. It is aimed to deal with the uncertainty element of the problem. Within ‘Solution Structuring’ module, two knowledge structuring schemes, namely Decision Tree and Interactive Slider Diagram, are proposed to deal with the large size of solution sets generated by the “Sensitivity Analysis” module. An innovative, hybrid, Supervised and Unsupervised Machine Learning algorithm is developed to generate a decision tree that aims to structure the solution set. The unsupervised learning stage is implemented using DBSCAN algorithm, while the supervised learning element adopts C4.5 algorithm. The methodological approach is tested and validated using an exemplar case study on coating processes in an automotive company. The case is characterised by three operations, twelve possible technology mix states, both capital budget and environmental limits, and 243 different sensitivity analysis experiments. The painting systems are evaluated and compared based on their quality, technology life-cycle costs, and their potential VOC (Volatile Organic Compounds) emissions into the air.

Traffic Engineering (TE) uses methods and models from a variety of mathematical fields, such as statistics and optimization, to improve the performance of telecommunication networks. In this thesis, we study TE problems dealing with networks that impose single-path routing. As the name infers, in this type of routing, the traffic flow of each "commodity" cannot be split in its path between its origin and destination. Given its cheap cost, single-path routing is widely used in today's data centers, where thousands of stored servers perform computations or host Internet services. One common case of single-path routing is the one enforced by the Spanning Tree Protocol (STP) in switched Ethernet networks. The STP requires the network to keep its activated links loop-free, while maintaining the other redundant links ready for back-up, in case of link failure. The Multiple Spanning Tree Protocol (MSTP) extends the STP by installing multiple virtual networks compliant with the STP, over a single physical topology. Therefore, the MSTP is greatly beneficial for network service providers, as it allows for a more efficient use of the existing resources.Network design problems dealing with the MSTP are generally highly combinatorial and very hard to solve. As such, TE literature mainly suggests heuristic methods, which can quickly produce reasonable designs. Notwithstanding, due to a scarce existence of lower bounds to the optimum values of such problems, there is little knowledge about the quality of the solutions provided by these heuristics.In this sense, we propose mathematical programming models and methods that can provide optimal designs for these networks, or at the very least, obtain valid lower bounds. Taking into mind the goal of avoiding congestion in the network, we focus on two problems that deal with the following load-balancing objectives: the minimization of the worst-case link utilization, and the minimization of flow costs given by piecewise linear functions that penalize heavily-loaded links. The study of both these problems yielded relevant by-products: the first is the study of a MSTP network design problem, where we minimize the total load, and the second is the study of a fundamental unsplittable multicommodity flow problem with piecewise linear costs.For all the considered problems, we provide studies of complexity, extensive polyhedral studies to compare the proposed formulations, and a wide array of computational experiments to evaluate the performance of the proposed models and methods. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

The interdisciplinary field of systems biology has evolved rapidly over the last few years. Different disciplines have contributed to the development of both its experimental and theoretical branches.Although computational biology has been an increasing activity in computer science for more than a two decades, it has been only in the past few years that optimization models have been increasingly developed and analyzed by researchers whose primary background is Operations Research(OR). This dissertation aims at contributing to the field of computational biology by applying mathematical programming to certain problems in molecular biology.Specifically, we address three problems in the domain of Genome Wide Association Studies}:(i) the Pure Parsimony Haplotyping Under uncertatind Data Problem that consists in finding the minimum number of haplotypes necessary to explain a given set of genotypes containing possible reading errors; (ii) the Parsimonious Loss Of Heterozygosity Problem that consists of partitioning suspected polymorphisms from a set of individuals into a minimum number of deletion areas; (iii) and the Multiple Individuals Polymorphic Alu Insertion Recognition Problem that consists of finding the set of locations in the genome where ALU sequences are inserted in some individual(s).All three problems are NP-hard combinatorial optimization problems. Therefore, we analyse their combinatorial structure and we propose an exact approach to solution for each of them. The proposed models are efficient, accurate, compact, polynomial-sized and usable in all those cases for which the parsimony criterion is well suited for estimation. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Mixed-Integer Programming has been a vital tool for the chemical engineer in the recent decades and is employed extensively in process design and control. This dissertation presents some new Mixed-Integer Programming formulations developed for two well-studied problems, one with a central role in the area of Optimisation, the other of great interest to the chemical industry. These are the Travelling Salesman Problem and the problem of scheduling cleaning actions for heat exchanger networks subject to fouling. The Travelling Salesman Problem finds a plethora of applications in many scientific disciplines, Chemical Engineering included. None of the mathematical programming formulations proposed for solving the problem considers fewer than O(n^2) binary degrees of freedom. The first part of this dissertation introduces a novel mathematical description of the Travelling Salesman Problem that succeeds in reducing the binary degrees of freedom to O(nlog2(n)). Three Mixed-Integer Linear Programming formulations are developed and the computational performance of these is tested through computational studies. Sophisticated methods are now available for scheduling the cleaning actions for networks of heat exchangers subject to fouling. In the majority of these, only one form of cleaning is used, which restores the performance of the exchanger back to its clean level. A recent study revised the scheduling problem for the case where there are several cleaning methods available. The second part of this dissertation extends their approach, developed for individual units, to heat exchanger networks and explores the concept of selection of cleaning techniques further. Mixed-Integer Programming formulations are proposed for the scheduling task, for two fouling scenarios: (i) chemical reaction fouling and (ii) biological fouling. A series of results are presented for the implementation of the scheduling formulations to networks of different sizes.

Abstract The purpose of this thesis is to investigate the economics of biodiversity maintenance in boreal forests. From the many tasks available in forest management to improve biodiversity maintenance, the focus is on the lengthening of forest rotation and strict protection, i.e., protected areas. Accordingly, the analysis basis on two different models named forest rotation model and site selection model. Moreover, both socially optimal and cost-effective conservation are considered. The data consists of 32 old-growth stands from northern Finland. The four studies of this dissertation provide evidence of the non-negligible economic consequences of taking biodiversity services into account along with timber production in the forest management. Study I shows that theoretically the optimal management of initial stands involves three alternatives: immediate clear cutting, delayed harvesting, and protection. Moreover, the numerical analysis reveals that taking into account the biodiversity services along with timber production results in considerably longer optimal rotation than in pure timber production management. Delayed harvesting is the most common option for socially optimal management of old-growth forests. However, the integrated approach results also in strict protection of some stands. Study II compares alternative approaches, named integrated, ecological and penny pincher selection, for selecting forest reserves. It suggests the integrated selection leads to 9–19% higher conservation cost-efficiency than the other selections. The integrated selection takes into account both the economic value and ecological features of the stands as the other selections focus only on one of these aspects. It seems also that the xeric forest type may be under-represented in the current old-growth forest preservation network in the studied region. Study III analyses the performance of alternative biodiversity indicators used in the selection of protected areas. It shows that the use of indicators likely results in a loss of species and, therefore, a complete species inventory is necessary if the goal is to maintain all species in the landscape. However, the use of indicators seems to be an economically more efficient practice than to execute a large species survey for habitat protection. Study IV examines the relative merits of alternative biodiversity conservation targets for forestry, which give different weights to species according to their conservation status and assumed population persistence. Also, socially optimal conservation is solved as a benchmark by maximizing the benefits from timber production and biodiversity services. According the results it is optimal to protect 16 out of 32 stands. Alternative conservation goals give different characters in terms of benefit-cost tradeoffs. More specifically goals relying on complementarity between protected stands result in great marginal costs at a high conservation level.

Fixed interval scheduling problems have wide range of practical use in production planning, transportation, in hospitals or in schools when planning timetables. When solving these problems we often encounter requirement of integrality of solutions. Ignoring this condition is often not possible. In this thesis we propose some formulations of scheduling problems and their stochastic extensions. We also propone a new formulation of stochastic FIS problem, for which integrality of solution is byproduct of its definition. We present Gâteaux derivative and its relationship to stability of optimal value function of stochastic optimization problems under the influence of contamination. We propose a new theorem on the stability of such functions for fixed interval scheduling problems.

A key challenge for manufacturing companies is to store parts in an efficient way atthe lowest cost possible. As the demand of differentiated products increases, togetherwith the fact that old products are not phased out at the same pace, the need of usingstorage space as dynamically as possible becomes vital.Scania’s engine assembly manufactures engines for various automotive vehicles andmarine & industry applications. The variation in engine range in Scania’s offeringleads to the need of holding a vast, and increasing, assortment of parts in the produc-tion. As a consequence, this puts more pressure on the logistics and furnishing withinthe engine assembly.This master thesis aims to facilitate the process of assigning parts’ storage locationsin the most profitable manner through an optimization model, the Location Model, inExcel VBA. Together with the model, suggestions of work methods are presented.By implementing the Location Model at Scania’s engine assembly, 4,98 % of all keptparts are recommended location changes, while resulting in cost savings, for the chosen30-day period. These location changes result in a cost saving of 6,73 % of the totallogistic costs for the same time period.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programming (IP) has been and continues to be widely used by industries to minimize cost and effectively manage resources. Faster computers and innovative IP techniques have enabled the solution to many large-scale IPs. However, IPs are NP-hard and many IPs require exponential time to solve. Lifting is one of the most widely used techniques that helps to reduce computational time and is widely applied in today's commercial IP software. Lifting was first introduced by Gomory for bounded integer programs and a theoretical and computationally intractible technique to simultaneously lift sets of variables was introduced by Zemel in 1978. This thesis presents a new algorithm called the Maximal Simultaneous Lifting Algorithm (MSLA), to simultaneously uplift sets of binary integer variables into a cover inequality. These lifted inequalities result in strong inequalities that are facet defining under fairly moderate assumptions. A computational study shows that this algorithm can find numerous strong inequalities for random Knapsack (KP) instances. The pre-processing time observed for these instances is less than 1/50th of a second, which is negligible. These simultaneously lifted inequalities are easy to find and incorporating these cuts to KP instances reduced the solution time by an average of 41%. Therefore, implementing MSLA should be highly beneficial for large real-world problems.