Reconfiguração de sistemas de distribuição de energia elétrica utilizando a metaheurística busca em vizinhança variável

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

Métodos de solução para um problema de sequenciamento da produção com sincronismo de execução de tarefas

Pós-graduação em Engenharia Mecânica - FEG

A Modified Branch and Bound Algorithm to Solve the Transmission Expansion Planning Problem

In this paper a novel Branch and Bound (B&B) algorithm to solve the transmission expansion planning which is a non-convex mixed integer nonlinear programming problem (MINLP) is presented. Based on defining the options of the separating variables and makes a search in breadth, we call this algorithm a B&BML algorithm. The proposed algorithm is implemented in AMPL and an open source Ipopt solver is used to solve the nonlinear programming (NLP) problems of all candidates in the B&B tree. Strategies have been developed to address the problem of non-linearity and non-convexity of the search region. The proposed algorithm is applied to the problem of long-term transmission expansion planning modeled as an MINLP problem. The proposed algorithm has carried out on five commonly used test systems such as Garver 6-Bus, IEEE 24-Bus, 46-Bus South Brazilian test systems, Bolivian 57-Bus, and Colombian 93-Bus. Results show that the proposed methodology not only can find the best known solution but it also yields a large reduction between 24% to 77.6% in the number of NLP problems regarding to the size of the systems.

Algoritmo tabu search especializado para o problema de planejamento da expansao de sistemas de transmissão

Pós-graduação em Engenharia Elétrica - FEIS

Integrated pulp and paper mill planning and scheduling

This article describes a real-world production planning and scheduling problem occurring at an integrated pulp and paper mill (P&P) which manufactures paper for cardboard out of produced pulp. During the cooking of wood chips in the digester, two by-products are produced: the pulp itself (virgin fibers) and the waste stream known as black liquor. The former is then mixed with recycled fibers and processed in a paper machine. Here, due to significant sequence-dependent setups in paper type changeovers, sizing and sequencing of lots have to be made simultaneously in order to efficiently use capacity. The latter is converted into electrical energy using a set of evaporators, recovery boilers and counter-pressure turbines. The planning challenge is then to synchronize the material flow as it moves through the pulp and paper mills, and energy plant, maximizing customer demand (as backlogging is allowed), and minimizing operation costs. Due to the intensive capital feature of P&P, the output of the digester must be maximized. As the production bottleneck is not fixed, to tackle this problem we propose a new model that integrates the critical production units associated to the pulp and paper mills, and energy plant for the first time. Simple stochastic mixed integer programming based local search heuristics are developed to obtain good feasible solutions for the problem. The benefits of integrating the three stages are discussed. The proposed approaches are tested on real-world data. Our work may help P&P companies to increase their competitiveness and reactiveness in dealing with demand pattern oscillations. (C) 2012 Elsevier Ltd. All rights reserved.

Asynchronous teams for joint lot-sizing and scheduling problem in flow shops

The integrated production scheduling and lot-sizing problem in a flow shop environment consists of establishing production lot sizes and allocating machines to process them within a planning horizon in a production line with machines arranged in series. The problem considers that demands must be met without backlogging, the capacity of the machines must be respected, and machine setups are sequence-dependent and preserved between periods of the planning horizon. The objective is to determine a production schedule to minimise the setup, production and inventory costs. A mathematical model from the literature is presented, as well as procedures for obtaining feasible solutions. However, some of the procedures have difficulty in obtaining feasible solutions for large-sized problem instances. In addition, we address the problem using different versions of the Asynchronous Team (A-Team) approach. The procedures were compared with literature heuristics based on Mixed Integer Programming. The proposed A-Team procedures outperformed the literature heuristics, especially for large instances. The developed methodologies and the results obtained are presented.

MATHEMATICAL MODELS AND POLYHEDRAL STUDIES FOR INTEGRAL SHEET METAL DESIGN

We deal with the optimization of the production of branched sheet metal products. New forming techniques for sheet metal give rise to a wide variety of possible profiles and possible ways of production. In particular, we show how the problem of producing a given profile geometry can be modeled as a discrete optimization problem. We provide a theoretical analysis of the model in order to improve its solution time. In this context we give the complete convex hull description of some substructures of the underlying polyhedron. Moreover, we introduce a new class of facet-defining inequalities that represent connectivity constraints for the profile and show how these inequalities can be separated in polynomial time. Finally, we present numerical results for various test instances, both real-world and academic examples.

