Approximate credal network updating by linear programming with applications to decision making

Credal nets are probabilistic graphical models which extend Bayesian nets to cope with sets of distributions. An algorithm for approximate credal network updating is presented. The problem in its general formulation is a multilinear optimization task, which can be linearized by an appropriate rule for fixing all the local models apart from those of a single variable. This simple idea can be iterated and quickly leads to accurate inferences. A transformation is also derived to reduce decision making in credal networks based on the maximality criterion to updating. The decision task is proved to have the same complexity of standard inference, being NPPP-complete for general credal nets and NP-complete for polytrees. Similar results are derived for the E-admissibility criterion. Numerical experiments confirm a good performance of the method.

Approximating Credal Network Inferences by Linear Programming

An algorithm for approximate credal network updating is presented. The problem in its general formulation is a multilinear optimization task, which can be linearized by an appropriate rule for fixing all the local models apart from those of a single variable. This simple idea can be iterated and quickly leads to very accurate inferences. The approach can also be specialized to classification with credal networks based on the maximality criterion. A complexity analysis for both the problem and the algorithm is reported together with numerical experiments, which confirm the good performance of the method. While the inner approximation produced by the algorithm gives rise to a classifier which might return a subset of the optimal class set, preliminary empirical results suggest that the accuracy of the optimal class set is seldom affected by the approximate probabilities

Ancillary services dispatch using linear programming and genetic algorithm approaches

Electricity market players operating in a liberalized environment requires access to an adequate decision support tool, allowing them to consider all the business opportunities and take strategic decisions. Ancillary services represent a good negotiation opportunity that must be considered by market players. For this, decision support tools must include ancillary market simulation. This paper proposes two different methods (Linear Programming and Genetic Algorithm approaches) for ancillary services dispatch. The methodologies are implemented in MASCEM, a multi-agent based electricity market simulator. A test case concerning the dispatch of Regulation Down, Regulation Up, Spinning Reserve and Non-Spinning Reserve services is included in this paper.

Stochastic short-term maintenance scheduling of GENCOs in an oligopolistic electricity market

In the proposed model, the independent system operator (ISO) provides the opportunity for maintenance outage rescheduling of generating units before each short-term (ST) time interval. Long-term (LT) scheduling for 1 or 2 years in advance is essential for the ISO and the generation companies (GENCOs) to decide their LT strategies; however, it is not possible to be exactly followed and requires slight adjustments. The Cournot-Nash equilibrium is used to characterize the decision-making procedure of an individual GENCO for ST intervals considering the effective coordination with LT plans. Random inputs, such as parameters of the demand function of loads, hourly demand during the following ST time interval and the expected generation pattern of the rivals, are included as scenarios in the stochastic mixed integer program defined to model the payoff-maximizing objective of a GENCO. Scenario reduction algorithms are used to deal with the computational burden. Two reliability test systems were chosen to illustrate the effectiveness of the proposed model for the ST decision-making process for future planned outages from the point of view of a GENCO.

Localização Ótima de Aparelhos de Corte Normalmente Abertos e Normalmente Fechados em Redes de Distribuição

Tipicamente as redes elétricas de distribuição apresentam uma topologia parcialmente malhada e são exploradas radialmente. A topologia radial é obtida através da abertura das malhas nos locais que otimizam o ponto de operação da rede, através da instalação de aparelhos de corte que operam normalmente abertos. Para além de manterem a topologia radial, estes equipamentos possibilitam também a transferência de cargas entre saídas, aquando da ocorrência de defeitos. As saídas radiais são ainda dotadas de aparelhos de corte que operam normalmente fechados, estes têm como objetivo maximizar a fiabilidade e isolar defeitos, minimizando a área afetada pelos mesmos. Assim, na presente dissertação são desenvolvidos dois algoritmos determinísticos para a localização ótima de aparelhos de corte normalmente abertos e fechados, minimizando a potência ativa de perdas e o custo da energia não distribuída. O algoritmo de localização de aparelhos de corte normalmente abertos visa encontrar a topologia radial ótima que minimiza a potência ativa de perdas. O método é desenvolvido em ambiente Matlab – Tomlab, e é formulado como um problema de programação quadrática inteira mista. A topologia radial ótima é garantida através do cálculo de um trânsito de potências ótimo baseado no modelo DC. A função objetivo é dada pelas perdas por efeito de Joule. Por outro lado o problema é restringido pela primeira lei de Kirchhoff, limites de geração das subestações, limites térmicos dos condutores, trânsito de potência unidirecional e pela condição de radialidade. Os aparelhos de corte normalmente fechados são localizados ao longo das saídas radiais obtidas pelo anterior algoritmo, e permite minimizar o custo da energia não distribuída. No limite é possível localizar um aparelho de corte normalmente fechado em todas as linhas de uma rede de distribuição, sendo esta a solução que minimiza a energia não distribuída. No entanto, tendo em conta que a cada aparelho de corte está associado um investimento, é fundamental encontrar um equilíbrio entre a melhoria de fiabilidade e o investimento. Desta forma, o algoritmo desenvolvido avalia os benefícios obtidos com a instalação de aparelhos de corte normalmente fechados, e retorna o número e a localização dos mesmo que minimiza o custo da energia não distribuída. Os métodos apresentados são testados em duas redes de distribuição reais, exploradas com um nível de tensão de 15 kV e 30 kV, respetivamente. A primeira rede é localizada no distrito do Porto e é caraterizada por uma topologia mista e urbana. A segunda rede é localizada no distrito de Bragança e é caracterizada por uma topologia maioritariamente aérea e rural.

