Equivalence of piecewise-linear approximation and Lagrangian relaxation for network revenue management

The network revenue management (RM) problem arises in airline, hotel, media,and other industries where the sale products use multiple resources. It can be formulatedas a stochastic dynamic program but the dynamic program is computationallyintractable because of an exponentially large state space, and a number of heuristicshave been proposed to approximate it. Notable amongst these -both for their revenueperformance, as well as their theoretically sound basis- are approximate dynamic programmingmethods that approximate the value function by basis functions (both affinefunctions as well as piecewise-linear functions have been proposed for network RM)and decomposition methods that relax the constraints of the dynamic program to solvesimpler dynamic programs (such as the Lagrangian relaxation methods). In this paperwe show that these two seemingly distinct approaches coincide for the network RMdynamic program, i.e., the piecewise-linear approximation method and the Lagrangianrelaxation method are one and the same.

An adaptive multiscale method for density-driven instabilities

Accurate modeling of flow instabilities requires computational tools able to deal with several interacting scales, from the scale at which fingers are triggered up to the scale at which their effects need to be described. The Multiscale Finite Volume (MsFV) method offers a framework to couple fine-and coarse-scale features by solving a set of localized problems which are used both to define a coarse-scale problem and to reconstruct the fine-scale details of the flow. The MsFV method can be seen as an upscaling-downscaling technique, which is computationally more efficient than standard discretization schemes and more accurate than traditional upscaling techniques. We show that, although the method has proven accurate in modeling density-driven flow under stable conditions, the accuracy of the MsFV method deteriorates in case of unstable flow and an iterative scheme is required to control the localization error. To avoid large computational overhead due to the iterative scheme, we suggest several adaptive strategies both for flow and transport. In particular, the concentration gradient is used to identify a front region where instabilities are triggered and an accurate (iteratively improved) solution is required. Outside the front region the problem is upscaled and both flow and transport are solved only at the coarse scale. This adaptive strategy leads to very accurate solutions at roughly the same computational cost as the non-iterative MsFV method. In many circumstances, however, an accurate description of flow instabilities requires a refinement of the computational grid rather than a coarsening. For these problems, we propose a modified iterative MsFV, which can be used as downscaling method (DMsFV). Compared to other grid refinement techniques the DMsFV clearly separates the computational domain into refined and non-refined regions, which can be treated separately and matched later. This gives great flexibility to employ different physical descriptions in different regions, where different equations could be solved, offering an excellent framework to construct hybrid methods.

Practical applications of a systematic approach to the chemical abatement of pollutants in water and air

The present dissertation is devoted to the systematic approach to the development of organic toxic and refractory pollutants abatement by chemical decomposition methods in aqueous and gaseous phases. The systematic approach outlines the basic scenario of chemical decomposition process applications with a step-by-step approximation to the most effective result with a predictable outcome for the full-scale application, confirmed by successful experience. The strategy includes the following steps: chemistry studies, reaction kinetic studies in interaction with the mass transfer processes under conditions of different control parameters, contact equipment design and studies, mathematical description of the process for its modelling and simulation, processes integration into treatment technology and its optimisation, and the treatment plant design. The main idea of the systematic approach for oxidation process introduction consists of a search for the most effective combination between the chemical reaction and the treatment device, in which the reaction is supposed to take place. Under this strategy,a knowledge of the reaction pathways, its products, stoichiometry and kinetics is fundamental and, unfortunately, often unavailable from the preliminary knowledge. Therefore, research made in chemistry on novel treatment methods, comprisesnowadays a substantial part of the efforts. Chemical decomposition methods in the aqueous phase include oxidation by ozonation, ozone-associated methods (O3/H2O2, O3/UV, O3/TiO2), Fenton reagent (H2O2/Fe2+/3+) and photocatalytic oxidation (PCO). In the gaseous phase, PCO and catalytic hydrolysis over zero valent ironsare developed. The experimental studies within the described methodology involve aqueous phase oxidation of natural organic matter (NOM) of potable water, phenolic and aromatic amino compounds, ethylene glycol and its derivatives as de-icing agents, and oxygenated motor fuel additives ¿ methyl tert-butyl ether (MTBE) ¿ in leachates and polluted groundwater. Gas-phase chemical decomposition includes PCO of volatile organic compounds and dechlorination of chlorinated methane derivatives. The results of the research summarised here are presented in fifteenattachments (publications and papers submitted for publication and under preparation).

