Leilões combinados

Mestrado em Controlo de Gestão e dos Negócios

Increase of the Delivered Power Probability in Distribution Networks using Pareto DC Programming

A methodology to increase the probability of delivering power to any load point through the identification of new investments in distribution network components is proposed in this paper. The method minimizes the investment cost as well as the cost of energy not supplied in the network. A DC optimization model based on mixed integer non-linear programming is developed considering the Pareto front technique in order to identify the adequate investments in distribution networks components which allow increasing the probability of delivering power for any customer in the distribution system at the minimum possible cost for the system operator, while minimizing the energy not supplied cost. Thus, a multi-objective problem is formulated. To illustrate the application of the proposed methodology, the paper includes a case study which considers a 180 bus distribution network

Aplicação de um modelo de programação linear inteira mista (PLIM) na expansão da rede de distribuição de energia elétrica em Angola

Em Angola, apenas cerca de 30% da população tem acesso à energia elétrica, nível que decresce para valores inferiores a 10% em zonas rurais mais remotas. Este problema é agravado pelo facto de, na maioria dos casos, as infraestruturas existentes se encontrarem danificadas ou não acompanharem o desenvolvimento da região. Em particular na capital angolana, Luanda que, sendo a menor província de Angola, é a que regista atualmente a maior densidade populacional. Com uma população de cerca de 5 milhões de habitantes, não só há frequentemente problemas relacionados com a falha do fornecimento de energia elétrica como há ainda uma percentagem considerável de municípios onde a rede elétrica ainda nem sequer chegou. O governo de Angola, no seu esforço de crescimento e aproveitamento das suas enormes potencialidades, definiu o setor energético como um dos fatores críticos para o desenvolvimento sustentável do país, tendo assumido que este é um dos eixos prioritários até 2016. Existem objetivos claros quanto à reabilitação e expansão das infraestruturas do setor elétrico, aumentando a capacidade instalada do país e criando uma rede nacional adequada, com o intuito não só de melhorar a qualidade e fiabilidade da rede já existente como de a aumentar. Este trabalho de dissertação consistiu no levantamento de dados reais relativamente à rede de distribuição de energia elétrica de Luanda, na análise e planeamento do que é mais premente fazer relativamente à sua expansão, na escolha dos locais onde é viável localizar novas subestações, na modelação adequada do problema real e na proposta de uma solução ótima para a expansão da rede existente. Depois de analisados diferentes modelos matemáticos aplicados ao problema de expansão de redes de distribuição de energia elétrica encontrados na literatura, optou-se por um modelo de programação linear inteira mista (PLIM) que se mostrou adequado. Desenvolvido o modelo do problema, o mesmo foi resolvido por recurso a software de otimização Analytic Solver e CPLEX. Como forma de validação dos resultados obtidos, foi implementada a solução de rede no simulador PowerWorld 8.0 OPF, software este que permite a simulação da operação do sistema de trânsito de potências.

Scalable and Efficient Configuration of TimeDivision Multiplexed Resources

Consumer-electronics systems are becoming increasingly complex as the number of integrated applications is growing. Some of these applications have real-time requirements, while other non-real-time applications only require good average performance. For cost-efficient design, contemporary platforms feature an increasing number of cores that share resources, such as memories and interconnects. However, resource sharing causes contention that must be resolved by a resource arbiter, such as Time-Division Multiplexing. A key challenge is to configure this arbiter to satisfy the bandwidth and latency requirements of the real-time applications, while maximizing the slack capacity to improve performance of their non-real-time counterparts. As this configuration problem is NP-hard, a sophisticated automated configuration method is required to avoid negatively impacting design time. The main contributions of this article are: 1) An optimal approach that takes an existing integer linear programming (ILP) model addressing the problem and wraps it in a branch-and-price framework to improve scalability. 2) A faster heuristic algorithm that typically provides near-optimal solutions. 3) An experimental evaluation that quantitatively compares the branch-and-price approach to the previously formulated ILP model and the proposed heuristic. 4) A case study of an HD video and graphics processing system that demonstrates the practical applicability of the approach.