Predicting trabecular bone microdamage initiation and accumulation using a non-linear perfect damage model

Studies evaluating the mechanical behavior of the trabecular microstructure play an important role in our understanding of pathologies such as osteoporosis, and in increasing our understanding of bone fracture and bone adaptation. Understanding of such behavior in bone is important for predicting and providing early treatment of fractures. The objective of this study is to present a numerical model for studying the initiation and accumulation of trabecular bone microdamage in both the pre- and post-yield regions. A sub-region of human vertebral trabecular bone was analyzed using a uniformly loaded anatomically accurate microstructural three-dimensional finite element model. The evolution of trabecular bone microdamage was governed using a non-linear, modulus reduction, perfect damage approach derived from a generalized plasticity stress-strain law. The model introduced in this paper establishes a history of microdamage evolution in both the pre- and post-yield regions

Domain/Multi-Domain Protection and Provisioning in Optical Networks

L’évolution récente des commutateurs de sélection de longueurs d’onde (WSS -Wavelength Selective Switch) favorise le développement du multiplexeur optique d’insertionextraction reconfigurable (ROADM - Reconfigurable Optical Add/Drop Multiplexers) à plusieurs degrés sans orientation ni coloration, considéré comme un équipement fort prometteur pour les réseaux maillés du futur relativement au multiplexage en longueur d’onde (WDM -Wavelength Division Multiplexing ). Cependant, leur propriété de commutation asymétrique complique la question de l’acheminement et de l’attribution des longueur d’ondes (RWA - Routing andWavelength Assignment). Or la plupart des algorithmes de RWA existants ne tiennent pas compte de cette propriété d’asymétrie. L’interruption des services causée par des défauts d’équipements sur les chemins optiques (résultat provenant de la résolution du problème RWA) a pour conséquence la perte d’une grande quantité de données. Les recherches deviennent ainsi incontournables afin d’assurer la survie fonctionnelle des réseaux optiques, à savoir, le maintien des services, en particulier en cas de pannes d’équipement. La plupart des publications antérieures portaient particulièrement sur l’utilisation d’un système de protection permettant de garantir le reroutage du trafic en cas d’un défaut d’un lien. Cependant, la conception de la protection contre le défaut d’un lien ne s’avère pas toujours suffisante en termes de survie des réseaux WDM à partir de nombreux cas des autres types de pannes devenant courant de nos jours, tels que les bris d’équipements, les pannes de deux ou trois liens, etc. En outre, il y a des défis considérables pour protéger les grands réseaux optiques multidomaines composés de réseaux associés à un domaine simple, interconnectés par des liens interdomaines, où les détails topologiques internes d’un domaine ne sont généralement pas partagés à l’extérieur. La présente thèse a pour objectif de proposer des modèles d’optimisation de grande taille et des solutions aux problèmes mentionnés ci-dessus. Ces modèles-ci permettent de générer des solutions optimales ou quasi-optimales avec des écarts d’optimalité mathématiquement prouvée. Pour ce faire, nous avons recours à la technique de génération de colonnes afin de résoudre les problèmes inhérents à la programmation linéaire de grande envergure. Concernant la question de l’approvisionnement dans les réseaux optiques, nous proposons un nouveau modèle de programmation linéaire en nombres entiers (ILP - Integer Linear Programming) au problème RWA afin de maximiser le nombre de requêtes acceptées (GoS - Grade of Service). Le modèle résultant constitue celui de l’optimisation d’un ILP de grande taille, ce qui permet d’obtenir la solution exacte des instances RWA assez grandes, en supposant que tous les noeuds soient asymétriques et accompagnés d’une matrice de connectivité de commutation donnée. Ensuite, nous modifions le modèle et proposons une solution au problème RWA afin de trouver la meilleure matrice de commutation pour un nombre donné de ports et de connexions de commutation, tout en satisfaisant/maximisant la qualité d’écoulement du trafic GoS. Relativement à la protection des réseaux d’un domaine simple, nous proposons des solutions favorisant la protection contre les pannes multiples. En effet, nous développons la protection d’un réseau d’un domaine simple contre des pannes multiples, en utilisant les p-cycles de protection avec un chemin indépendant des pannes (FIPP - Failure Independent Path Protecting) et de la protection avec un chemin dépendant des pannes (FDPP - Failure Dependent Path-Protecting). Nous proposons ensuite une nouvelle formulation en termes de modèles de flots pour les p-cycles FDPP soumis à des pannes multiples. Le nouveau modèle soulève un problème de taille, qui a un nombre exponentiel de contraintes en raison de certaines contraintes d’élimination de sous-tour. Par conséquent, afin de résoudre efficacement ce problème, on examine : (i) une décomposition hiérarchique du problème auxiliaire dans le modèle de décomposition, (ii) des heuristiques pour gérer efficacement le grand nombre de contraintes. À propos de la protection dans les réseaux multidomaines, nous proposons des systèmes de protection contre les pannes d’un lien. Tout d’abord, un modèle d’optimisation est proposé pour un système de protection centralisée, en supposant que la gestion du réseau soit au courant de tous les détails des topologies physiques des domaines. Nous proposons ensuite un modèle distribué de l’optimisation de la protection dans les réseaux optiques multidomaines, une formulation beaucoup plus réaliste car elle est basée sur l’hypothèse d’une gestion de réseau distribué. Ensuite, nous ajoutons une bande pasiv sante partagée afin de réduire le coût de la protection. Plus précisément, la bande passante de chaque lien intra-domaine est partagée entre les p-cycles FIPP et les p-cycles dans une première étude, puis entre les chemins pour lien/chemin de protection dans une deuxième étude. Enfin, nous recommandons des stratégies parallèles aux solutions de grands réseaux optiques multidomaines. Les résultats de l’étude permettent d’élaborer une conception efficace d’un système de protection pour un très large réseau multidomaine (45 domaines), le plus large examiné dans la littérature, avec un système à la fois centralisé et distribué.