Accelerating benders decomposition with heuristicmaster problem solutions

In this paper, a general scheme for generating extra cuts during the execution of a Benders decomposition algorithm is presented. These cuts are based on feasible and infeasible master problem solutions generated by means of a heuristic. This article includes general guidelines and a case study with a fixed charge network design problem. Computational tests with instances of this problem show the efficiency of the strategy. The most important aspect of the proposed ideas is their generality, which allows them to be used in virtually any Benders decomposition implementation.

Computing primal solutions with exact arithmetics in SCIP.

The research for exact solutions of mixed integer problems is an active topic in the scientific community. State-of-the-art MIP solvers exploit a floating- point numerical representation, therefore introducing small approximations. Although such MIP solvers yield reliable results for the majority of problems, there are cases in which a higher accuracy is required. Indeed, it is known that for some applications floating-point solvers provide falsely feasible solutions, i.e. solutions marked as feasible because of approximations that would not pass a check with exact arithmetic and cannot be practically implemented. The framework of the current dissertation is SCIP, a mixed integer programs solver mainly developed at Zuse Institute Berlin. In the same site we considered a new approach for exactly solving MIPs. Specifically, we developed a constraint handler to plug into SCIP, with the aim to analyze the accuracy of provided floating-point solutions and compute exact primal solutions starting from floating-point ones. We conducted a few computational experiments to test the exact primal constraint handler through the adoption of two main settings. Analysis mode allowed to collect statistics about current SCIP solutions' reliability. Our results confirm that floating-point solutions are accurate enough with respect to many instances. However, our analysis highlighted the presence of numerical errors of variable entity. By using the enforce mode, our constraint handler is able to suggest exact solutions starting from the integer part of a floating-point solution. With the latter setting, results show a general improvement of the quality of provided final solutions, without a significant loss of performances.

Optimization and Machine Learning Frameworks for Complex Network Analysis

Thesis (Ph.D.)--University of Washington, 2016-06

Zero weights and non-zero slacks:different solution to the same problem

This paper re-assesses three independently developed approaches that are aimed at solving the problem of zero-weights or non-zero slacks in Data Envelopment Analysis (DEA). The methods are weights restricted, non-radial and extended facet DEA models. Weights restricted DEA models are dual to envelopment DEA models with restrictions on the dual variables (DEA weights) aimed at avoiding zero values for those weights; non-radial DEA models are envelopment models which avoid non-zero slacks in the input-output constraints. Finally, extended facet DEA models recognize that only projections on facets of full dimension correspond to well defined rates of substitution/transformation between all inputs/outputs which in turn correspond to non-zero weights in the multiplier version of the DEA model. We demonstrate how these methods are equivalent, not only in their aim but also in the solutions they yield. In addition, we show that the aforementioned methods modify the production frontier by extending existing facets or creating unobserved facets. Further we propose a new approach that uses weight restrictions to extend existing facets. This approach has some advantages in computational terms, because extended facet models normally make use of mixed integer programming models, which are computationally demanding.

Optimization models for selecting bus stops for accessibility improvements for people with disabilities

Bus stops are key links in the journeys of transit patrons with disabilities. Inaccessible bus stops prevent people with disabilities from using fixed-route bus services, thus limiting their mobility. The Americans with Disabilities Act (ADA) of 1990 prescribes the minimum requirements for bus stop accessibility by riders with disabilities. Due to limited budgets, transit agencies can only select a limited number of bus stop locations for ADA improvements annually. These locations should preferably be selected such that they maximize the overall benefits to patrons with disabilities. In addition, transit agencies may also choose to implement the universal design paradigm, which involves higher design standards than current ADA requirements and can provide amenities that are useful for all riders, like shelters and lighting. Many factors can affect the decision to improve a bus stop, including rider-based aspects like the number of riders with disabilities, total ridership, customer complaints, accidents, deployment costs, as well as locational aspects like the location of employment centers, schools, shopping areas, and so on. These interlacing factors make it difficult to identify optimum improvement locations without the aid of an optimization model. This dissertation proposes two integer programming models to help identify a priority list of bus stops for accessibility improvements. The first is a binary integer programming model designed to identify bus stops that need improvements to meet the minimum ADA requirements. The second involves a multi-objective nonlinear mixed integer programming model that attempts to achieve an optimal compromise among the two accessibility design standards. Geographic Information System (GIS) techniques were used extensively to both prepare the model input and examine the model output. An analytic hierarchy process (AHP) was applied to combine all of the factors affecting the benefits to patrons with disabilities. An extensive sensitivity analysis was performed to assess the reasonableness of the model outputs in response to changes in model constraints. Based on a case study using data from Broward County Transit (BCT) in Florida, the models were found to produce a list of bus stops that upon close examination were determined to be highly logical. Compared to traditional approaches using staff experience, requests from elected officials, customer complaints, etc., these optimization models offer a more objective and efficient platform on which to make bus stop improvement suggestions.