An evolutionary multi-objective optimization system for earthworks

Earthworks involve the levelling or shaping of a target area through the moving or processing of the ground surface. Most construction projects require earthworks, which are heavily dependent on mechanical equipment (e.g., excavators, trucks and compactors). Often, earthworks are the most costly and time-consuming component of infrastructure constructions (e.g., road, railway and airports) and current pressure for higher productivity and safety highlights the need to optimize earthworks, which is a nontrivial task. Most previous attempts at tackling this problem focus on single-objective optimization of partial processes or aspects of earthworks, overlooking the advantages of a multi-objective and global optimization. This work describes a novel optimization system based on an evolutionary multi-objective approach, capable of globally optimizing several objectives simultaneously and dynamically. The proposed system views an earthwork construction as a production line, where the goal is to optimize resources under two crucial criteria (costs and duration) and focus the evolutionary search (non-dominated sorting genetic algorithm-II) on compaction allocation, using linear programming to distribute the remaining equipment (e.g., excavators). Several experiments were held using real-world data from a Portuguese construction site, showing that the proposed system is quite competitive when compared with current manual earthwork equipment allocation.

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.

Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs

Most research on single machine scheduling has assumedthe linearity of job holding costs, which is arguablynot appropriate in some applications. This motivates ourstudy of a model for scheduling $n$ classes of stochasticjobs on a single machine, with the objective of minimizingthe total expected holding cost (discounted or undiscounted). We allow general holding cost rates that are separable,nondecreasing and convex on the number of jobs in eachclass. We formulate the problem as a linear program overa certain greedoid polytope, and establish that it issolved optimally by a dynamic (priority) index rule,whichextends the classical Smith's rule (1956) for the linearcase. Unlike Smith's indices, defined for each class, ournew indices are defined for each extended class, consistingof a class and a number of jobs in that class, and yieldan optimal dynamic index rule: work at each time on a jobwhose current extended class has larger index. We furthershow that the indices possess a decomposition property,as they are computed separately for each class, andinterpret them in economic terms as marginal expected cost rate reductions per unit of expected processing time.We establish the results by deploying a methodology recentlyintroduced by us [J. Niño-Mora (1999). "Restless bandits,partial conservation laws, and indexability. "Forthcomingin Advances in Applied Probability Vol. 33 No. 1, 2001],based on the satisfaction by performance measures of partialconservation laws (PCL) (which extend the generalizedconservation laws of Bertsimas and Niño-Mora (1996)):PCL provide a polyhedral framework for establishing theoptimality of index policies with special structure inscheduling problems under admissible objectives, which weapply to the model of concern.

Promoting the development of secure mobile agent applications

Peer-reviewed

Identifying quantitative operation principles in metabolic pathways: a systematic method for searching feasible enzyme activity patterns leading to cellular adaptive responses

Background: Optimization methods allow designing changes in a system so that specific goals are attained. These techniques are fundamental for metabolic engineering. However, they are not directly applicable for investigating the evolution of metabolic adaptation to environmental changes. Although biological systems have evolved by natural selection and result in well-adapted systems, we can hardly expect that actual metabolic processes are at the theoretical optimum that could result from an optimization analysis. More likely, natural systems are to be found in a feasible region compatible with global physiological requirements. Results: We first present a new method for globally optimizing nonlinear models of metabolic pathways that are based on the Generalized Mass Action (GMA) representation. The optimization task is posed as a nonconvex nonlinear programming (NLP) problem that is solved by an outer- approximation algorithm. This method relies on solving iteratively reduced NLP slave subproblems and mixed-integer linear programming (MILP) master problems that provide valid upper and lower bounds, respectively, on the global solution to the original NLP. The capabilities of this method are illustrated through its application to the anaerobic fermentation pathway in Saccharomyces cerevisiae. We next introduce a method to identify the feasibility parametric regions that allow a system to meet a set of physiological constraints that can be represented in mathematical terms through algebraic equations. This technique is based on applying the outer-approximation based algorithm iteratively over a reduced search space in order to identify regions that contain feasible solutions to the problem and discard others in which no feasible solution exists. As an example, we characterize the feasible enzyme activity changes that are compatible with an appropriate adaptive response of yeast Saccharomyces cerevisiae to heat shock Conclusion: Our results show the utility of the suggested approach for investigating the evolution of adaptive responses to environmental changes. The proposed method can be used in other important applications such as the evaluation of parameter changes that are compatible with health and disease states.