Genetic Programming meets Model-Driven Development

Genetic programming is known to provide good solutions for many problems like the evolution of network protocols and distributed algorithms. In such cases it is most likely a hardwired module of a design framework that assists the engineer to optimize specific aspects of the system to be developed. It provides its results in a fixed format through an internal interface. In this paper we show how the utility of genetic programming can be increased remarkably by isolating it as a component and integrating it into the model-driven software development process. Our genetic programming framework produces XMI-encoded UML models that can easily be loaded into widely available modeling tools which in turn posses code generation as well as additional analysis and test capabilities. We use the evolution of a distributed election algorithm as an example to illustrate how genetic programming can be combined with model-driven development. This example clearly illustrates the advantages of our approach – the generation of source code in different programming languages.

Entwicklung und Anwendung einer Kraftwerks- und Speichereinsatzoptimierung für die Untersuchung von Energieversorgungsszenarien mit hohem Anteil erneuerbarer Energien in Deutschland

In dieser Arbeit wurde ein gemischt-ganzzahliges lineares Einsatzoptimierungsmodell für Kraftwerke und Speicher aufgebaut und für die Untersuchung der Energieversorgung Deutschlands im Jahre 2050 gemäß den Leitstudie-Szenarien 2050 A und 2050 C ([Nitsch und Andere, 2012]) verwendet, in denen erneuerbare Energien einen Anteil von über 85 % an der Stromerzeugung haben und die Wind- und Solarenergie starke Schwankungen der durch steuerbare Kraftwerke und Speicher zu deckenden residualen Stromnachfrage (Residuallast) verursachen. In Szenario 2050 A sind 67 TWh Wasserstoff, die elektrolytisch aus erneuerbarem Strom zu erzeugen sind, für den Verkehr vorgesehen. In Szenario 2050 C ist kein Wasserstoff für den Verkehr vorgesehen und die effizientere Elektromobilität hat einen Anteil von 100% am Individualverkehr. Daher wird weniger erneuerbarer Strom zur Erreichung desselben erneuerbaren Anteils im Verkehrssektor benötigt. Da desweiteren Elektrofahrzeuge Lastmanagementpotentiale bieten, weisen die Residuallasten der Szenarien eine unterschiedliche zeitliche Charakteristik und Jahressumme auf. Der Schwerpunkt der Betrachtung lag auf der Ermittlung der Auslastung und Fahrweise des in den Szenarien unterstellten ’Kraftwerks’-parks bestehend aus Kraftwerken zur reinen Stromerzeugung, Kraft-Wärme-Kopplungskraftwerken, die mit Wärmespeichern, elektrischen Heizstäben und Gas-Backupkesseln ausgestattet sind, Stromspeichern und Wärmepumpen, die durch Wärmespeicher zum Lastmanagment eingesetzt werden können. Der Fahrplan dieser Komponenten wurde auf minimale variable Gesamtkosten der Strom- und Wärmeerzeugung über einen Planungshorizont von jeweils vier Tagen hin optimiert. Das Optimierungsproblem wurde mit dem linearen Branch-and-Cut-Solver der software CPLEX gelöst. Mittels sogenannter rollierender Planung wurde durch Zusammensetzen der Planungsergebnisse für überlappende Planungsperioden der Kraftwerks- und Speichereinsatz für die kompletten Szenariojahre erhalten. Es wurde gezeigt, dass der KWK-Anteil an der Wärmelastdeckung gering ist. Dies wurde begründet durch die zeitliche Struktur der Stromresiduallast, die wärmeseitige Dimensionierung der Anlagen und die Tatsache, dass nur eine kurzfristige Speicherung von Wärme vorgesehen war. Die wärmeseitige Dimensionierung der KWK stellte eine Begrenzung des Deckungsanteils dar, da im Winter bei hoher Stromresiduallast nur wenig freie Leistung zur Beladung der Speicher zur Verfügung stand. In den Berechnungen für das Szenario 2050 A und C lag der mittlere Deckungsanteil der KWK an der Wärmenachfrage von ca. 100 TWh_th bei 40 bzw. 60 %, obwohl die Auslegung der KWK einen theoretischen Anteil von über 97 % an der Wärmelastdeckung erlaubt hätte, gäbe es die Beschränkungen durch die Stromseite nicht. Desweiteren wurde die CO2-Vermeidungswirkung der KWK-Wärmespeicher und des Lastmanagements mit Wärmepumpen untersucht. In Szenario 2050 A ergab sich keine signifikante CO2-Vermeidungswirkung der KWK-Wärmespeicher, in Szenario 2050 C hingegen ergab sich eine geringe aber signifikante CO2-Einsparung in Höhe von 1,6 % der Gesamtemissionen der Stromerzeugung und KWK-gebundenen Wärmeversorgung. Das Lastmanagement mit Wärmepumpen vermied Emissionen von 110 Tausend Tonnen CO2 (0,4 % der Gesamtemissionen) in Szenario A und 213 Tausend Tonnen in Szenario C (0,8 % der Gesamtemissionen). Es wurden darüber hinaus Betrachtungen zur Konkurrenz zwischen solarthermischer Nahwärme und KWK bei Einspeisung in dieselben Wärmenetze vorgenommen. Eine weitere Einschränkung der KWK-Erzeugung durch den Einspeisevorrang der Solarthermie wurde festgestellt. Ferner wurde eine untere Grenze von 6,5 bzw. 8,8 TWh_th für die in den Szenarien mindestens benötigte Wasserstoff-Speicherkapazität ermittelt. Die Ergebnisse dieser Arbeit legen nahe, das technisch-ökonomische Potential von Langzeitwärmespeichern für eine bessere Integration von KWK ins System zu ermitteln bzw. generell nach geeigneteren Wärmesektorszenarien zu suchen, da deutlich wurde, dass für die öffentliche Wärmeversorgung die KWK in Kombination mit Kurzzeitwärmespeicherung, Gaskesseln und elektrischen Heizern keine sehr effektive CO2 -Reduktion in den Szenarien erreicht. Es sollte dabei z.B. untersucht werden, ob ein multivalentes System aus KWK, Wärmespeichern und Wärmepumpen eine ökonomisch darstellbare Alternative sein könnte und im Anschluss eine Betrachtung der optimalen Anteile von KWK, Wärmepumpen und Solarthermie im Wärmemarkt vorgenommen werden.