L'objectif de cette thèse consiste à présenter un nouvel algorithme pour la programmation non linéaire en nombres entiers, inspirée par la méthode Multiplicative Weights Update et qui compte sur une nouvelle classe de reformulations, appelées les reformulations ponctuelles.La programmation non linéaire en nombres entiers est un sujet très difficile et fascinant dans le domaine de l'optimisation mathématique à la fois d'un point de vue théorique et computationnel. Il est possible de formuler de nombreux problèmes dans ce schéma général et, habituellement, ils posent de réels défis en termes d'efficacité et de précision de la solution obtenue quant aux procédures de résolution.La thèse est divisée en trois parties principales : une introduction composée par le Chapitre 1, une définition théorique du nouvel algorithme dans le Chapitre 2 et l'application de cette nouvelle méthodologie à deux problèmes concrets d'optimisation, tels que la sélection optimale du portefeuille avec le critère moyenne-variance dans le Chapitre 3 et le problème du sac à dos non linéaire dans le Chapitre 4. Conclusions et questions ouvertes sont présentées dans le Chapitre 5. / This thesis presents a new algorithm for Mixed Integer NonLinear Programming, inspired by the Multiplicative Weights Update framework and relying on a new class of reformulations, called the pointwise reformulations.Mixed Integer NonLinear Programming is a hard and fascinating topic in Mathematical Optimization both from a theoretical and a computational viewpoint. Many real-word problems can be cast this general scheme and, usually, are quite challenging in terms of efficiency and solution accuracy with respect to the solving procedures.The thesis is divided in three main parts: a foreword consisting in Chapter 1, a theoretical foundation of the new algorithm in Chapter 2, and the application of this new methodology to two real-world optimization problems, namely the Mean-Variance Portfolio Selection in Chapter 3, and the Multiple NonLinear Separable Knapsack Problem in Chapter 4. Conclusions and open questions are drawn in Chapter 5.

No description available.

The quadratic traveling salesman problem (QTSP) is an extension of the (classical) Traveling Salesman Problem (TSP) where the costs depend on each two nodes that are traversed in succession, i. e., on the edges in the symmetric (STSP) and on the arcs in the asymmetric case (ATSP). The QTSP is motivated by an application in bioinformatics. It can be used in the solution of certain Permuted Markov models that are set up for the recognition of transcription factor binding sites and of splice sites in gene regulation. Important special cases are the Angular-Metric TSP used in robotics and the TSP with Reload Costs used in the planning of telecommunication and transport networks. The SQTSP and the AQTSP can be formulated as integer optimization problems over the polytope associated with the STSP resp. ATSP together with a quadratic cost function. We study the polytopes arising from a linearization of the respective quadratic integer programming formulations. Based on the proof of the dimension of the polytopes using the so called direct method we can prove the facetness of several valid inequalities. These facets and valid inequalities can be divided into three large groups. Some are related to the Boolean quadric polytope. Furthermore we introduce the conflicting edges/arc inequalities that forbid certain configurations of edges and 2-edges resp. of arcs and 2-arcs. Finally, we strengthen valid inequalities of STSP and ATSP in order to get stronger inequalities in the quadratic case. We present two general lifting approaches. One is applicable to all inequalities with nonnegative coefficients and the second allows to strengthen clique tree inequalities. Applying these approaches to the subtour elimination constraints leads to facets in most cases, but in general facetness is not preserved. In addition, the complexity of the separation problems for some of the facet classes is studied. Finally, we present some computational results using a branch-and-cut framework, which is improved by some of the newly derived cutting planes. The tested instances from biology could be solved surprisingly well. Instances with up to 100 nodes could be solved in less than 700 seconds improving the results in the literature by several orders of magnitude. For most of the randomly generated instances using some additional separators allowed to reduce the root gaps and the numbers of nodes in the branch-and-cut tree significantly, often even the running times.