Sherali-Adams Relaxations and Indistinguishability in Counting Logics

Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the linear programming relaxation known as fractional isomorphism. We show that the levels of the Sherali--Adams (SA) hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well-known color-refinement heuristic for graph isomorphism called the Weisfeiler--Lehman algorithm, or, equivalently, with the levels of indistinguishability in a logic with counting quantifiers and a bounded number of variables. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers that a fixed number of levels of SA suffice to determine isomorphism of planar and minor-free graphs. We also offer applications in both finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs, such as that of having a flow circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer, and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to $\Omega(n)$ levels, where $n$ is the number of vertices in the graph.

« Resolution Search » et problèmes d’optimisation discrète

Thèse réalisée en cotutelle avec l'Université d'Avignon.

Lagrangian-informed mixed integer programming reformulations

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques.

Preparation and Study of Optical Properties of CdS, CdS-TiO2 and CdS-Au Nanocomposites for Photonic Applications

Nanophotonics can be regarded as a fusion of nanotechnology and photonics and it is an emerging field providing researchers opportunities in fundamental science and new technologies. In recent times many new methodsand techniques have been developed to prepare materials at nanoscale dimensions. Most of these materials exhibit unique and interesting optical properties and behavior. Many of these have been found to be very useful to develop new devices and systems such as tracers in biological systems, optical limiters, light emitters and energy harvesters. This thesis presents a summary of the work done by the author in the field by choosing a few semiconductor systems to prepare nanomaterials and nanocomposites. Results of the study of linear and nonlinear optical properties of materials thus synthesized are also presented in the various chapters of this thesis. CdS is the material chosen here and the methods and the studies of the detailed investigation are presented in this thesis related to the optical properties of CdS nanoparticles and its composites. Preparation and characterization methods and experimental techniques adopted for the investigations were illustrated in chapter 2 of this thesis. Chapter 3 discusses the preparation of CdS, TiO2 and Au nanoparticles. We observed that the fluorescence behaviour of the CdS nanoparticles, prepared by precipitation technique, depends on excitation wavelength. It was found that the peak emission wavelength can be shifted by as much as 147nm by varyingthe excitation wavelengths and the reason for this phenomenon is the selective excitation of the surface states in the nanoparticles. This provided certain amount of tunability for the emission which results from surface states.TiO2 nanoparticle colloids were prepared by hydrothermal method. The optical absorption study showed a blue shift of absorption edge, indicating quantum confinement effect. The large spectral range investigated allows observing simultaneously direct and indirect band gap optical recombination. The emission studies carried out show four peaks, which are found to be generated from excitonic as well as surface state transitions. It was found that the emission wavelengths of these colloidal nanoparticles and annealed nanoparticles showed two category of surface state emission in addition to the excitonic emission. Au nanoparticles prepared by Turkevich method showed nanoparticles of size below 5nm using plasmonic absorption calculation. It was also found that there was almost no variation in size as the concentration of precursor was changed from 0.2mM to 0.4mM.We have observed SHG from CdS nanostructured thin film prepared onglass substrate by chemical bath deposition technique. The results point out that studied sample has in-plane isotropy. The relative values of tensor components of the second-order susceptibility were determined to be 1, zzz 0.14, xxz and 0.07. zxx These values suggest that the nanocrystals are oriented along the normal direction. However, the origin of such orientation remains unknown at present. Thus CdS is a promising nonlinear optical material for photonic applications, particularly for integrated photonic devices. CdS Au nanocomposite particles were prepared by mixing CdS nanoparticles with Au colloidal nanoparticles. Optical absorption study of these nanoparticles in PVA solution suggests that absorption tail was red shifted compared to CdS nanoparticles. TEM and EDS analysis suggested that the amount of Au nanoparticles present on CdS nanoparticles is very small. Fluorescence emission is unaffected indicating the presence of low level of Au nanoparticles. CdS:Au PVA and CdS PVA nanocomposite films were fabricated and optically characterized. The results showed a red-shift for CdS:Au PVA film for absorption tail compared to CdS PVA film. Nonlinear optical analysis showed a huge nonlinear optical absorption for CdS:Au PVA nanocomposite and CdS:PVA films. Also an enhancement in nonlinear optical absorption is found for CdS:Au PVA thin film compared to the CdS PVA thin film. This enhancement is due to the combined effect of plasmonic as well as excitonic contribution at high input intensity. Samples of CdS doped with TiO2 were also prepared and the linear optical absorption spectra of these nanocompositeparticles clearly indicated the influence of TiO2 nanoparticles. TEM and EDS studies have confirmed the presence of TiO2 on CdS nanoparticles. Fluorescence studies showed that there is an increase in emission peak around 532nm for CdS nanoparticles. Nonlinear optical analysis of CdS:TiO2 PVA nanocomposite films indicated a large nonlinear optical absorption compared to that of CdS:PVA nanocomposite film. The values of nonlinear optical absorption suggests that these nanocomposite particles can be employed for optical limiting applications. CdSe-CdS and CdSe-ZnS core-shell QDs with varying shell size were characterized using UV–VIS spectroscopy. Optical absorption and TEM analysis of these QDs suggested a particle size around 5 nm. It is clearly shown that the surface coating influences the optical properties of QDs in terms of their size. Fluorescence studies reveal the presence of trap states in CdSe-CdS and CdSe- ZnS QDs. Trap states showed an increase as a shell for CdS is introduced and increasing the shell size of CdS beyond a certain value leads to a decrease in the trap state emission. There is no sizeable nonlinear optical absorption observed. In the case of CdSe- ZnS QDs, the trap state emission gets enhanced with the increase in ZnS shell thickness. The enhancement of emission from trap states transition due to the increase in thickness of ZnS shell gives a clear indication of distortion occurring in the spherical symmetry of CdSe quantum dots. Consequently the nonlinear optical absorption of CdSe-ZnS QDs gets increased and the optical limiting threshold is decreased as the shell thickness is increased in respect of CdSe QDs. In comparison with CdSe-CdS QDs, CdSe-ZnS QDs possess much better optical properties and thereby CdSe-ZnS is a strong candidate for nonlinear as well as linear optical applications.

