This thesis presents the mixed integer bilevel programming problems where some optimality conditions and solution algorithms are derived. Bilevel programming problems are optimization problems which are partly constrained by another optimization problem. The theoretical part of this dissertation is mainly based on the investigation of optimality conditions of mixed integer bilevel program. Taking into account both approaches (optimistic and pessimistic) which have been developed in the literature to deal with this type of problem, we derive some conditions for the existence of solutions. After that, we are able to discuss local optimality conditions using tools of variational analysis for each different approach. Moreover, bilevel optimization problems with semidefinite programming in the lower level are considered in order to formulate more optimality conditions for the mixed integer bilevel program. We end the thesis by developing some algorithms based on the theory presented

In this thesis, we derive necessary optimality conditions for bilevel programming problems (BPPs for short) in Banach spaces. This rather abstract setting reflects our desire to characterize the local optimal solutions of hierarchical optimization problems in function spaces arising from several applications. Since our considerations are based on the tools of variational analysis introduced by Boris Mordukhovich, we study related properties of pointwise defined sets in function spaces. The presence of sequential normal compactness for such sets in Lebesgue and Sobolev spaces as well as the variational geometry of decomposable sets in Lebesgue spaces is discussed. Afterwards, we investigate mathematical problems with complementarity constraints (MPCCs for short) in Banach spaces which are closely related to BPPs. We introduce reasonable stationarity concepts and constraint qualifications which can be used to handle MPCCs. The relations between the mentioned stationarity notions are studied in the setting where the underlying complementarity cone is polyhedric. The results are applied to the situations where the complementarity cone equals the nonnegative cone in a Lebesgue space or is polyhedral. Next, we use the three main approaches of transforming a BPP into a single-level program (namely the presence of a unique lower level solution, the KKT approach, and the optimal value approach) to derive necessary optimality conditions for BPPs. Furthermore, we comment on the relation between the original BPP and the respective surrogate problem. We apply our findings to formulate necessary optimality conditions for three different classes of BPPs. First, we study a BPP with semidefinite lower level problem possessing a unique solution. Afterwards, we deal with bilevel optimal control problems with dynamical systems of ordinary differential equations at both decision levels. Finally, an optimal control problem of ordinary or partial differential equations with implicitly given pointwise state constraints is investigated.

