Approximation limits of linear programs (beyond hierarchies)

We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^1/2-ε)-approximations for CLIQUE require LPs of size 2^nΩ(ε). This lower bound applies to LPs using a certain encoding of CLIQUE as a linear optimization problem. Moreover, we establish a similar result for approximations of semidefinite programs by LPs. Our main technical ingredient is a quantitative improvement of Razborov's [38] rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of shifts of the unique disjointness matrix.

Modelagem em programação linear para resolução de jogos fuzzy intervalares

A teoria de jogos modela estratégias entre agentes (jogadores), os quais possuem recompensas ao fim do jogo conforme suas ações. O melhor par de estratégias para os jogadores constitui uma solução de equilíbrio. Porém, nem sempre se consegue estimar os dados do problema. Diante disso, os parâmetros incertos presentes em modelos de jogos são formalizados pela teoria fuzzy. Assim, a teoria fuzzy auxilia a teoria de jogos, formando jogos fuzzy. Dessa forma, parâmetros, como as recompensas, tornam-se números fuzzy. Mais ainda, quando há incerteza na representação desses números fuzzy utilizam-se os números fuzzy intervalares. Então, neste trabalho modelos de jogos fuzzy intervalares são analisados e métodos computacionais são desenvolvidos para a resolução desses jogos. Por fim, realizam-se simulações de programação linear para observar melhor a aplicação das teorias estudadas e avaliar a proposta.

Metodologia de otimização estocástica para coordenação eólico-fotovoltaica

Esta dissertação incide sobre o tema da coordenação entre sistemas eólicos e fotovoltaicos que participam no mercado de eletricidade. A incerteza da potência eólica e fotovoltaica é uma caraterística predominante nesta coordenação, devendo ser considerada no planeamento ótimo de sistemas eólico-fotovoltaicos. A fim de modelizar a incerteza é apresentada uma metodologia de otimização estocástica baseada em programação linear para maximizar o lucro esperado de uma empresa produtora de energia elétrica que participa no mercado diário. A coordenação entre sistemas eólicos e fotovoltaicos visa mitigar os desequilíbrios de energia, resultantes das ofertas horárias submetidas no mercado diário e, consequentemente, reduzir as penalizações financeiras. Os resultados da coordenação entre um sistema eólico e um sistema fotovoltaico são comparados com os resultados obtidos para a operação não coordenada. Estes resultados permitem concluir que a metodologia desenvolvida aplicada à coordenação apresenta um lucro esperado superior ao lucro obtido para a operação não coordenada; Abstract Stochastic Optimization Methodology for Wind-Photovoltaic Coordination This dissertation focuses on the issue of coordination between wind and photovoltaic systems participating in electricity markets. The uncertainty of wind and photovoltaic power is a main characteristic of these systems, which must be included in the optimal scheduling of the coordination of wind with photovoltaic systems. In order to model the uncertainty is presented a stochastic approach based on linear programming to maximize the profit of a wind photovoltaic power producer which participates in electricity markets. The coordination of wind with photovoltaic systems aims to mitigate the energy deviations, as a result of the participation in day-ahead market and therefore reducing economic penalties. The results obtained by the coordination are compared to results obtained by the separated operation of wind and photovoltaic systems. The results allow concluding that the proposed approach applied to the coordination presents an expected profit higher than the expected profit without coordination.

CLIMATE CHANGE ADAPTATION IN VULNERABLE CROP AND LIVESTOCK PRODUCTION SYSTEMS IN MGETA, TANZANIA