Optical microcavities (OMs) are receiving increasing attention owing to their potential applications ranging from cavity quantum electrodynamics, optical detection to photonic devices. Recently, rolled-up structures have been demonstrated as OMs which have gained considerable attention owing to their excellent customizability. To fully exploit this customizability, asymmetric and topological rolled-up OMs are proposed and investigated in addition to conventional rolled-up OMs in this thesis. By doing so, novel phenomena and applications are demonstrated in OMs. The fabrication of conventional rolled-up OMs is presented in details. Then, dynamic mode tuning by a near-field probe is performed on a conventional rolled-up OM. Next, mode splitting in rolled-up OMs is investigated. The effect of single nanoparticles on mode splitting in a rolled-up OM is studied. Because of a non-synchronized oscillating shift for different azimuthal split modes induced by a single nanoparticle at different positions, the position of the nanoparticle can be determined on the rolled-up OM. Moreover, asymmetric rolled-up OMs are fabricated for the purpose of introducing coupling between spin and orbital angular momenta (SOC) of light into OMs. Elliptically polarized modes are observed due to the SOC of light. Modes with an elliptical polarization can also be modeled as coupling between the linearly polarized TE and TM mode in asymmetric rolled-up OMs. Furthermore, by adding a helical geometry to rolled-up structures, Berry phase of light is introduced into OMs. A -π Berry phase is generated for light in topological rolled-up OMs so that modes have a half-integer number of wavelengths. In order to obtain a deeper understanding for existing rolled-up OMs and to develop the new type of rolled-up OMs, complete theoretical models are also presented in this thesis.

Elektronische und elektrische Systeme stellen seit einigen Jahren einen zunehmenden Anteil an den Gesamtproduktionskosten von Personenkraftfahrzeugen. Laut Prognosen wird sich diese Entwicklung zwar abschwächen, jedoch wird der Wertschöpfungsanteil der Elektronik am Fahrzeug weiter zunehmen. Die hier vorliegende Arbeit beschäftigt sich mit leistungselektronischen Subsystemen in PKW, die aufgrund der benötigten Chipfläche der Halbleiter kostenintensiv sind. Ziel der Arbeit ist es, Strukturen zu entwickeln und zu untersuchen, die es ermöglichen, mehrere Verbraucher in einer solchen Struktur zu betreiben und dadurch Leistungshalbleiter einzusparen. In einer Analyse werden die derzeitige Struktur der Verbraucher im Fahrzeug, die dazugehö-rige Elektronik und die zeitlichen Abhängigkeiten der Verbraucher untereinander dargestellt. Die Analyse kommt zu dem Schluss, dass die Verbraucher im Fahrzeug auf den jeweiligen Einsatzzweck hin optimiert sind. Dadurch sind sie kostengünstig und einfach aufgebaut. Ge-meinsamkeiten, die für eine Vereinheitlichung der Leistungselektronik genutzt werden kön-nen, können unter Beachtung der betrachteten Systeme gefunden werden. Daraus werden Anforderungen an alternative leistungselektronische Strukturen formuliert. In der Arbeit werden zwei leistungselektronische Schaltungen untersucht, die den Forderun-gen nach einer Einsparung von Leistungshalbleitern gerecht werden. Bei der matrixförmigen Vernetzungsschaltung sind die Versorgungsleitungen in Zeilen und Spalten angeordnet, zwi-schen denen die Verbraucher angeschlossen sind. Bei der linearen Vernetzungsschaltung be-nutzen alle an einer Struktur angeschlossenen Verbraucher teilweise eine gemeinsame und eine individuelle Leistungselektronik. Dabei wird ein geringerer Vernetzungsgrad erreicht. Bei der matrixförmigen Vernetzungsschaltung wird ein hoher Vernetzungsgrad erzielt. Hier-bei kann eine Vielzahl von Verbrauchern mit vergleichsweise wenig Leistungselektronik be-trieben werden. Der hohe Vernetzungsgrad hat Bedingungen an die Anordnung der in der Struktur befindlichen Verbraucher zur Folge, die es nur bei kleinen Strukturen ermöglichen ohne Hilfsmittel eine optimale Struktur zu entwerfen. Für größere Strukturen werden Me-thoden benötigt, um die Anordnung der Verbraucher so zu gestalten, dass die Bedingungen an den gleichzeitigen Betrieb in der Applikation erfüllt werden können. Diese Aufgabe entspricht dem mathematischen Problemkreis der kombinatorischen Optimierung. Als Lösungsmethoden werden die Ganzzahlige Lineare Programmierung, die in jedem Fall ein exaktes Ergebnis er-reicht, und Genetische Algorithmen verwendet, die auch bei sehr großen Strukturen ein opti-miertes Ergebnis erzielen können. Die Genetischen Algorithmen werden in dieser Arbeit auf das Problem und dessen Darstellung angepasst, und die Ergebnisse der Optimierung mit de-nen der exakten Verfahren verglichen. Ergebnisse zeigen, dass die auf die Problemstellung angepassten Genetischen Algorithmen mit hoher Sicherheit das globale Optimum finden. Es werden matrixförmige und lineare Strukturen für eine Sitzsteuerung und eine Klappen-verstellung einer Klimaanlage entworfen, mit den beschriebenen Methoden optimiert und nachfolgend bewertet. In der Bewertung wird gezeigt, dass die entworfenen alternativen Strukturen den konventionellen teilweise überlegen sind und je nach elektronischem System zu einer deutlichen Kosteneinsparung führen können. In den untersuchten Systemen hat sich die lineare Struktur als besonders vorteilhaft herausgestellt.