Estudo comparativo de métodos de preparo de amostras de tinta para a determinação de metais e metalóides por técnicas de espectrometria atômica

This work deals with paint decomposition methods for major, minor and trace elements determination. Three methods were investigated: (1) decomposition in closed quartz vessel and heating in microwave oven; (2) decomposition in open vessel using HNO3 and ashing, following the ASTM D 3335-85a method; and (3) decomposition in open vessel using HNO3 + HF and ashing. Paints of different types and colours were analyzed, in which several elements were determined using inductively coupled plasma mass spectrometry (ICP-MS) and inductively coupled plasma optical emission spectrometry (ICP OES). It was observed that method (1) is appropriate for trace, minor and major elements determination, while method (3) is appropriate for Ti.

Nichtüberlappende Gebietszerlegungsmethoden für lineare und quasilineare (monotone und nichtmonotone) Probleme

In dieser Arbeit werden nichtüberlappende Gebietszerlegungsmethoden einerseits hinsichtlich der zu lösenden Problemklassen verallgemeinert und andererseits in bisher nicht untersuchten Kontexten betrachtet. Dabei stehen funktionalanalytische Untersuchungen zur Wohldefiniertheit, eindeutigen Lösbarkeit und Konvergenz im Vordergrund. Im ersten Teil werden lineare elliptische Dirichlet-Randwertprobleme behandelt, wobei neben Problemen mit dominantem Hauptteil auch solche mit singulärer Störung desselben, wie konvektions- oder reaktionsdominante Probleme zugelassen sind. Der zweite Teil befasst sich mit (gleichmäßig) monotonen koerziven quasilinearen elliptischen Dirichlet-Randwertproblemen. In beiden Fällen wird das Lipschitz-Gebiet in endlich viele Lipschitz-Teilgebiete zerlegt, wobei insbesondere Kreuzungspunkte und Teilgebiete ohne Außenrand zugelassen sind. Anschließend werden Transmissionsprobleme mit frei wählbaren $L^{\infty}$-Parameterfunktionen hergeleitet, wobei die Konormalenableitungen als Funktionale auf geeigneten Funktionenräumen über den Teilrändern ($H_{00}^{1/2}(\Gamma)$) interpretiert werden. Die iterative Lösung dieser Transmissionsprobleme mit einem Ansatz von Deng führt auf eine Substrukturierungsmethode mit Robin-artigen Transmissionsbedingungen, bei der eine Auswertung der Konormalenableitungen aufgrund einer geschickten Aufdatierung der Robin-Daten nicht notwendig ist (insbesondere ist die bekannte Robin-Robin-Methode von Lions als Spezialfall enthalten). Die Konvergenz bezüglich einer partitionierten $H^1$-Norm wird für beide Problemklassen gezeigt. Dabei werden keine über $H^1$ hinausgehende Regularitätsforderungen an die Lösungen gestellt und die Gebiete müssen keine zusätzlichen Glattheitsvoraussetzungen erfüllen. Im letzten Kapitel werden nichtmonotone koerzive quasilineare Probleme untersucht, wobei das Zugrunde liegende Gebiet nur in zwei Lipschitz-Teilgebiete zerlegt sein soll. Das zugehörige nichtlineare Transmissionsproblem wird durch Kirchhoff-Transformation in lineare Teilprobleme mit nichtlinearen Kopplungsbedingungen überführt. Ein optimierungsbasierter Lösungsansatz, welcher einen geeigneten Abstand der rücktransformierten Dirichlet-Daten der linearen Teilprobleme auf den Teilrändern minimiert, führt auf ein optimales Kontrollproblem. Die dabei entstehenden regularisierten freien Minimierungsprobleme werden mit Hilfe eines Gradientenverfahrens unter minimalen Glattheitsforderungen an die Nichtlinearitäten gelöst. Unter zusätzlichen Glattheitsvoraussetzungen an die Nichtlinearitäten und weiteren technischen Voraussetzungen an die Lösung des quasilinearen Ausgangsproblems, kann zudem die quadratische Konvergenz des Newton-Verfahrens gesichert werden.