Modeling small-scale dairy farms in central Mexico using multi-criteria programming

Milk supply from Mexican dairy farms does not meet demand and small-scale farms can contribute toward closing the gap. Two multi-criteria programming techniques, goal programming and compromise programming, were used in a study of small-scale dairy farms in central Mexico. To build the goal and compromise programming models, 4 ordinary linear programming models were also developed, which had objective functions to maximize metabolizable energy for milk production, to maximize margin of income over feed costs, to maximize metabolizable protein for milk production, and to minimize purchased feedstuffs. Neither multicriteria approach was significantly better than the other; however, by applying both models it was possible to perform a more comprehensive analysis of these small-scale dairy systems. The multi-criteria programming models affirm findings from previous work and suggest that a forage strategy based on alfalfa, rye-grass, and corn silage would meet nutrient requirements of the herd. Both models suggested that there is an economic advantage in rescheduling the calving season to the second and third calendar quarters to better synchronize higher demand for nutrients with the period of high forage availability.

Simulation models in farming systems research : potential and challenges

Integrated simulation models can be useful tools in farming system research. This chapter reviews three commonly used approaches, i.e. linear programming, system dynamics and agent-based models. Applications of each approach are presented and strengths and drawbacks discussed. We argue that, despite some challenges, mainly related to the integration of different approaches, model validation and the representation of human agents, integrated simulation models contribute important insights to the analysis of farming systems. They help unravelling the complex and dynamic interactions and feedbacks among bio-physical, socio-economic, and institutional components across scales and levels in farming systems. In addition, they can provide a platform for integrative research, and can support transdisciplinary research by functioning as learning platforms in participatory processes.