The purpose of this thesis is to investigate how tractor swapping can be implemented in Vehicle Routing Problems (VRP) with electric heavy goods vehicles, and to evaluate how a model that allows for tractor swapping performs, in terms of schedule cost, against a model that does not. Hence, this thesis introduces a new rich VRP variant which includes tractor swapping, as well as time windows, pickup and delivery, and electric vehicles. The model is named Electric Tractor Swap Vehicle Routing Problem (E-TSVRP) and is formulated as a mixed integer linear program. As for the solver, Gurobi is used. The results show that utilizing tractor swapping can reduce the total cost of serving customers significantly by reducing en-route charging and utilizing drivers more efficiently. Specifically, it is shown that the cost reduction comes mainly from reducing driver work time. By demonstrating how tractor swapping works and how the results can be visualized on smaller cases, this thesis aims to serve as a foundation for future research within the field. To be able to fully implement the model for large logistics problem instances however, alternative solution methods such as heuristics or metaheuristics should be developed so that the problems can be solved in a reasonable amount of time. / Syftet med denna uppsats är att undersöka hur traktorbyten kan implementeras i "Vehicle Routing Problem" (VRP) med tunga, elektriska lastfordon, och att utvärdera hur en modell som tillåter traktorbyten presterar mot en modell som inte tillåter det, med avseende på den totala schemakostnaden. I uppsatsen introduceras därför en ny och generell VRP som har stöd för traktorbyten, men som också modellerar energikonsumtion och laddning av elektriska lastbilar, samt tillåter tidsfönster för när leveranser kan levereras och hämtas upp på godtyckliga platser. Modellen kallas för "Electric Tractor Swap Vehicle Routing Problem" (E-TSVRP) och formuleras som ett linjärt, blandat heltalsprogram. Programmet löses sedan med lösaren Gurobi. Resultaten visar att utnyttjandet av traktorbyten kan märkbart minska den totala kostnaden av att leverera varor till kunder genom att minska tiden som föraren väntar på att traktorn laddar. Mer specifikt tillåts möjligheten att byta till en ny traktor när den tidigare får slut på energi, vilket möjliggör en högre utnyttjandegrad av förarna, och den fakturerade tiden associerad till förarna kan minskas. Detta sker genom en avvägning mellan å ena sidan högre hårdvarukostnader för fler traktorer och å andra sidan lägre förarkostnader. Genom att demonstrera hur traktorbyten fungerar och hur resultaten kan visualiseras på mindre transportproblem, strävar denna uppsats efter att verka som en grund för framtida forskning. För att modellen ska kunna användas för stora logistikproblem bör dock alternativa lösningsmetoder som till exempel lösningsheuristiker eller metaheuristiker utvecklas så att problemen kan lösas inom en rimlig tid.