Pre-school contributions to future achievements

This paper provides recent evidence about the beneÖts of attending preschool on future performance. A non-parametric matching procedure is used over two outcomes: math and verbal scores at a national mandatory test (Saber11) in Colombia. It is found that students who had the chance of attending preschool obtain higher scores in math (6.7%) and verbal (5.4%) than those who did not. A considerable fraction of these gaps comes from the upper quintiles of studentís performance, suggesting that preschool matters when is done at high quality institutions. When we include the number of years at the preschool, the gap rises up to 12% in verbal and 17% in math.

Rural-urban disparities in child nutrition in Bangladesh and Nepal

Background The persistence of rural-urban disparities in child nutrition outcomes in developing countries alongside rapid urbanisation and increasing incidence of child malnutrition in urban areas raises an important health policy question - whether fundamentally different nutrition policies and interventions are required in rural and urban areas. Addressing this question requires an enhanced understanding of the main drivers of rural-urban disparities in child nutrition outcomes especially for the vulnerable segments of the population. This study applies recently developed statistical methods to quantify the contribution of different socio-economic determinants to rural-urban differences in child nutrition outcomes in two South Asian countries – Bangladesh and Nepal. Methods Using DHS data sets for Bangladesh and Nepal, we apply quantile regression-based counterfactual decomposition methods to quantify the contribution of (1) the differences in levels of socio-economic determinants (covariate effects) and (2) the differences in the strength of association between socio-economic determinants and child nutrition outcomes (co-efficient effects) to the observed rural-urban disparities in child HAZ scores. The methodology employed in the study allows the covariate and coefficient effects to vary across entire distribution of child nutrition outcomes. This is particularly useful in providing specific insights into factors influencing rural-urban disparities at the lower tails of child HAZ score distributions. It also helps assess the importance of individual determinants and how they vary across the distribution of HAZ scores. Results There are no fundamental differences in the characteristics that determine child nutrition outcomes in urban and rural areas. Differences in the levels of a limited number of socio-economic characteristics – maternal education, spouse’s education and the wealth index (incorporating household asset ownership and access to drinking water and sanitation) contribute a major share of rural-urban disparities in the lowest quantiles of child nutrition outcomes. Differences in the strength of association between socio-economic characteristics and child nutrition outcomes account for less than a quarter of rural-urban disparities at the lower end of the HAZ score distribution. Conclusions Public health interventions aimed at overcoming rural-urban disparities in child nutrition outcomes need to focus principally on bridging gaps in socio-economic endowments of rural and urban households and improving the quality of rural infrastructure. Improving child nutrition outcomes in developing countries does not call for fundamentally different approaches to public health interventions in rural and urban areas.

On the welfare costs of business cycles in the 20th century

Lucas (1987) has shown a surprising result in business-cycle research, that the welfare cost of business cycles are relatively small. Using standard assumptions on preferences and a reasonable reduced form for consumption, we computed these welfare costs for the pre- and post-WWII era, using three alternative trend-cycle decomposition methods. The post-WWII period is very era this basic result is dramatically altered. For the Beveridge and Nelson decomposition, and reasonable preference parameter and discount values, we get a compensation of about 5% of consumption, which is by all means a sizable welfare cost (about US$ 1,000.00 a year).

