Application-Specific Modified Particle Swarm Optimization for energy resource scheduling considering vehicle-to-grid

This paper presents a modified Particle Swarm Optimization (PSO) methodology to solve the problem of energy resources management with high penetration of distributed generation and Electric Vehicles (EVs) with gridable capability (V2G). The objective of the day-ahead scheduling problem in this work is to minimize operation costs, namely energy costs, regarding the management of these resources in the smart grid context. The modifications applied to the PSO aimed to improve its adequacy to solve the mentioned problem. The proposed Application Specific Modified Particle Swarm Optimization (ASMPSO) includes an intelligent mechanism to adjust velocity limits during the search process, as well as self-parameterization of PSO parameters making it more user-independent. It presents better robustness and convergence characteristics compared with the tested PSO variants as well as better constraint handling. This enables its use for addressing real world large-scale problems in much shorter times than the deterministic methods, providing system operators with adequate decision support and achieving efficient resource scheduling, even when a significant number of alternative scenarios should be considered. The paper includes two realistic case studies with different penetration of gridable vehicles (1000 and 2000). The proposed methodology is about 2600 times faster than Mixed-Integer Non-Linear Programming (MINLP) reference technique, reducing the time required from 25 h to 36 s for the scenario with 2000 vehicles, with about one percent of difference in the objective function cost value.

Esclonamento de máquinas de cogeração utilzando programação inteira mista

As centrais termoelétricas convencionais convertem apenas parte do combustível consumido na produção de energia elétrica, sendo que outra parte resulta em perdas sob a forma de calor. Neste sentido, surgiram as unidades de cogeração, ou Combined Heat and Power (CHP), que permitem reaproveitar a energia dissipada sob a forma de energia térmica e disponibilizá-la, em conjunto com a energia elétrica gerada, para consumo doméstico ou industrial, tornando-as mais eficientes que as unidades convencionais Os custos de produção de energia elétrica e de calor das unidades CHP são representados por uma função não-linear e apresentam uma região de operação admissível que pode ser convexa ou não-convexa, dependendo das caraterísticas de cada unidade. Por estas razões, a modelação de unidades CHP no âmbito do escalonamento de geradores elétricos (na literatura inglesa Unit Commitment Problem (UCP)) tem especial relevância para as empresas que possuem, também, este tipo de unidades. Estas empresas têm como objetivo definir, entre as unidades CHP e as unidades que apenas geram energia elétrica ou calor, quais devem ser ligadas e os respetivos níveis de produção para satisfazer a procura de energia elétrica e de calor a um custo mínimo. Neste documento são propostos dois modelos de programação inteira mista para o UCP com inclusão de unidades de cogeração: um modelo não-linear que inclui a função real de custo de produção das unidades CHP e um modelo que propõe uma linearização da referida função baseada na combinação convexa de um número pré-definido de pontos extremos. Em ambos os modelos a região de operação admissível não-convexa é modelada através da divisão desta àrea em duas àreas convexas distintas. Testes computacionais efetuados com ambos os modelos para várias instâncias permitiram verificar a eficiência do modelo linear proposto. Este modelo permitiu obter as soluções ótimas do modelo não-linear com tempos computationais significativamente menores. Para além disso, ambos os modelos foram testados com e sem a inclusão de restrições de tomada e deslastre de carga, permitindo concluir que este tipo de restrições aumenta a complexidade do problema sendo que o tempo computacional exigido para a resolução do mesmo cresce significativamente.

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

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

Choix d'un associateur 2-D pour le balayage multiple et optimisation de l'estimation des pistes

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Strategy-proofness makes the difference: deferred-acceptance with responsive priorities

In college admissions and student placements at public schools, the admission decision can be thought of as assigning indivisible objects with capacity constraints to a set of students such that each student receives at most one object and monetary compensations are not allowed. In these important market design problems, the agent-proposing deferred-acceptance (DA-)mechanism with responsive strict priorities performs well and economists have successfully implemented DA-mechanisms or slight variants thereof. We show that almost all real-life mechanisms used in such environments - including the large classes of priority mechanisms and linear programming mechanisms - satisfy a set of simple and intuitive properties. Once we add strategy-proofness to these properties, DA-mechanisms are the only ones surviving. In market design problems that are based on weak priorities (like school choice), generally multiple tie-breaking (MTB)procedures are used and then a mechanism is implemented with the obtained strict priorities. By adding stability with respect to the weak priorities, we establish the first normative foundation for MTB-DA-mechanisms that are used in NYC.