This thesis addresses route planning of Battery Electric Heavy-Duty Commercial Vehicles to enhance the reliability of electric vehicle transport. Collaborating with Scania, a Swedish truck manufacturing company, the goal is to develop a pipeline that uses open source data from OpenStreetMap and performs a modified Contraction Hierarchy in order to create a graph that can be used as input to a modified Vehicle Routing Problem formulation using Mixed Integer Programming. The input graph is preprocessed to support a Battery Electric Heavy-Duty Commercial Vehicle model in order to more accurately predict energy consumption. The challenges lie in balancing computational efficiency and electric vehicle characteristics. The implemented pipeline demonstrates success but initial tests show that a naive version of the pipeline, not implementing Contraction Hierarchies, can perform better. Several speedups can be made in order to improve the efficiency of the pipeline, the main being in programming in a more efficient programming language than Python. Further testing is needed for larger input graphs to assess performance accurately.

Historically, electricity supply was heavily centralized and was provided by conventional thermal power plants such as coal-fired, gas, or nuclear power plants. The share of conventional power generation is being increasingly replaced by power generation from renewable sources. In Europe, the share of electricity generation from fossil fuels fell from 49% in 2011 to 37% in 2020, whereas the share from renewables increased from 22% to 38% during the same timeframe. Renewable generation is expected to rise by 10% annually to almost triple the current renewable capacity by 2030. The accelerating adoption of renewables changes the character of the electricity infrastructure from a centralized energy supply to a highly decentralized one, such that generation is moving closer to the point of demand. This change brings numerous challenges with it. This work focuses on challenges in operational planning of distributed energy resources from the perspective of so-called aggregators that are increasingly participating in energy markets. Aggregators combine different energy resources, i.e., electricity producers and consumers, and operate them as a distributed power plant. However, the planning of the energy resources is still coordinated collectively in a centralized manner by the aggregator. This work aims to develop a framework to schedule energy resources from the perspective of an aggregator to cover a large variety of technical assets and to simultaneously consider market interactions such as bid acceptance and rejection possibilities. The inevitable and accelerating proliferation of renewable energy resources brings with it -- as a consequence of its intermittency -- a growing need in control reserve and storage technologies. Hence, a focus is placed on control reserve, energy storage, and integrated scheduling and bidding, as well as their trade-offs, to answer the following research questions: 1) What is the current state of control reserve formulations and how can they be improved? Specifically regarding reserve under consideration of limitations with respect to the rate of change of power output, maximum power output, and energy capacity. 2) What are the effects of using different control reserve formulations? 3) Which trade-offs exist in the operation of storage plants in a market environment? 4) Is it possible to derive a rigorous, tractable mathematical model to simultaneously determine scheduling and bidding decisions? 5) Which trade-offs exist between scheduling and bidding decisions and what are their effects? 6) To what extent is it possible to solve energy resource scheduling models faster while retaining sufficiently high solution quality? / In der Vergangenheit war die Stromerzeugung stark zentralisiert und wurde durch konventionelle Kraftwerke wie Kohle-, Gas- oder Kernkraftwerke bereitgestellt. Der Anteil der konventionellen Stromerzeugung wird zunehmend durch die Stromerzeugung aus erneuerbaren Quellen ersetzt. In Europa sank der Anteil der Stromerzeugung aus fossilen Brennstoffen von 49% im Jahr 2011 auf 37% im Jahr 2020, während der Anteil der erneuerbaren Energien im gleichen Zeitraum von 22% auf 38% anstieg. Es wird erwartet, dass die Stromerzeugung aus erneuerbaren Energien jährlich um 10 % steigt und sich die derzeitige Kapazität bis 2030 fast verdreifacht. Die zunehmende Einführung erneuerbarer Energien verändert den Charakter der Elektrizitätsinfrastruktur von einer zentralisierten zu einer stark dezentralisierten Energieversorgung, so dass die Erzeugung näher an den Ort des Bedarfs rückt. Dieser Wandel bringt zahlreiche Herausforderungen mit sich. Diese Arbeit konzentriert sich auf die Herausforderungen bei der Betriebsplanung dezentraler Energieanlagen aus der Perspektive sogenannter Aggregatoren, die zunehmend an den Energiemärkten teilnehmen. Aggregatoren fassen verschiedene Energieanlagen, d.h. Stromerzeuger und -verbraucher, zusammen und betreiben sie als dezentrales Kraftwerk. Die Planung der Energieressourcen wird jedoch weiterhin zentral durch den Aggregator koordiniert. Diese Arbeit zielt darauf ab, ein Framework für die Planung von Energieressourcen aus der Sicht eines Aggregators zu entwickeln, um eine große Vielfalt an technischen Anlagen abzudecken und gleichzeitig Marktinteraktionen wie Gebotsannahme- und Ablehnungsmöglichkeiten zu berücksichtigen. Der unvermeidliche und zunehmende Ausbau von erneuerbaren Energieressourcen bringt -- als Folge ihrer Unstetigkeit -- einen wachsenden Bedarf an Regelleistung- und Speichertechnologien mit sich. Daher liegt der Schwerpunkt auf Regelleistung, Energiespeicherung und integrierter Anlagen- und Gebotsplanung sowie deren Trade-offs, um die folgenden Forschungsfragen zu beantworten: 1) Was ist der aktuelle Stand von Regelleistungsmodellen und wie können diese verbessert werden? Insbesondere im Hinblick auf Regelleistung unter Berücksichtigung von Einschränkungen hinsichtlich der Änderungsrate der Leistungsabgabe, der maximalen Leistungsabgabe und der Energiekapazität. 2) Welche Auswirkungen hat die Verwendung unterschiedlicher Regelleistungsmodelle? 3) Welche Zielkonflikte bestehen beim Betrieb von Speicheranlagen in einem Marktumfeld? 4) Ist es möglich, ein rigoroses, praktikables mathematisches Modell zur gleichzeitigen Bestimmung von Anlagen- und Gebotsplanung aufzustellen? 5) Welche Zielkonflikte bestehen zwischen Anlagen- und Gebotsplanung und welche Auswirkungen haben sie? 6) Inwieweit ist es möglich, Modelle zur Planung von Energieressourcen schneller zu lösen und dabei eine ausreichend hohe Lösungsqualität beizubehalten?

In contexts involving multiple agents (players), determining how they can cooperate through the formation of coalitions and how they can share surplus benefits coming from the collaboration is crucial. This can provide decision-aid to players and analysis tools for policy makers regulating economic markets. Such settings belong to the field of cooperative game theory. A critical element in this area has been the size of the representation of these games: for each possible partition of players, the value of each coalition on it must be provided. Symmetric partition function form games (SPFGs) belong to a class of cooperative games with two important characteristics. First, they account for externalities provoked by any group of players joining forces or splitting into subsets on the remaining coalitions of players. Second, they consider that players are indistinct, meaning that only the number of players in each coalition is relevant for the SPFG. Using mixed-integer programming, we present the first representation of SPFGs that is polynomial on the number of players in the game. We also characterize the family of SPFGs that we can represent. In particular, the representation is able to encode exactly all SPFGs with five players or less. Furthermore, we provide a compact representation approximating SPFGs when there are six players or more and the SPFG cannot be represented exactly. We also introduce a flexible framework that uses stability methods inspired from the literature to identify a stable social-welfare maximizing game outcome using our representation. We showcase the value of our compact (approximated) representation and approach to determine a stable partition and payoff allocation to a competitive market from the literature. / Dans tout contexte impliquant plusieurs agents (joueurs), il est impératif de déterminer comment les agents coopéreront par la formation de coalitions et comment ils partageront les bénéfices supplémentaires issus de la collaboration. Ceci peut fournir une aide à la décision aux joueurs, ou encore des outils d'analyse pour les responsables en charge de réguler les marchés économiques. De telles situations relèvent de la théorie des jeux coopérative. Un élément crucial de ce domaine est la taille de la représentation de ces jeux : pour chaque partition de joueurs possible, la valeur de chaque coalition qu'on y retrouve doit être donnée. Les jeux symétriques à fonction de partition (SPFG) appartiennent à une classe de jeux coopératifs possédant deux caractéristiques principales. Premièrement, ils sont sensibles aux externalités, provoquées par n'importe quel groupe de joueurs qui s'allient ou défont leurs alliances, qui sont ressenties par les autres coalitions de joueurs. Deuxièmement, ils considèrent que les joueurs sont indistincts, et donc que seul le nombre de joueurs dans chaque coalition est à retenir pour représenter un SPFG. Par l'utilisation d'outils de programmation mixte en nombres entiers, nous présentons la première représentation de SPFG qui est polynomiale en nombre de joueurs dans le jeu. De surcroît, nous caractérisons la famille des SPFG qu'il est possible de représenter, qui inclut notamment tous les SPFG de cinq joueurs ou moins. De plus, elle dispose d'une approximation compacte pour le cas où, dans un jeu à six joueurs ou plus, le SPFG ne peut pas être représenté de façon exacte. Également, nous introduisons un cadre flexible qui utilise des méthodes visant la stabilité inspirées par la littérature pour identifier, à l'aide de notre représentation, une issue stable qui maximise le bien-être social des joueurs. Nous démontrons la valeur de notre représentation (approximée) compacte et de notre approche pour sélectionner une partition stable et une allocation des profits dans une application de marché compétitif provenant de la littérature.