Cette thèse aborde l'optimisation multicritère et l'optimisation à deux niveaux. L'investigation porte principalement sur les méthodes, les applications et les liens possibles entre les deux classes d'optimisation. Premièrement, nous développons une méthode de résolution des problèmes d'optimisation linéaire multicritère. Pour ce faire, nous introduisons une nouvelle caractérisation des faces efficaces et exploitons le résultat selon lequel l'ensemble des tableaux idéaux associés aux sommets extrêmes dégénérés est connexe. Ceci a permis de développer une approche de parcours de sommet extrême pour générer l'ensemble des solutions efficaces. Dans le même ordre d'idée, nous développons une méthode de résolution des problèmes linéaires à deux niveaux. L'approche est basée sur un résultat, que nous avons formalisé et démontré, qui stipule que la solution optimale du problème linéaire à deux niveaux est l'un des sommets extrêmes du domaine admissible. L'implémentation de l'approche a permis de démontrer qu'il existait dans la littérature des problèmes dont les solutions connues étaient fausses. Deuxièmement, en termes d'applications, nous construisons un modèle d'optimisation multicritère pouvant être exploité dans l'optique d'une planification optimale de la distribution de l'énergie électrique au Cameroun. Nous proposons aussi, à partir d'un modèle d'optimisation à deux niveaux, une technique dont la mise en œuvre par l'État pourrait permettre de protéger les industries locales de la concurrence des firmes internationales. Enfin, nous étudions l'interrelation entre l'optimisation multicritère et l'optimisation à deux niveaux. Tout d'abord, nous tirons des conditions de Pareto-optimalité des solutions du problème à deux niveaux. Ensuite, nous montrons qu'il est possible d'obtenir une solution optimale de certaines classes de problèmes d'optimisation à deux niveaux en résolvant deux problèmes particuliers d'optimisation multicritère. Puis, nous étudions le cas de problème à deux niveaux dans lequel chaque décideur possède plusieurs fonctions objectifs conflictuelles, en nous focalisant sur le cas linéaire. Après, nous construisons un problème artificiel d'optimisation linéaire multicritère dont l'ensemble des solutions efficaces est égal au domaine des solutions admissibles du problème du leader. Pour terminer, nous utilisons ce résultat pour proposer deux approches de résolution dépendant chacune des aspirations du leader / This thesis addresses two important classes of optimization : multiobjective optimization and bilevel optimization. The investigation concerns their solution methods, applications, and possible links between them. First of all, we develop a procedure for solving Multiple Objective Linear Programming Problems (MOLPP). The method is based on a new characterization of efficient faces. It exploits the connectedness property of the set of ideal tableaux associated to degenerated points in the case of degeneracy. We also develop an approach for solving Bilevel Linear Programming Problems (BLPP). It is based on the result that an optimal solution of the BLPP is reachable at an extreme point of the underlying region. Consequently, we develop a pivoting technique to find the global optimal solution on an expanded tableau that represents the data of the BLPP. The solutions obtained by our algorithm on some problems available in the literature show that these problems were until now wrongly solved. Some applications of these two areas of optimization problems are explored. An application of multicriteria optimization techniques for finding an optimal planning for the distribution of electrical energy in Cameroon is provided. Similary, a bilevel optimization model that could permit to protect any economic sector where local initiatives are threatened is proposed. Finally, the relationship between the two classes of optimization is investigated. We first look at the conditions that guarantee that the optimal solution of a given BPP is Pareto optimal for both upper and lower level objective functions. We then introduce a new relation that establishes a link between MOLPP and BLPP. Moreover, we show that, to solve a BPP, it is possible to solve two artificial M0PPs. In addition, we explore Bilevel Multiobjective Programming Problem (BMPP), a case of BPP where each decision maker (DM) has more than one objective function. Given a MPP, we show how to construct two artificial M0PPs such that any point that is efficient for both problems is also efficient for the BMPP. For the linear case specially, we introduce an artificial MOLPP such that its resolution can permit to generate the whole feasible set of the leader DM. Based on this result and depending on whether the leader can evaluate or not his preferences for his different objective functions, two approaches for obtaining efficient solutions are presented

Em um problema de natureza hierárquica, o nível mais influente toma certas decisões que afetam o comportamento dos níveis inferiores. Cada decisão do nível mais influente é considerada como fixa pelos níveis inferiores, que, com tais informações, tomam decisões que maximizam seus objetivos. Essas decisões podem influenciar os resultados obtidos pelo nível superior, que, por sua vez, também anseia pela decisão ótima. Em programação matemática, este problema é modelado como um problema de programação em níveis. Neste trabalho, consideramos uma classe particular de problemas de programação em níveis: os problemas de programação matemática em dois níveis. Estudamos uma técnica de resolução que consiste em substituir o problema do nível inferior por suas condições necessárias de primeira ordem, que podem ser formuladas de diversas maneiras, conforme as restrições de complementaridade são modificadas. O novo problema torna-se um problema de programação não linear e pode ser resolvido com algoritmos clássicos de otimização. Com o auxílio de condições de otimalidade de primeira e segunda ordem mostramos as relações entre o problema original e o problema reformulado. Aplicamos a técnica a problemas encontrados na literatura, analisamos o seu comportamento e apresentamos estratégias para eliminar certos inconvenientes encontrados. / In problems of hierarchical nature, the choices made by the most influential level - the so-called leader - affect the behavior of the lower levels. For each one of the leader\'s decisions there is a response from the lower levels, which maximizes the value of their respective objectives. These optimal choices, in return, may have influence in the results achieved by the leader, which also wants to make the optimal choices. In mathematical programming, this kind of problem is described as a multilevel programming problem. The present work considers a specific kind of multilevel problem: the bilevel mathematical problem. We study a resolution technique which consists in replacing the lower level problem by its necessary first order conditions, which can be formulated in various ways, as complementarity constraints occur and are modified. The new reformulated problem is a nonlinear programming problem which can be solved by classical optimization methods. Using first and second order optimality conditions, we show the relations between the original bilevel problem and the reformulated problem. We apply the described technique to solve a set of bilevel problems taken from the literature, analyse their behavior and discuss strategies to prevent undesirable difficulties that may arise.