Contribution à l’élaboration d’un guide alimentaire béninois : approche par la programmation linéaire et validation sur le terrain

Contexte: Le Bénin est atteint par le double fardeau nutritionnel : dans le même pays, et parfois dans le même ménage, il y a des personnes malnutries et d’autres aux prises avec des maladies chroniques. Ces conditions, au moins pour partie, peuvent être prévenues si la population est sensibilisée à de bonnes habitudes alimentaires. Pour ce faire, les professionnels de la santé ont besoin d’outils comme un guide alimentaire (GA) pour faciliter l’apprentissage de bonnes pratiques alimentaires. Ce dernier nécessite plusieurs étapes à son élaboration, dont la définition des groupes alimentaires, la présentation visuelle et la quantification des portions d'aliments. Objectif : Ce travail a eu pour but de proposer et d’homologuer des portions quotidiennes d’aliments dans chaque groupe alimentaire pour différents groupes d’âge de Béninois. Méthode : Elle consiste à : 1) Caractériser la consommation alimentaire locale; 2) Optimiser le profil moyen de consommation alimentaire quotidienne à l’aide de la programmation linéaire (PL); 3) Traduire les résultats en termes de nombre et taille de portions d’aliments de chaque groupe à consommer quotidiennement; 4) Illustrer les recommandations au moyen d’exemples de menus journaliers; 5) Homologuer le prototype du GA avec des experts béninois. La PL a permis de déterminer les choix d’aliments et quantités optimales à recommander à partir des enquêtes transversales récentes et des recommandations nutritionnelles de l’OMS. Résultats : Les quantités et portions d'aliments recommandées à la consommation ont été déterminées. Les résultats ont été partagés avec les personnes-ressources en nutrition au Bénin. Le premier prototype du GA a été développé pour restitution subséquente aux autorités du Bénin.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

On the generalized obnoxious center problem: antimedian subsets

The set of vertices that maximize (minimize) the remoteness is the antimedian (median) set of the profile. It is proved that for an arbitrary graph G and S V (G) it can be decided in polynomial time whether S is the antimedian set of some profile. Graphs in which every antimedian set is connected are also considered.

Szenarien zur zukünftigen Stromversorgung, kostenoptimierte Variationen zur Versorgung Europas und seiner Nachbarn mit Strom aus erneuerbaren Energien