De nos jours, atteindre un niveau élevé de satisfaction des employés à l’intérieur d’horaires efficients est une tâche importante et ardue à laquelle les compagnies font face. Dans ce travail, nous abordons une nouvelle variante du problème de création d’horaire de personnel face à une demande inconnue, en tenant compte de la satisfaction des employés via l’incertitude endogène qui découle de la combinaison des préférences des employés envers les horaires, et de ceux qu’ils reçoivent. Nous abordons ce problème dans le contexte de la création d’horaire d’employés remplaçants, un problème opérationnel de l’industrie du transport en commun qui n’a pas encore été étudié, bien qu’assez présent dans les compagnies nord-américaines. Pour faire face aux défis qu’amènent les deux sources d’incertitude, les absences des employés réguliers et des employés remplaçants, nous modélisons ce problème en un programme stochastique en nombres entiers à deux étapes avec recours mixte en nombres entiers. Les décisions de première étape consistent à trouver les journées de congé des employés remplaçants. Une fois que les absences inconnues des employés réguliers sont révélées, les décisions de deuxième étape consistent à planifier les tâches des employés remplaçants. Nous incorporons les préférences des employés remplaçants envers les journées de congé dans notre modèle pour observer à quel point la satisfaction de ces employés peut affecter leurs propres taux d’absence. Nous validons notre approche sur un an de données de la ville de Los Angeles. Notre travail est présentement en cours d’implémentation chez un fournisseur mondial de solutions logicielles pour les opérations de transport en commun. / Nowadays, reaching a high level of employee satisfaction in efficient schedules is an important and difficult task faced by companies. In this work, we tackle a new variant of the personnel scheduling problem under unknown demand by considering employee satisfaction via endogenous uncertainty depending on the combination of their preferred and received schedules. We address this problem in the context of reserve staff scheduling, an operational problem from the transit industry that has not yet been studied, although rather present in North American transit companies. To handle the challenges brought by the two uncertainty sources, regular employee and reserve employee absences, we formulate this problem as a two-stage stochastic integer program with mixed-integer recourse. The first-stage decisions consist in finding the days off of the reserve employees. After the unknown regular employee absences are revealed, the second-stage decisions are to schedule the reserve staff duties. We incorporate reserve employees’ preferences for days off into the model to examine how employee satisfaction may affect their own absence rates. We validate our approach on one year of data from the city of Los Angeles. Our work is currently being implemented in a world-leader software solutions provider for public transit operations.