How effective are heuristic solutions for electricity planning in developing countries

Acknowledgement The first author would like to acknowledge the University of Aberdeen and the Henderson Economics Research Fund for funding his PhD studies in the period 2011-2014 which formed the basis for the research presented in this paper. The first author would also like to acknowledge the Macaulay Development Trust which funds his postdoctoral fellowship with The James Hutton Institute, Aberdeen, Scotland. The authors thank two anonymous referees for valuable comments and suggestions on earlier versions of this paper. All usual caveats apply

Optimal Capital Requirements in Financial Networks with Fire Sales

I explore and analyze a problem of finding the socially optimal capital requirements for financial institutions considering two distinct channels of contagion: direct exposures among the institutions, as represented by a network and fire sales externalities, which reflect the negative price impact of massive liquidation of assets.These two channels amplify shocks from individual financial institutions to the financial system as a whole and thus increase the risk of joint defaults amongst the interconnected financial institutions; this is often referred to as systemic risk. In the model, there is a trade-off between reducing systemic risk and raising the capital requirements of the financial institutions. The policymaker considers this trade-off and determines the optimal capital requirements for individual financial institutions. I provide a method for finding and analyzing the optimal capital requirements that can be applied to arbitrary network structures and arbitrary distributions of investment returns.

In particular, I first consider a network model consisting only of direct exposures and show that the optimal capital requirements can be found by solving a stochastic linear programming problem. I then extend the analysis to financial networks with default costs and show the optimal capital requirements can be found by solving a stochastic mixed integer programming problem. The computational complexity of this problem poses a challenge, and I develop an iterative algorithm that can be efficiently executed. I show that the iterative algorithm leads to solutions that are nearly optimal by comparing it with lower bounds based on a dual approach. I also show that the iterative algorithm converges to the optimal solution.

Finally, I incorporate fire sales externalities into the model. In particular, I am able to extend the analysis of systemic risk and the optimal capital requirements with a single illiquid asset to a model with multiple illiquid assets. The model with multiple illiquid assets incorporates liquidation rules used by the banks. I provide an optimization formulation whose solution provides the equilibrium payments for a given liquidation rule.

I further show that the socially optimal capital problem using the ``socially optimal liquidation" and prioritized liquidation rules can be formulated as a convex and convex mixed integer problem, respectively. Finally, I illustrate the results of the methodology on numerical examples and

discuss some implications for capital regulation policy and stress testing.

Effektiviseringsmöjligheter avseende fyllnadsgrad : En jämförande analys mellan nuläge och optimerat resultat

The study aims to provide information on efficiency opportunities on SCA's northbound cassettes. It has been made by examining the capacity utilization rate on the northbound cassettes on SCA's vessels for a period of two weeks. The cargo loaded in the ports of Rotterdam and Sheerness consists of external cargo of varying shape. The cargo is shipped northbound to Holmsund and Sundsvall. Measurements have been made on the cargo to the final destinations Sundsvall, Holmsund and Finland. The measurements have been used in a mathematical optimization model created to optimize the loading of the cassettes. The model is based on placing boxes in a grid where the boxes that are placed representing the cargo and the grids representing the cassettes. The aim of the model is to reduce the number of cassettes and thereby increase the capacity utilization rate. The study resulted in an increase in capacity utilization rate for both area and volume to all destinations. The overall improvement for all cassettes examined resulted in an increase in the area capacity utilization rate by 9.02 percentage points and 5.72 percentage points for the volume capacity utilization rate. It also resulted in a decrease of 22 cassettes in total on the four voyages that were examined which indicate that there are opportunities to improve the capacity utilization rate. The study also shows that the model can be used as a basis for similar problems.