Sowohl die Ressourcenproblematik als auch die drohenden Ausmaße der Klimaänderung lassen einen Umstieg auf andere Energiequellen langfristig unausweichlich erscheinen und mittelfristig als dringend geboten. Unabhängig von der Frage, auf welchem Niveau sich der Energiebedarf stabilisieren lässt, bleibt dabei zu klären, welche Möglichkeiten sich aus technischer und wirtschaftlicher Sicht in Zukunft zur Deckung unseres Energiebedarfs anbieten. Eine aussichtsreiche Option besteht in der Nutzung regenerativer Energien in ihrer ganzen Vielfalt. Die Arbeit "Szenarien zur zukünftigen Stromversorgung, kostenoptimierte Variationen zur Versorgung Europas und seiner Nachbarn mit Strom aus erneuerbaren Energien" konzentriert sich mit der Stromversorgung auf einen Teilaspekt der Energieversorgung, der zunehmend an Wichtigkeit gewinnt und als ein Schlüssel zur nachhaltigen Energieversorgung interpretiert werden kann. Die Stromversorgung ist heute weltweit für etwa die Hälfte des anthropogenen CO2-Ausstoßes verantwortlich. In dieser Arbeit wurden anhand verschiedener Szenarien Möglichkeiten einer weitgehend CO2–neutralen Stromversorgung für Europa und seine nähere Umgebung untersucht, wobei das Szenariogebiet etwa 1,1 Mrd. Einwohner und einen Stromverbrauch von knapp 4000 TWh/a umfasst. Dabei wurde untersucht, wie die Stromversorgung aufgebaut sein sollte, damit sie möglichst kostengünstig verwirklicht werden kann. Diese Frage wurde beispielsweise für Szenarien untersucht, in denen ausschließlich heute marktverfügbare Techniken berücksichtigt wurden. Auch der Einfluss der Nutzung einiger neuer Technologien, die bisher noch in Entwicklung sind, auf die optimale Gestaltung der Stromversorgung, wurde anhand einiger Beispiele untersucht. Die Konzeption der zukünftigen Stromversorgung sollte dabei nach Möglichkeit objektiven Kriterien gehorchen, die auch die Vergleichbarkeit verschiedener Versorgungsansätze gewährleisten. Dafür wurde ein Optimierungsansatz gewählt, mit dessen Hilfe sowohl bei der Konfiguration als auch beim rechnerischen Betrieb des Stromversorgungssystems weitgehend auf subjektive Entscheidungsprozesse verzichtet werden kann. Die Optimierung hatte zum Ziel, für die definierte möglichst realitätsnahe Versorgungsaufgabe den idealen Kraftwerks- und Leitungspark zu bestimmen, der eine kostenoptimale Stromversorgung gewährleistet. Als Erzeugungsoptionen werden dabei u.a. die Nutzung Regenerativer Energien durch Wasserkraftwerke, Windenergiekonverter, Fallwindkraftwerke, Biomassekraftwerke sowie solare und geothermische Kraftwerke berücksichtigt. Abhängig von den gewählten Randbedingungen ergaben sich dabei unterschiedliche Szenarien. Das Ziel der Arbeit war, mit Hilfe unterschiedlicher Szenarien eine breite Basis als Entscheidungsgrundlage für zukünftige politische Weichenstellungen zu schaffen. Die Szenarien zeigen Optionen für eine zukünftige Gestaltung der Stromversorgung auf, machen Auswirkungen verschiedener – auch politischer – Rahmenbedingungen deutlich und stellen so die geforderte Entscheidungsgrundlage bereit. Als Grundlage für die Erstellung der Szenarien mussten die verschiedenen Potentiale erneuerbarer Energien in hoher zeitlicher und räumlicher Auflösung ermittelt werden, mit denen es erstmals möglich war, die Fragen einer großräumigen regenerativen Stromversorgung ohne ungesicherte Annahmen anhand einer verlässlichen Datengrundlage anzugehen. Auch die Charakteristika der verschiedensten Energiewandlungs- und Transportsysteme mussten studiert werden und sind wie deren Kosten und die verschiedenen Potentiale in der vorliegenden Arbeit ausführlich diskutiert. Als Ausgangsszenario und Bezugspunkt dient ein konservatives Grundszenario. Hierbei handelt es sich um ein Szenario für eine Stromversorgung unter ausschließlicher Nutzung erneuerbarer Energien, die wiederum ausschließlich auf heute bereits entwickelte Technologien zurückgreift und dabei für alle Komponenten die heutigen Kosten zugrundelegt. Dieses Grundszenario ist dementsprechend auch als eine Art konservative Worst-Case-Abschätzung für unsere Zukunftsoptionen bei der regenerativen Stromversorgung zu verstehen. Als Ergebnis der Optimierung basiert die Stromversorgung beim Grundszenario zum größten Teil auf der Stromproduktion aus Windkraft. Biomasse und schon heute bestehende Wasserkraft übernehmen den überwiegenden Teil der Backup-Aufgaben innerhalb des – mit leistungsstarker HGÜ (Hochspannungs–Gleichstrom–Übertragung) verknüpften – Stromversorgungsgebiets. Die Stromgestehungskosten liegen mit 4,65 €ct / kWh sehr nahe am heute Üblichen. Sie liegen niedriger als die heutigen Preisen an der Strombörse. In allen Szenarien – außer relativ teuren, restriktiv ”dezentralen” unter Ausschluss großräumig länderübergreifenden Stromtransports – spielt der Stromtransport eine wichtige Rolle. Er wird genutzt, um Ausgleichseffekte bei der dargebotsabhängigen Stromproduktion aus erneuerbaren Quellen zu realisieren, gute kostengünstige Potentiale nutzbar zu machen und um die Speicherwasserkraft sowie die dezentral genutzte Biomasse mit ihrer Speicherfähigkeit für großräumige Backup-Aufgaben zu erschließen. Damit erweist sich der Stromtransport als einer der Schlüssel zu einer kostengünstigen Stromversorgung. Dies wiederum kann als Handlungsempfehlung bei politischen Weichenstellungen interpretiert werden, die demnach gezielt auf internationale Kooperation im Bereich der Nutzung erneuerbarer Energien setzen und insbesondere den großräumigen Stromtransport mit einbeziehen sollten. Die Szenarien stellen detaillierte und verlässliche Grundlagen für wichtige politische und technologische Zukunftsentscheidungen zur Verfügung. Sie zeigen, dass bei internationaler Kooperation selbst bei konservativen Annahmen eine rein regenerative Stromversorgung möglich ist, die wirtschaftlich ohne Probleme zu realisieren wäre und verweisen den Handlungsbedarf in den Bereich der Politik. Eine wesentliche Aufgabe der Politik läge darin, die internationale Kooperation zu organisieren und Instrumente für eine Umgestaltung der Stromversorgung zu entwickeln. Dabei kann davon ausgegangen werden, dass nicht nur ein sinnvoller Weg zu einer CO2–neutralen Stromversorgung beschritten würde, sondern sich darüber hinaus ausgezeichnete Entwicklungsperspektiven für die ärmeren Nachbarstaaten der EU und Europas eröffnen.

