Some new results regarding spikes and a heuristic for spike construction

his paper addresses the problem of minimizing the number of columns with superdiagonal nonzeroes (viz., spiked columns) in a square, nonsingular linear system of equations which is to be solved by Gaussian elimination. The exact focus is on a class of min-spike heuristics in which the rows and columns of the coefficient matrix are first permuted to block lower-triangular form. Subsequently, the number of spiked columns in each irreducible block and their heights above the diagonal are minimized heuristically. We show that ifevery column in an irreducible block has exactly two nonzeroes, i.e., is a doubleton, then there is exactly one spiked column. Further, if there is at least one non-doubleton column, there isalways an optimal permutation of rows and columns under whichnone of the doubleton columns are spiked. An analysis of a few benchmark linear programs suggests that singleton and doubleton columns can abound in practice. Hence, it appears that the results of this paper can be practically useful. In the rest of the paper, we develop a polynomial-time min-spike heuristic based on the above results and on a graph-theoretic interpretation of doubleton columns.

Chance constrained uncertain classification via robust optimization

This paper studies the problem of constructing robust classifiers when the training is plagued with uncertainty. The problem is posed as a Chance-Constrained Program (CCP) which ensures that the uncertain data points are classified correctly with high probability. Unfortunately such a CCP turns out to be intractable. The key novelty is in employing Bernstein bounding schemes to relax the CCP as a convex second order cone program whose solution is guaranteed to satisfy the probabilistic constraint. Prior to this work, only the Chebyshev based relaxations were exploited in learning algorithms. Bernstein bounds employ richer partial information and hence can be far less conservative than Chebyshev bounds. Due to this efficient modeling of uncertainty, the resulting classifiers achieve higher classification margins and hence better generalization. Methodologies for classifying uncertain test data points and error measures for evaluating classifiers robust to uncertain data are discussed. Experimental results on synthetic and real-world datasets show that the proposed classifiers are better equipped to handle data uncertainty and outperform state-of-the-art in many cases.

Modeling reservoir irrigation in uncertain hydrologic environment

In a detailed model for reservoir irrigation taking into account the soil moisture dynamics in the root zone of the crops, the data set for reservoir inflow and rainfall in the command will usually be of sufficient length to enable their variations to be described by probability distributions. However, the potential evapotranspiration of the crop itself depends on the characteristics of the crop and the reference evaporation, the quantification of both being associated with a high degree of uncertainty. The main purpose of this paper is to propose a mathematical programming model to determine the annual relative yield of crops and to determine its reliability, for a single reservoir meant for irrigation of multiple crops, incorporating variations in inflow, rainfall in the command area, and crop consumptive use. The inflow to the reservoir and rainfall in the reservoir command area are treated as random variables, whereas potential evapotranspiration is modeled as a fuzzy set. The model's application is illustrated with reference to an existing single-reservoir system in Southern India.

Environmental Concerns in Water Pricing Policy: an Application of Data Envelopment Analysis (DEA)

25 p.

An economic air pollution control model-application : photochemical smog in Los Angeles County in 1975

An economic air pollution control model, which determines the least cost of reaching various air quality levels, is formulated. The model takes the form of a general, nonlinear, mathematical programming problem. Primary contaminant emission levels are the independent variables. The objective function is the cost of attaining various emission levels and is to be minimized subject to constraints that given air quality levels be attained.

The model is applied to a simplified statement of the photochemical smog problem in Los Angeles County in 1975 with emissions specified by a two-dimensional vector, total reactive hydrocarbon, (RHC), and nitrogen oxide, (NO_x), emissions. Air quality, also two-dimensional, is measured by the expected number of days per year that nitrogen dioxide, (NO₂), and mid-day ozone, (O₃), exceed standards in Central Los Angeles.

The minimum cost of reaching various emission levels is found by a linear programming model. The base or "uncontrolled" emission levels are those that will exist in 1975 with the present new car control program and with the degree of stationary source control existing in 1971. Controls, basically "add-on devices", are considered here for used cars, aircraft, and existing stationary sources. It is found that with these added controls, Los Angeles County emission levels [(1300 tons/day RHC, 1000 tons /day NO_x) in 1969] and [(670 tons/day RHC, 790 tons/day NO_x) at the base 1975 level], can be reduced to 260 tons/day RHC (minimum RHC program) and 460 tons/day NO_x (minimum NO_x program).

"Phenomenological" or statistical air quality models provide the relationship between air quality and emissions. These models estimate the relationship by using atmospheric monitoring data taken at one (yearly) emission level and by using certain simple physical assumptions, (e. g., that emissions are reduced proportionately at all points in space and time). For NO₂, (concentrations assumed proportional to NO_x emissions), it is found that standard violations in Central Los Angeles, (55 in 1969), can be reduced to 25, 5, and 0 days per year by controlling emissions to 800, 550, and 300 tons /day, respectively. A probabilistic model reveals that RHC control is much more effective than NO_x control in reducing Central Los Angeles ozone. The 150 days per year ozone violations in 1969 can be reduced to 75, 30, 10, and 0 days per year by abating RHC emissions to 700, 450, 300, and 150 tons/day, respectively, (at the 1969 NO_x emission level).