Um problema de programação da produção numa fundição automatizada

Este trabalho apresenta a modelagem de um problema particular de Programação da Produção numa Fundição Automatizada e sua resolução por um algoritmo de busca heurística, que explora a estrutura do problema.

Multi-areas optimal reactive power flow

This paper describes a method for the decentralized solution of the optimal reactive power flow (ORPF) problem in interconnected power systems. The ORPF model is solved in a decentralized framework, consisting of regions, where the transmission system operator in each area operates its system independently of the other areas, obtaining an optimal coordinated but decentralized solution. The proposed scheme is based on an augmented Lagrangian approach using the auxiliary problem principle (APP). An implementation of an interior point method is described to solve the decoupled problem in each area. The described method is successfully implemented and tested using the IEEE two area RTS 96 test system. Numerical results comparing the solutions obtained by the traditional and the proposed decentralized methods are presented for validation. ©2008 IEEE.

Multiarea optimal power flow using multiobjective evolutionary algorithm

In this work the multiarea optimal power flow (OPF) problem is decoupled into areas creating a set of regional OPF subproblems. The objective is to solve the optimal dispatch of active and reactive power for a determined area, without interfering in the neighboring areas. The regional OPF subproblems are modeled as a large-scale nonlinear constrained optimization problem, with both continuous and discrete variables. Constraints violated are handled as objective functions of the problem. In this way the original problem is converted to a multiobjective optimization problem, and a specifically-designed multiobjective evolutionary algorithm is proposed for solving the regional OPF subproblems. The proposed approach has been examined and tested on the RTS-96 and IEEE 354-bus test systems. Good quality suboptimal solutions were obtained, proving the effectiveness and robustness of the proposed approach. ©2009 IEEE.

Decentralized AC power flow for real-time multi-TSO power system operation

This paper adjusts decentralized OPF optimization to the AC power flow problem in power systems with interconnected areas operated by diferent transmission system operators (TSO). The proposed methodology allows finding the operation point of a particular area without explicit knowledge of network data of the other interconnected areas, being only necessary to exchange border information related to the tie-lines between areas. The methodology is based on the decomposition of the first-order optimality conditions of the AC power flow, which is formulated as a nonlinear programming problem. To allow better visualization of the concept of independent operation of each TSO, an artificial neural network have been used for computing border information of the interconnected TSOs. A multi-area Power Flow tool can be seen as a basic building block able to address a large number of problems under a multi-TSO competitive market philosophy. The IEEE RTS-96 power system is used in order to show the operation and effectiveness of the decentralized AC Power Flow. ©2010 IEEE.

Aplicação de técnicas de decomposição em problemas de corte de estoque

Pós-graduação em Matemática - IBILCE

Representação modal alternativa de linhas de transmissão trifásicas simétricas não idealmente transpostas

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

A practical approach for outdoors distributed target localization in wireless sensor networks

Wireless sensor networks are posed as the new communication paradigm where the use of small, low-complexity, and low-power devices is preferred over costly centralized systems. The spectra of potential applications of sensor networks is very wide, ranging from monitoring, surveillance, and localization, among others. Localization is a key application in sensor networks and the use of simple, efficient, and distributed algorithms is of paramount practical importance. Combining convex optimization tools with consensus algorithms we propose a distributed localization algorithm for scenarios where received signal strength indicator readings are used. We approach the localization problem by formulating an alternative problem that uses distance estimates locally computed at each node. The formulated problem is solved by a relaxed version using semidefinite relaxation technique. Conditions under which the relaxed problem yields to the same solution as the original problem are given and a distributed consensusbased implementation of the algorithm is proposed based on an augmented Lagrangian approach and primaldual decomposition methods. Although suboptimal, the proposed approach is very suitable for its implementation in real sensor networks, i.e., it is scalable, robust against node failures and requires only local communication among neighboring nodes. Simulation results show that running an additional local search around the found solution can yield performance close to the maximum likelihood estimate.