Optimalizace toku v síti je klasickou aplikací matematického programování. Tyto modely mají, mimo jiné, široké uplatnění také v logistice, kde se tak snažíme docílit optimálního rozdělení dopravy, např. vzhledem k maximalizaci zisku, či minimalizaci nákladů. Toto pojetí ovšem často problém idealizuje, poněvadž předpokládá existenci jediného rozhodovatele. Takový přístup je možný ve striktně organizovaných sítích jako např. v logistických sítích přepravních společností, železničních sítích či armádním zásobování. Úloha ''Traffic Assignment Problem'' (TAP) se zaměřuje na dopady teorie her na optimalizaci toku, tj. zkoumá vliv více rozhodovatelů na celkové využití sítě. V práci se zaobíráme úlohou TAP s působením náhodných vlivů, k čemuž využíváme metod stochastické a vícestupňové optimalizace. Dále zkoumáme možnosti zlepšení stávajícího využití sítě za rozhodnutí autoritativního rozhodovatele, kterému je umožněn zásah do samotné struktury sítě, k čemuž využíváme víceúrovňové programování.

In der Dissertation werden Zwei-Ebenen-Optimierungsaufgaben mit spezieller Struktur untersucht. Von Interesse sind hierbei für den sogenannten pessimistischen Lösungszugang Existenzresultate für Lösungen, die Eckpunkteigenschaft einer Lösung, eine Regularisierungstechnik, Optimalitätsbedingungen sowie für den linearen Fall ein Verfahren zur Bestimmung einer global pessimistischen Lösung. Beim optimistischen Lösungszugang wird zunächst eine Verallgemeinerung des Lösungsbegriffes angegeben. Anschließend finden sich Betrachtungen zur Komplexität des Problems, zu Optimalitätsbedingungen sowie ein Abstiegs- und Branch&Bound-Verfahren für den linearen Fall wieder. Den Abschluss der Arbeit bilden ein Anwendungsbeispiel und numerische Testrechnungen.

L’objectif de cette thèse est de développer et étudier des modèles mathématiques d’échanges économiques, basés sur la flexibilité de la demande, entre fournisseurs et consommateurs d’électricité. D’une part, des fournisseurs d’électricité offrent des prix dépendant de l’heure de consommation. D’autre part, des consommateurs adaptent leur usage, minimisant leur facture et le désagrément lié aux changements de consommation induits. La structure de ces problèmes correspond à des problèmes d’optimisation bi-niveau. Trois types de modèles sont étudiés. Tout d’abord, l’interaction entre un fournisseur et un opérateur de smart grid est modélisée par un problème à un seul meneur et un seul suiveur. Pour cette première approche, le niveau de détails du suiveur est particulièrement élevé, et inclut notamment une gestion stochastique de la production distribuée. La meilleure réponse d’un fournisseur dans un modèle à plusieurs meneurs et plusieurs suiveurs fait l’objet de la seconde partie de la thèse. Celle-ci intègre aussi la possibilité d’avoir des agrégateurs comme suiveurs. Deux nouvelles méthodes de résolution reposant sur la sélection d’équilibres de Nash entre suiveurs sont proposées. Enfin, dans une troisième et dernière partie, on se focalise sur la recherche d’équilibres non coopératifs pour ce modèle à plusieurs meneurs et plusieurs suiveurs.Tous les problèmes abordés dans cette thèse le sont non seulement d’un point de vue théorique, mais également d’un point de vue numérique / The objective of this thesis is to develop and study mathematical models of economical exchanges between energy suppliers and consumers, using demand-side management. On one hand, the suppliers offer time-of-use electricity prices. On the other hand, energy consumers decide on their energy demand schedule, minimizing their electricity bill and the inconvenience due to schedule changes. This problem structure gives rise to bilevel optimization problems.Three kinds of models are studied. First, single-leader single-follower problems modeling the interaction between an energy supplier and a smart grid operator. In this first approach, the level of details is very high on the follower’s side, and notably includes a stochastic treatment of distributed generation. Second, a multi-leader multi-follower problem is studied from the point of view of the best response of one of the suppliers. Aggregators are included in the lower level. Two new resolution methods based on a selection of Nash equilibriums at the lower level are proposed. In the third and final part, the focus is on the evaluation of noncooperative equilibriums for this multi-leader multi-follower problem.All the problems have been studied both from a theoretical and numerical point of view.