Increased occurrence of drought and dry spells during the growing season have resulted in increased interest in protection of tropical water catchment areas. In Mgeta, a water catchment area in the Uluguru Mountains in Tanzania, water used for vegetable and fruit production is provided through canals from the Uluguru South Forest Reserve. The clearing of forest land for cultivation in the steep slopes in the area is causing severe land degradation, which is threatening the water catchment area, livelihoods, and food security of the local communities, as well as the major population centers in the lowlands. In this paper, the economic performance of a traditional cropping-livestock system with East African (EA)-goats and pigs and extensive vegetable production is compared with a more sustainable and environmentally friendly crop-dairy goat production system. A linear programming (LP) crop-livestock model, maximizing farm income considering the environmental constraints in the area was applied for studying the economic performance of dairy goats in the production system. The model was worked out for the rainy and dry seasons and the analysis was conducted for a basic scenario representing the current situation, based on the variability in the 30 years period from 1982-2012, and in a scenario of both lower crop yields and increased crop variability due to climate change. Data obtained from a sample of 60 farmers that were interviewed using a questionnaire was used to develop and parameterize the model. The study found that in the steep slopes of the area, a crop-dairy goat system with extensive use of grass and multipurpose trees (MPTs) would do better than the traditional vegetable gardening with the EA goat production system. The crop-dairy goat system was superior both in the basic and in a climate change scenario since the yield variation of the grass and MPTs system was less affected compared to vegetable crops due to more tree cover and the use of perennial grasses. However, the goat milk production in the area was constrained by inadequate feeding and lack of an appropriate breeding program. Hence, farmers should enhance goat milk production by supplementing with more concentrate feed and by implementing goat-breeding principles. Moreover, policy measures to promote such a development are briefly discussed.

Utilização de inteligência competitiva, da gestão de riscos e da computação aplicada para ganhos de competitividade em instituição organizadora de concursos

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2015.

Modelling reactive and proactive behaviour in simulation

This research investigated the simulation model behaviour of a traditional and combined discrete event as well as agent based simulation models when modelling human reactive and proactive behaviour in human centric complex systems. A departmental store was chosen as human centric complex case study where the operation system of a fitting room in WomensWear department was investigated. We have looked at ways to determine the efficiency of new management policies for the fitting room operation through simulating the reactive and proactive behaviour of staff towards customers. Once development of the simulation models and their verification had been done, we carried out a validation experiment in the form of a sensitivity analysis. Subsequently, we executed a statistical analysis where the mixed reactive and proactive behaviour experimental results were compared with some reactive experimental results from previously published works. Generally, this case study discovered that simple proactive individual behaviour could be modelled in both simulation models. In addition, we found the traditional discrete event model performed similar in the simulation model output compared to the combined discrete event and agent based simulation when modelling similar human behaviour.

Análise gráfica de estruturas porosas sobre a ótica da estereologia

In this work we developed a computer simulation program for physics porous structures based on programming language C + + using a Geforce 9600 GT with the PhysX chip, originally developed for video games. With this tool, the ability of physical interaction between simulated objects is enlarged, allowing to simulate a porous structure, for example, reservoir rocks and structures with high density. The initial procedure for developing the simulation is the construction of porous cubic structure consisting of spheres with a single size and with varying sizes. In addition, structures can also be simulated with various volume fractions. The results presented are divided into two parts: first, the ball shall be deemed as solid grains, ie the matrix phase represents the porosity, the second, the spheres are considered as pores. In this case the matrix phase represents the solid phase. The simulations in both cases are the same, but the simulated structures are intrinsically different. To validate the results presented by the program, simulations were performed by varying the amount of grain, the grain size distribution and void fraction in the structure. All results showed statistically reliable and consistent with those presented in the literature. The mean values and distributions of stereological parameters measured, such as intercept linear section of perimeter area, sectional area and mean free path are in agreement with the results obtained in the literature for the structures simulated. The results may help the understanding of real structures.

Numerical enclosures of the optimal cost of the Kantorovitch’s mass transportation problem

International audience

Lot production size problem and simulation of urban transport

OBJECTIVES AND STUDY METHOD: There are two subjects in this thesis: “Lot production size for a parallel machine scheduling problem with auxiliary equipment” and “Bus holding for a simulated traffic network”. Although these two themes seem unrelated, the main idea is the optimization of complex systems. The “Lot production size for a parallel machine scheduling problem with auxiliary equipment” deals with a manufacturing setting where sets of pieces form finished products. The aim is to maximize the profit of the finished products. Each piece may be processed in more than one mold. Molds must be mounted on machines with their corresponding installation setup times. The key point of our methodology is to solve the single period lot-sizing decisions for the finished products together with the piece-mold and the mold-machine assignments, relaxing the constraint that a single mold may not be used in two machines at the same time. For the “Bus holding for a simulated traffic network” we deal with One of the most annoying problems in urban bus operations is bus bunching, which happens when two or more buses arrive at a stop nose to tail. Bus bunching reflects an unreliable service that affects transit operations by increasing passenger-waiting times. This work proposes a linear mathematical programming model that establishes bus holding times at certain stops along a transit corridor to avoid bus bunching. Our approach needs real-time input, so we simulate a transit corridor and apply our mathematical model to the data generated. Thus, the inherent variability of a transit system is considered by the simulation, while the optimization model takes into account the key variables and constraints of the bus operation. CONTRIBUTIONS AND CONCLUSIONS: For the “Lot production size for a parallel machine scheduling problem with auxiliary equipment” the relaxation we propose able to find solutions more efficiently, moreover our experimental results show that most of the solutions verify that molds are non-overlapping even if they are installed on several machines. We propose an exact integer linear programming, a Relax&Fix heuristic, and a multistart greedy algorithm to solve this problem. Experimental results on instances based on real-world data show the efficiency of our approaches. The mathematical model and the algorithm for the lot production size problem, showed in this research, can be used for production planners to help in the scheduling of the manufacturing. For the “Bus holding for a simulated traffic network” most of the literature considers quadratic models that minimize passenger-waiting times, but they are harder to solve and therefore difficult to operate by real-time systems. On the other hand, our methodology reduces passenger-waiting times efficiently given our linear programming model, with the characteristic of applying control intervals just every 5 minutes.

Exact solutions for the agricultural and the two-dimensional packing problems

Objectives and study method: The objective of this study is to develop exact algorithms that can be used as management tools for the agricultural production planning and to obtain exact solutions for two of the most well known twodimensional packing problems: the strip packing problem and the bin packing problem. For the agricultural production planning problem we propose a new hierarchical scheme of three stages to improve the current agricultural practices. The objective of the first stage is to delineate rectangular and homogeneous management zones into the farmer’s plots considering the physical and chemical soil properties. This is an important task because the soil properties directly affect the agricultural production planning. The methodology for this stage is based on a new method called “Positions and Covering” that first generates all the possible positions in which the plot can be delineated. Then, we use a mathematical model of linear programming to obtain the optimal physical and chemical management zone delineation of the plot. In the second stage the objective is to determine the optimal crop pattern that maximizes the farmer’s profit taken into account the previous management zones delineation. In this case, the crop pattern is affected by both management zones delineation, physical and chemical. A mixed integer linear programming is used to solve this stage. The objective of the last stage is to determine in real-time the amount of water to irrigate in each crop. This stage takes as input the solution of the crop planning stage, the atmospheric conditions (temperature, radiation, etc.), the humidity level in plots, and the physical management zones of plots, just to name a few. This procedure is made in real-time during each irrigation period. A linear programming is used to solve this problem. A breakthrough happen when we realize that we could propose some adaptations of the P&C methodology to obtain optimal solutions for the two-dimensional packing problem and the strip packing. We empirically show that our methodologies are efficient on instances based on real data for both problems: agricultural and two-dimensional packing problems. Contributions and conclusions: The exact algorithms showed in this study can be used in the making-decision support for agricultural planning and twodimensional packing problems. For the agricultural planning problem, we show that the implementation of the new hierarchical approach can improve the farmer profit between 5.27% until 8.21% through the optimization of the natural resources. An important characteristic of this problem is that the soil properties (physical and chemical) and the real-time factors (climate, humidity level, evapotranspiration, etc.) are incorporated. With respect to the two-dimensional packing problems, one of the main contributions of this study is the fact that we have demonstrate that many of the best solutions founded in literature by others approaches (heuristics approaches) are the optimal solutions. This is very important because some of these solutions were up to now not guarantee to be the optimal solutions.

Texto guía para docentes enfocado en el bloque de matemáticas discretas en el primero B.G.U.

El presente trabajo de titulación denominado Texto Guía para Docentes enfocado en el bloque de Matemáticas Discretas del Primero B.G.U, ha sido desarrollado con la finalidad de presentar un aporte significativoy de ayuda al docente de Matemáticas de Primero de Bachillerato, anhelando un mejor desenvolvimiento dentro del aula de clase. Este documento está elaborado en base a la legislación educativa ecuatoriana vigente y de los documentos oficiales del Ministerio de Educación, el tema propuesto corresponde al tercer bloque curricular del primer año de Bachillerato General Unificado en la asignatura de Matemáticas. Nuestro trabajo de titulación se compone de tres capítulos. En el capítulo uno, se presenta una síntesis de temas como la evolución de la educación ecuatoriana, los modelos pedagógicos, los métodos de enseñanza, didáctica de la matemática y programación lineal, considerados como base para el desarrollo de la propuesta. En el capítulo dos, se detalla la investigación estadística realizada mediante una encuesta aplicada a docentes de Matemáticas de Primer año de Bachillerato, pertenecientes a la Coordinación Zonal 6 de Educación, Distrito Norte. Los resultados encontrados cimentaron la propuesta de la implementación del texto guía para el aprendizaje de Matemáticas Discretas. En el capítulo tres se elabora la propuesta del texto guía, estructurado en seis guías didácticas, cada una corresponde al desarrollo de una destreza con criterio de desempeñopara el tema planteado. Al final de este capítulo, se detallan conclusiones y recomendaciones dirigidas para el docente de matemáticas.

Short-Term Trading for a Wind-PV Power Producer in an Electricity Market

This paper deals with the problem of coordinated trading of wind and photovoltaic systems in order to find the optimal bid to submit in a pool-based electricity market. The coordination of wind and photovoltaic systems presents uncertainties not only due to electricity market prices, but also with wind and photovoltaic power forecast. Electricity markets are characterized by financial penalties in case of deficit or excess of generation. So, the aim o this work is to reduce these financial penalties and maximize the expected profit of the power producer. The problem is formulated as a stochastic linear programming problem. The proposed approach is validated with real data of pool-based electricity market of Iberian Peninsula.

Coordinated Scheduling of Wind-Thermal Gencos in Day-Ahead Markets

This paper presents a stochastic mixed-integer linear programming approach for solving the self-scheduling problem of a price-taker thermal and wind power producer taking part in a pool-based electricity market. Uncertainty on electricity price and wind power is considered through a set of scenarios. Thermal units are modeled by variable costs, start-up costs and technical operating constraints, such as: ramp up/down limits and minimum up/down time limits. An efficient mixed-integer linear program is presented to develop the offering strategies of the coordinated production of thermal and wind energy generation, aiming to maximize the expected profit. A case study with data from the Iberian Electricity Market is presented and results are discussed to show the effectiveness of the proposed approach.

Bidding strategy of wind-thermal energy producers

This paper presents a stochastic mixed-integer linear programming approach for solving the self-scheduling problem of a price-taker thermal and wind power producer taking part in a pool-based electricity market. Uncertainty on electricity price and wind power is considered through a set of scenarios. Thermal units are modelled by variable costs, start-up costs and technical operating constraints, such as: forbidden operating zones, ramp up/down limits and minimum up/down time limits. An efficient mixed-integer linear program is presented to develop the offering strategies of the coordinated production of thermal and wind energy generation, having as a goal the maximization of profit. A case study with data from the Iberian Electricity Market is presented and results are discussed to show the effectiveness of the proposed approach.

Optimal Wind Bidding Strategies in Day-Ahead Markets

This paper presents a computer application for wind energy bidding in a day-ahead electricity market to better accommodate the variability of the energy source. The computer application is based in a stochastic linear mathematical programming problem. The goal is to obtain the optimal bidding strategy in order to maximize the revenue. Electricity prices and financial penalties for shortfall or surplus energy deliver are modeled. Finally, conclusions are drawn from an illustrative case study, using data from the day-ahead electricity market of the Iberian Peninsula.