Uncertainty Propagation in Model-Based Recognition

Building robust recognition systems requires a careful understanding of the effects of error in sensed features. Error in these image features results in a region of uncertainty in the possible image location of each additional model feature. We present an accurate, analytic approximation for this uncertainty region when model poses are based on matching three image and model points, for both Gaussian and bounded error in the detection of image points, and for both scaled-orthographic and perspective projection models. This result applies to objects that are fully three- dimensional, where past results considered only two-dimensional objects. Further, we introduce a linear programming algorithm to compute the uncertainty region when poses are based on any number of initial matches. Finally, we use these results to extend, from two-dimensional to three- dimensional objects, robust implementations of alignmentt interpretation- tree search, and ransformation clustering.

Operational Cost Reduction in WDM Networks using Lighttours

Wavelength division multiplexing (WDM) networks have been adopted as a near-future solution for the broadband Internet. In previous work we proposed a new architecture, named enhanced grooming (G+), that extends the capabilities of traditional optical routes (lightpaths). In this paper, we compare the operational expenditures incurred by routing a set of demands using lightpaths with that of lighttours. The comparison is done by solving an integer linear programming (ILP) problem based on a path formulation. Results show that, under the assumption of single-hop routing, almost 15% of the operational cost can be reduced with our architecture. In multi-hop routing the operation cost is reduced in 7.1% and at the same time the ratio of operational cost to number of optical-electro-optical conversions is reduced for our architecture. This means that ISPs could provide the same satisfaction in terms of delay to the end-user with a lower investment in the network architecture

G+: Enhanced Traffic Grooming in WDM Mesh Networks using Lighttours

In this article, a new technique for grooming low-speed traffic demands into high-speed optical routes is proposed. This enhancement allows a transparent wavelength-routing switch (WRS) to aggregate traffic en route over existing optical routes without incurring expensive optical-electrical-optical (OEO) conversions. This implies that: a) an optical route may be considered as having more than one ingress node (all inline) and, b) traffic demands can partially use optical routes to reach their destination. The proposed optical routes are named "lighttours" since the traffic originating from different sources can be forwarded together in a single optical route, i.e., as taking a "tour" over different sources towards the same destination. The possibility of creating lighttours is the consequence of a novel WRS architecture proposed in this article, named "enhanced grooming" (G+). The ability to groom more traffic in the middle of a lighttour is achieved with the support of a simple optical device named lambda-monitor (previously introduced in the RingO project). In this article, we present the new WRS architecture and its advantages. To compare the advantages of lighttours with respect to classical lightpaths, an integer linear programming (ILP) model is proposed for the well-known multilayer problem: traffic grooming, routing and wavelength assignment The ILP model may be used for several objectives. However, this article focuses on two objectives: maximizing the network throughput, and minimizing the number of optical-electro-optical conversions used. Experiments show that G+ can route all the traffic using only half of the total OEO conversions needed by classical grooming. An heuristic is also proposed, aiming at achieving near optimal results in polynomial time

Adding new components to the knowledge plane GMPLS over WDM networks

A recent study defines a new network plane: the knowledge plane. The incorporation of the knowledge plane over the network allows having more accurate information of the current and future network states. In this paper, the introduction and management of the network reliability information in the knowledge plane is proposed in order to improve the quality of service with protection routing algorithms in GMPLS over WDM networks. Different experiments prove the efficiency and scalability of the proposed scheme in terms of the percentage of resources used to protect the network

MA230exam00

Exam questions and solutions in LaTex

MA230exam01pdf

Exam questions and solutions in PDF