The main purpose of this dissertation is to investigate directional constraint qualifications and necessary optimality conditions for nonsmooth set-constrained mathematical programs. First, we study sufficient conditions for metric subregularity of the set-constrained system. We introduce the directional version of the quasi-/pseudo-normality as a sufficient condition for metric subregularity, which is weaker than the classical quasi-/pseudo-normality, respectively. Then we apply our results to complementarity and Karush-Kuhn-Tucker systems. Secondly, we study directional optimality conditions of bilevel programs. It is well-known that the value function reformulation of bilevel programs provides equivalent single-level optimization problems， which are nonsmooth and never satisfy the usual constraint qualifications such as the Mangasarian-Fromovitz constraint qualification (MFCQ). We show that even the first-order sufficient condition for metric subregularity (which is generally weaker than MFCQ) fails at each feasible point of bilevel programs. We introduce the directional Clarke calmness condition and show that under the directional Clarke calmness condition, the directional necessary optimality condition holds. We perform directional sensitivity analysis of the value function and propose the directional quasi-normality as a sufficient condition for the directional Clarke calmness. / Graduate / 2021-07-07

La programmation bi-niveau désigne une classe de problèmes d'optimisation emboîtés impliquant deux joueurs.Un joueur meneur annonce une décision à un joueur suiveur qui détermine sa réponse parmi l'ensemble des solutions d'un problème d'optimisation dont les données dépendent de la décision du meneur (problème de niveau bas).La décision optimale du meneur est la solution d'un autre problème d'optimisation dont les données dépendent de la réponse du suiveur (problème de niveau haut).Lorsque la réponse du suiveur n'est pas unique, on distingue les problèmes bi-niveaux optimistes et pessimistes,suivant que la réponse du suiveur soit respectivement la meilleure ou la pire possible pour le meneur.Les problèmes bi-niveaux sont souvent utilisés pour modéliser des problèmes de tarification. Dans les applications étudiées ici, le meneur est un vendeur qui fixe un prix, et le suiveur modélise le comportement d'un grand nombre de clients qui déterminent leur consommation en fonction de ce prix. Le problème de niveau bas est donc de grande dimension.Cependant, la plupart des problèmes bi-niveaux sont NP-difficiles, et en pratique, il n'existe pas de méthodes générales pour résoudre efficacement les problèmes bi-niveaux de grande dimension.Nous introduisons ici une nouvelle approche pour aborder la programmation bi-niveau.Nous supposons que le problème de niveau bas est un programme linéaire, en variables continues ou discrètes,dont la fonction de coût est déterminée par la décision du meneur.Ainsi, la réponse du suiveur correspond aux cellules d'un complexe polyédral particulier,associé à une hypersurface tropicale.Cette interprétation est motivée par des applications récentes de la géométrie tropicale à la modélisation du comportement d'agents économiques.Nous utilisons la dualité entre ce complexe polyédral et une subdivision régulière d'un polytope de Newton associé pour introduire une méthode dedécomposition qui résout une série de sous-problèmes associés aux différentes cellules du complexe.En utilisant des résultats portant sur la combinatoire des subdivisions, nous montrons que cette décomposition mène à un algorithme permettant de résoudre une grande classe de problèmes bi-niveaux en temps polynomial en la dimension du problème de niveau bas lorsque la dimension du problème de niveau haut est fixée.Nous identifions ensuite des structures spéciales de problèmes bi-niveaux pour lesquelles la borne de complexité peut être améliorée.C'est en particulier le cas lorsque la fonction coût du meneur ne dépend que de la réponse du suiveur.Ainsi, nous montrons que la version optimiste du problème bi-niveau peut être résolue en temps polynomial, notammentpour des instancesdans lesquelles les données satisfont certaines propriétés de convexité discrète.Nous montrons également que les solutions de tels problèmes sont des limites d'équilibres compétitifs.Dans la seconde partie de la thèse, nous appliquons cette approche à un problème d'incitation tarifaire dans les réseaux mobiles de télécommunication.Les opérateurs de données mobiles souhaitent utiliser des schémas de tarification pour encourager les différents utilisateurs à décaler leur consommation de données mobiles dans le temps, et par conséquent dans l'espace (à cause de leur mobilité), afin de limiter les pics de congestion.Nous modélisons cela par un problème bi-niveau de grande taille.Nous montrons qu'un cas simplifié peut être résolu en temps polynomial en utilisant la décomposition précédente,ainsi que des résultats de convexité discrète et de théorie des graphes.Nous utilisons ces idées pour développer une heuristique s'appliquant au cas général.Nous implémentons et validons cette méthode sur des données réelles fournies par Orange. / Bilevel programming deals with nested optimization problems involving two players. A leader annouces a decision to a follower, who responds by selecting a solution of an optimization problem whose data depend on this decision (low level problem). The optimal decision of the leader is the solution of another optimization problem whose data depend on the follower's response (high level problem). When the follower's response is not unique, one distinguishes between optimistic and pessimistic bilevel problems, in which the leader takes into account the best or worst possible response of the follower.Bilevel problems are often used to model pricing problems.We are interested in applications in which the leader is a seller who announces a price, and the follower models the behavior of a large number of customers who determine their consumptions depending on this price.Hence, the dimension of the low-level is large. However, most bilevel problems are NP-hard, and in practice, there is no general method to solve efficiently large-scale bilevel problems.In this thesis, we introduce a new approach to tackle bilevel programming. We assume that the low level problem is a linear program, in continuous or discrete variables, whose cost function is determined by the leader. Then, the follower responses correspond to the cells of a special polyhedral complex, associated to a tropical hypersurface. This is motivated by recent applications of tropical geometry to model the behavior of economic agents.We use the duality between this polyhedral complex and a regular subdivision of an associated Newton polytope to introduce a decomposition method, in which one solves a series of subproblems associated to the different cells of the complex. Using results about the combinatorics of subdivisions, we show thatthis leads to an algorithm to solve a wide class of bilevel problemsin a time that is polynomial in the dimension of the low-level problem when the dimension of the high-level problem is fixed.Then, we identify special structures of bilevel problems forwhich this complexity bound can be improved.This is the case when the leader's cost function depends only on the follower's response. Then, we showthe optimistic bilevel problem can be solved in polynomial time.This applies in particular to high dimensional instances in which the datasatisfy certain discrete convexity properties. We also show that the solutions of such bilevel problems are limits of competitive equilibria.In the second part of this thesis, we apply this approach to a price incentive problem in mobile telecommunication networks.The aim for Internet service providers is to use pricing schemes to encourage the different users to shift their data consumption in time(and so, also in space owing to their mobility),in order to reduce the congestion peaks.This can be modeled by a large-scale bilevel problem.We show that a simplified case can be solved in polynomial time by applying the previous decomposition approach together with graph theory and discrete convexity results. We use these ideas to develop an heuristic method which applies to the general case. We implemented and validated this method on real data provided by Orange.