The control cost-emission level and air quality-emission level relationships are combined in a graphical solution of the complete model to find the cost of various air quality levels. Best possible air quality levels with the controls considered here are 8 O₃ and 10 NO₂ violations per year (minimum ozone program) or 25 O₃ and 3 NO₂ violations per year (minimum NO₂ program) with an annualized cost of $230,000,000 (above the estimated $150,000,000 per year for the new car control program for Los Angeles County motor vehicles in 1975).

Discrete Modeling of Granular Media: A NURBS-based Approach

This dissertation is concerned with the development of a new discrete element method (DEM) based on Non-Uniform Rational Basis Splines (NURBS). With NURBS, the new DEM is able to capture sphericity and angularity, the two particle morphological measures used in characterizing real grain geometries. By taking advantage of the parametric nature of NURBS, the Lipschitzian dividing rectangle (DIRECT) global optimization procedure is employed as a solution procedure to the closest-point projection problem, which enables the contact treatment of non-convex particles. A contact dynamics (CD) approach to the NURBS-based discrete method is also formulated. By combining particle shape flexibility, properties of implicit time-integration, and non-penetrating constraints, we target applications in which the classical DEM either performs poorly or simply fails, i.e., in granular systems composed of rigid or highly stiff angular particles and subjected to quasistatic or dynamic flow conditions. The CD implementation is made simple by adopting a variational framework, which enables the resulting discrete problem to be readily solved using off-the-shelf mathematical programming solvers. The capabilities of the NURBS-based DEM are demonstrated through 2D numerical examples that highlight the effects of particle morphology on the macroscopic response of granular assemblies under quasistatic and dynamic flow conditions, and a 3D characterization of material response in the shear band of a real triaxial specimen.

Topology optimization of silicon anode structures for lithium-ion battery applications

This thesis presents a topology optimization methodology for the systematic design of optimal multifunctional silicon anode structures in lithium-ion batteries. In order to develop next generation high performance lithium-ion batteries, key design challenges relating to the silicon anode structure must be addressed, namely the lithiation-induced mechanical degradation and the low intrinsic electrical conductivity of silicon. As such, this work considers two design objectives of minimum compliance under design dependent volume expansion, and maximum electrical conduction through the structure, both of which are subject to a constraint on material volume. Density-based topology optimization methods are employed in conjunction with regularization techniques, a continuation scheme, and mathematical programming methods. The objectives are first considered individually, during which the iteration history, mesh independence, and influence of prescribed volume fraction and minimum length scale are investigated. The methodology is subsequently extended to a bi-objective formulation to simultaneously address both the compliance and conduction design criteria. A weighting method is used to derive the Pareto fronts, which demonstrate a clear trade-off between the competing design objectives. Furthermore, a systematic parameter study is undertaken to determine the influence of the prescribed volume fraction and minimum length scale on the optimal combined topologies. The developments presented in this work provide a foundation for the informed design and development of silicon anode structures for high performance lithium-ion batteries.

Otimização de torre de aço para aerogerador eólico.

Diversas formas de geração de energia vêm sendo desenvolvidas com o objetivo de oferecer alternativas ecologicamente corretas. Neste contexto, a energia eólica vem se destacando na região Nordeste do Brasil, devido ao grande potencial dos ventos da região. As torres, que representam parcela significativa do custo total do sistema, tendem a crescer buscando ventos mais fortes e permitindo assim a utilização de aerogeradores com maior capacidade de geração de energia. Este trabalho tem como objetivo formular um modelo de otimização de torres tubulares de aço, para aerogeradores eólicos. Busca-se minimizar o volume total (custo, indiretamente), tendo como variáveis de projeto as espessuras da parede da torre. São impostas restrições relativas à frequência natural e ao comportamento estrutural (tensão e deslocamento máximo de acordo com recomendações da norma Europeia). A estrutura da torre é modelada com base no Método dos Elementos Finitos e o carregamento atuante na estrutura inclui os pesos da torre, do conjunto de equipamentos instalados no topo (aerogerador), e o efeito estático da ação do vento sobre a torre. Para verificação das tensões, deslocamentos e frequências naturais, foram utilizados elementos finitos de casca disponíveis na biblioteca do programa de análise ANSYS. Os modelos de otimização foram também implementados no modulo de otimização do programa ANSYS (design optimization), que utiliza técnicas matemáticas em um processo iterativo computadorizado até que um projeto considerado ótimo seja alcançado. Nas aplicações foram usados os métodos de aproximação por subproblemas e o método de primeira ordem. Os resultados obtidos revelam que torres para aerogeradores merecem atenção especial, em relação à concepção do projeto estrutural, sendo que seu desempenho deve ser verificado através de metodologias completas que englobem além das análises clássicas (estáticas e dinâmicas), incluam também as análises de otimização.

Otimização da programação das limpezas em redes de trocadores de calor utilizando técnicas de programação matemática

Redes de trocadores de calor são bastante utilizadas na indústria química para promover a integração energética do processo, recuperando calor de correntes quentes para aquecer correntes frias. Estas redes estão sujeitas à deposição, o que causa um aumento na resistência à transferência de calor, prejudicando-a. Uma das principais formas de diminuir o prejuízo causado por este fenômeno é a realização periódica de limpezas nos trocadores de calor. O presente trabalho tem como objetivo desenvolver um novo método para encontrar a programação ótima das limpezas em uma rede de trocadores de calor. O método desenvolvido utiliza o conceito de horizonte deslizante associado a um problema de programação linear inteira mista (MILP). Este problema MILP é capaz de definir o conjunto ótimo de trocadores de calor a serem limpos em um determinado instante de tempo (primeiro instante do horizonte deslizante), levando em conta sua influência nos instantes futuros (restante do horizonte deslizante). O problema MILP utiliza restrições referentes aos balanços de energia, equações de trocadores de calor e número máximo de limpezas simultâneas, com o objetivo de minimizar o consumo de energia da planta. A programação ótima das limpezas é composta pela combinação dos resultados obtidos em cada um dos instantes de tempo.O desempenho desta abordagem foi analisado através de sua aplicação em diversos exemplos típicos apresentados na literatura, inclusive um exemplo de grande porte de uma refinaria brasileira. Os resultados mostraram que a abordagem aplicada foi capaz de prover ganhos semelhantes e, algumas vezes, superiores aos da literatura, indicando que o método desenvolvido é capaz de fornecer bons resultados com um baixo esforço computacional

Aplicação de técnicas de otimização no gerenciamento da deposição em redes de trocadores de calor

Deposição é um fenômeno indesejável que ocorre na superfície dos trocadores de calor ao longo de sua operação, ocasionando redução na efetividade térmica e aumento da resistência ao escoamento nestes equipamentos. Estes efeitos trazem grandes consequências econômicas e ambientais, devido ao aumento dos custos operacionais (energia adicional é requerida), aumento dos custos de projeto (demanda por equipamentos de maior área de troca térmica), limitações hidráulicas (que pode levar a uma diminuição da carga processada) e aumento das emissões (aumento da queima de combustíveis fósseis para suprir a energia adicional requerida). Neste contexto, o presente trabalho tem por objetivo fornecer ferramentas computacionais robustas que apliquem técnicas de otimização para o gerenciamento da deposição em redes de trocadores de calor, visando minimizar os seus efeitos negativos. Estas ferramentas foram desenvolvidas utilizando programação matemática no ambiente computacional GAMS, e três abordagens distintas para a resolução do problema da deposição foram pesquisadas. Uma delas consiste na identificação do conjunto ótimo de trocadores de calor a serem limpos durante uma parada para manutenção da planta, visando restaurar a carga térmica nesses equipamentos através da remoção dos depósitos existentes. Já as duas outras abordagens consistem em otimizar a distribuição das vazões das correntes ao longo de ramais paralelos, uma de forma estacionária e a outra de forma dinâmica, visando maximizar a recuperação de energia ao longo da rede. O desempenho destas três abordagens é ilustrado através de um conjunto de exemplos de redes de trocadores de calor, onde os ganhos reais obtidos com estas ferramentas de otimização desenvolvidas são demonstrados

Optimal design of Functionally Graded Materials using a procedural model and Particle Swarm Optimization

A new method for the optimal design of Functionally Graded Materials (FGM) is proposed in this paper. Instead of using the widely used explicit functional models, a feature tree based procedural model is proposed to represent generic material heterogeneities. A procedural model of this sort allows more than one explicit function to be incorporated to describe versatile material gradations and the material composition at a given location is no longer computed by simple evaluation of an analytic function, but obtained by execution of customizable procedures. This enables generic and diverse types of material variations to be represented, and most importantly, by a reasonably small number of design variables. The descriptive flexibility in the material heterogeneity formulation as well as the low dimensionality of the design vectors help facilitate the optimal design of functionally graded materials. Using the nature-inspired Particle Swarm Optimization (PSO) method, functionally graded materials with generic distributions can be efficiently optimized. We demonstrate, for the first time, that a PSO based optimizer outperforms classical mathematical programming based methods, such as active set and trust region algorithms, in the optimal design of functionally graded materials. The underlying reason for this performance boost is also elucidated with the help of benchmarked examples. © 2011 Elsevier Ltd. All rights reserved.

Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

Solving a signalized traffic intersection problem with an hyperbolic penalty function

Mathematical Program with Complementarity Constraints (MPCC) finds many applications in fields such as engineering design, economic equilibrium and mathematical programming theory itself. A queueing system model resulting from a single signalized intersection regulated by pre-timed control in traffic network is considered. The model is formulated as an MPCC problem. A MATLAB implementation based on an hyperbolic penalty function is used to solve this practical problem, computing the total average waiting time of the vehicles in all queues and the green split allocation. The problem was codified in AMPL.