Transport and trade of gas are decoupled after the liberalization of the European gas markets, which are now organized as so-called entry-exit systems. At the core of this market system are bookings and nominations, two special capacity-right contracts that grant traders access to the gas network. The latter is operated by a separate entity, known as the transmission system operator (TSO), who is in charge of the transport of gas from entry to exit nodes. In the mid to long term, traders sign a booking contract with the TSO to obtain injection and withdrawal capacities at entry and exit nodes, respectively. On a day-ahead basis, they then nominate within these booked capacities a balanced load flow of the planned amounts of gas to be injected into and withdrawn from the network the next day. The key property is that by signing a booking contract, the TSO is obliged to guarantee transportability for all balanced load flows in compliance with the booked capacities. To assess the feasibility of a booking, it is therefore necessary to check the feasibility of infinitely many nominations. As a result, deciding if a booking is feasible is a challenging mathematical problem, which we investigate in this dissertation.Our results range from passive networks, consisting of pipes only, to active networks, containing controllable elements to influence gas flows. Since the study of the latter naturally leads to a bilevel framework, we first consider some more general properties of bilevel optimization. For the case of linear bilevel optimization, we consider the hardness of validating the correctness of big-Ms often used in solving these problems via a single-level reformulation. We also derive a family of valid inequalities to be used in a bilevel-tailored branch-and-cut algorithm as a big-M-free alternative.We then turn to the study of feasible bookings. First, we present our results on passive networks, for which bilevel approaches are not required. A characterization of feasible bookings on passive networks is derived in terms of a finite set of nominations. While computing these nominations is a difficult task in general, we present polynomial complexity results for the special cases of tree-shaped or single-cycle passive networks. Finally, we consider networks with linearly modeled active elements. After obtaining a bilevel optimization model that allows us to determine the feasibility of a booking in this case, we derive various single-level reformulations to solve the problem. In addition, we obtain novel characterizations of feasible bookings on active networks, which generalize our characterization in the passive case. The performance of these various approaches is compared in a case study on two networks from the literature, one of which is a simplified version of the Greek gas network. / Transport et commerce de gaz sont découplés depuis la libéralisation des marchés européens du gaz, qui sont désormais organisés en systèmes dit d'entrée-sortie. Au cœur de ce système de marché se trouvent les réservations et les nominations, deux contrats spéciaux de droit à la capacité qui permettent aux négociants d'accéder au réseau de gaz. Ce dernier est exploité par une entité distincte, appelée gestionnaire de réseau de transport~(GRT), qui est chargée du transport du gaz entre les nœuds d'entrée et de sortie. À moyen et long terme, les négociants signent un contrat de réservation avec le GRT pour obtenir des capacités d'injection et d'extraction aux nœuds d'entrée et de sortie, respectivement. Au jour le jour, ils désignent ensuite, dans les limites des capacités réservées, un flux de charge équilibrée des quantités de gaz prévues à injecter et à extraire le lendemain. La propriété essentielle est qu'en signant un contrat de réservation, le GRT est obligé de garantir la transportabilité de tous les flux de charge équilibrée respectant les capacités réservées. Pour évaluer la faisabilité d'une réservation, il est donc nécessaire de vérifier la faisabilité d'une infinité de nominations. Par conséquent, décider si une réservation est réalisable est un problème mathématique difficile, que nous étudions dans cette thèse.Nos résultats vont des réseaux passifs, constitués uniquement de pipelines, aux réseaux actifs, contenant des éléments contrôlables pour influencer les flux de gaz. Comme l'étude de ces derniers conduit naturellement à un cadre biniveau, nous considérons d'abord certaines propriétés plus générales de l'optimisation biniveau. Pour le cas de l'optimisation biniveau linéaire, nous étudions la difficulté de valider l'exactitude des constantes de type big-M souvent utilisées dans la résolution de ces problèmes via une reformulation à un seul niveau. Nous déduisons également une famille d'inégalités valides à utiliser dans un algorithme de branch-and-cut adapté au biniveau comme alternative à l'approche utilisant des big-Ms.Nous nous tournons ensuite vers l'étude des réservations réalisables. D'abord, nous présentons nos résultats sur les réseaux passifs, pour lesquels les approches biniveaux ne sont pas nécessaires. Une caractérisation des réservations réalisables sur les réseaux passifs est déduite en termes d'un ensemble fini de nominations. Bien que le calcul de ces nominations soit une tâche difficile en général, nous présentons des algorithmes polynomiaux pour les cas particuliers des réseaux passifs en forme d'arbre ou contenant un cycle unique. Enfin, nous considérons les réseaux avec des éléments actifs modélisés à l'aide de contraintes linéaires. Après avoir obtenu un modèle biniveau, permettant de déterminer la faisabilité d'une réservation dans ce cas, nous dérivons diverses reformulations à un seul niveau pour résoudre le problème. En outre, nous obtenons de nouvelles caractérisations des réservations réalisables sur les réseaux actifs, qui généralisent notre caractérisation dans le cas passif. La performance de ces différentes approches est comparée dans une étude de cas réalisée sur deux réseaux de la littérature, dont l'un est une version simplifiée du réseau de gaz grec. / Nach der Liberalisierung der europäischen Gasmärkte, welche nun als sogenannte Entry-Exit Systeme organisiert sind, sind Transport und Handel von Gas entkoppelt. Im Zentrum dieses neuen Marktsystems sind Buchungen und Nominierungen, zwei spezielle Kapazitätrechtsverträge, die Händlern Zugang zum Gasnetz gewähren. Letzteres wird von einem separaten Akteur betrieben, dem sogenannten Fernleitungsnetzbetreiber (FNB), der für den Transport des Gases von den Einspeise- zu den Ausspeiseknoten verantwortlich ist. Händler schließen mittel- bis langfristig einen Buchungsvertrag mit dem FNB ab, um Ein- und Ausspeisekapazitäten zu erhalten. Täglich nominieren sie dann innerhalb der gebuchten Kapazitäten einen bilanzierten Lastfluss der geplanten Gasmengen, die am nächsten Tag eingespeist und entnommen werden sollen. Die Haupteigenschaft ist, dass der FNB sich durch Unterzeichnung eines Buchungsvertrages für die Transportierbarkeit aller bilanzierten Lastflüsse innerhalb der gebuchten Kapazitäten verpflichtet. Um die Zulässigkeit einer Buchung zu bestimmen ist es daher notwendig, die Zulässigkeit von unendlich vielen Nominierungen zu prüfen. Die Entscheidung, ob eine Buchung zulässig ist, ist daher ein anspruchsvolles mathematisches Problem, das wir in dieser Dissertation untersuchen.Unsere Ergebnisse reichen von passiven Netzen, die nur aus Rohren bestehen, bis hin zu aktiven Netzen, die steuerbare Elemente zur Beeinflussung der Gasflüsse enthalten. Da die Untersuchung aktiver Netze uns auf natürlichem Wege zu Bilevel-Problemen führt, betrachten wir zunächst einige allgemeinere Eigenschaften der Bilevel-Optimierung. Für den Fall der linearen Bilevel-Optimierung betrachten wir die Schwierigkeit, Big-Ms zu validieren, die oft bei der Lösung dieser Probleme mittels einer einstufigen Reformulierung verwendet werden. Wir leiten außerdem eine Familie gültiger Ungleichungen ab, die in einem Bilevel-spezifischen Branch-and-Cut Algorithmus als big-M-freie Alternative verwendet werden können.Wir wenden uns dann der Untersuchung von zulässigen Buchungen zu. Zunächst stellen wir unsere Ergebnisse zu passiven Netzwerken vor, für die Bilevel-Ansätze nicht erforderlich sind. Eine Charakterisierung zulässiger Buchungen in passiven Netzwerken wird in Bezug auf eine endliche Menge an Nominierungen hergeleitet. Während die Berechnung dieser Nominierungen im Allgemeinen eine schwierige Aufgabe ist, präsentieren wir polynomielle Komplexitätsergebnisse für die Spezialfälle baumförmiger oder einzyklischer passiver Netze. Schließlich betrachten wir Netze mit linear modellierten aktiven Elementen. Nachdem wir ein Bilevel-Modell hergeleitet haben, mit dem wir die Zulässigkeit einer Buchung in diesem Fall bestimmen können, leiten wir verschiedene einstufige Reformulierungen zur Lösung des Problems ab. Darüber hinaus erhalten wir neuartige Charakterisierungen zulässiger Buchungen auf aktiven Netzen, die unsere Charakterisierung im passiven Fall verallgemeinern. Die Anwendbarkeit dieser verschiedenen Ansätze wird in einer Fallstudie an zwei Netzen aus der Literatur verglichen, wovon eines eine vereinfachte Version des griechischen Gasnetzes ist. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished