Submitted by Geandra Rodrigues (geandrar@gmail.com) on 2018-09-04T12:20:42Z No. of bitstreams: 1 erickmariodonascimentooliveira.pdf: 3492871 bytes, checksum: 845fa85f6d95efe2e7ad13563f342bc3 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-09-04T13:21:49Z (GMT) No. of bitstreams: 1 erickmariodonascimentooliveira.pdf: 3492871 bytes, checksum: 845fa85f6d95efe2e7ad13563f342bc3 (MD5) / Made available in DSpace on 2018-09-04T13:21:49Z (GMT). No. of bitstreams: 1 erickmariodonascimentooliveira.pdf: 3492871 bytes, checksum: 845fa85f6d95efe2e7ad13563f342bc3 (MD5) Previous issue date: 2018-06-26 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho é apresentado o comportamento do algoritmo IED quando aplicado a problemas de programação em dois níveis. Para isso, o problema do seguidor é substituído pelas condições necessárias de primeira ordem de Karush-Kuhn-Tucker e, dessa maneira, o problema de programação em dois níveis é transformado em um problema de otimização com restrições não lineares. Dessa forma, as condições necessárias para utilização do algoritmo IED (Interior Epigraph Directions) são satisfeitas. Esse método tem como característica resolver problemas de otimização não convexa e não diferenciáveis via utilização da técnica de dualidade Lagrangiana, onde as funções de restrições são introduzidas na função objetivo para formar a função Lagrangiana. Além disso, o método considera o problema dual induzido por um esquema generalizado da dualidade Lagrangiana aumentada e obtém a solução primal produzindo uma sequência de pontos no interior do epígrafo da função dual. Dessa forma, o valor da função dual, em algum ponto do espaço dual, é dado pela minimização da Lagrangiana. Por fim, experimentos numéricos são apresentados em relação à utilização do algoritmo IED em problemas de programação em dois níveis encontrados na literatura. / This work presents the behavior of the IED algorithm when applied to bilevel programming problems. For this, the follower problem is replaced by the first-order necessary Karush-Kuhn-Tucker’s conditions and thus, the problem of bilevel programming turns into an optimization problem with non-linear constraints. Thus, the conditions required for use of the IED (Interior Epigraph Directions) algorithm are satisfied. This method has the characteristic of solving non-convex and non-differentiable optimization problems using the Lagrangian duality technique, where the constraint functions are introduced into the objective function for formulation of the Lagrangian. Furthermore, the method considers the dual problem induced by a generalized scheme of augmented Lagrangian duality and obtains the primal solution by producing a sequence of points inside the dual function epigraph. Then the value of the dual function, at some point in the dual space, is given by Lagrangian minimization. Finally, numerical experiments are presented showing the use of the IED algorithm in bilevel programming problems found in the literature.

In this thesis we study the problem of road taxation. This problem consists in finding the toll on the roads belonging to the government or a private company in order to maximize the revenue. An optimal taxation policy consists in determining level of tolls low enough to favor the use of toll arcs, and high enough to get important revenues. Since there are twolevels of decision, the problem is formulated as a bilevel bilinear program. / Doctorat en sciences, Orientation recherche opérationnelle / info:eu-repo/semantics/nonPublished

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.

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.

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.

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.

Le problème de tarification qui nous intéresse ici consiste à maximiser le revenu généré par les usagers d'un réseau de transport. Pour se rendre à leurs destinations, les usagers font un choix de route et utilisent des arcs sur lesquels nous imposons des tarifs. Chaque route est caractérisée (aux yeux de l'usager) par sa "désutilité", une mesure de longueur généralisée tenant compte à la fois des tarifs et des autres coûts associés à son utilisation. Ce problème a surtout été abordé sous une modélisation déterministe de la demande selon laquelle seules des routes de désutilité minimale se voient attribuer une mesure positive de flot. Le modèle déterministe se prête bien à une résolution globale, mais pèche par manque de réalisme. Nous considérons ici une extension probabiliste de ce modèle, selon laquelle les usagers d'un réseau sont alloués aux routes d'après un modèle de choix discret logit. Bien que le problème de tarification qui en résulte est non linéaire et non convexe, il conserve néanmoins une forte composante combinatoire que nous exploitons à des fins algorithmiques. Notre contribution se répartit en trois articles. Dans le premier, nous abordons le problème d'un point de vue théorique pour le cas avec une paire origine-destination. Nous développons une analyse de premier ordre qui exploite les propriétés analytiques de l'affectation logit et démontrons la validité de règles de simplification de la topologie du réseau qui permettent de réduire la dimension du problème sans en modifier la solution. Nous établissons ensuite l'unimodalité du problème pour une vaste gamme de topologies et nous généralisons certains de nos résultats au problème de la tarification d'une ligne de produits. Dans le deuxième article, nous abordons le problème d'un point de vue numérique pour le cas avec plusieurs paires origine-destination. Nous développons des algorithmes qui exploitent l'information locale et la parenté des formulations probabilistes et déterministes. Un des résultats de notre analyse est l'obtention de bornes sur l'erreur commise par les modèles combinatoires dans l'approximation du revenu logit. Nos essais numériques montrent qu'une approximation combinatoire rudimentaire permet souvent d'identifier des solutions quasi-optimales. Dans le troisième article, nous considérons l'extension du problème à une demande hétérogène. L'affectation de la demande y est donnée par un modèle de choix discret logit mixte où la sensibilité au prix d'un usager est aléatoire. Sous cette modélisation, l'expression du revenu n'est pas analytique et ne peut être évaluée de façon exacte. Cependant, nous démontrons que l'utilisation d'approximations non linéaires et combinatoires permet d'identifier des solutions quasi-optimales. Finalement, nous en profitons pour illustrer la richesse du modèle, par le biais d'une interprétation économique, et examinons plus particulièrement la contribution au revenu des différents groupes d'usagers. / The network pricing problem consists in finding tolls to set on a subset of a network's arcs, so to maximize a revenue expression. A fixed demand of commuters, going from their origins to their destinations, is assumed. Each commuter chooses a path of minimal "disutility", a measure of discomfort associated with the use of a path and which takes into account fixed costs and tolls. A deterministic modelling of commuter behaviour is mostly found in the literature, according to which positive flow is only assigned to \og shortest\fg\: paths. Even though the determinist pricing model is amenable to global optimization by the use of enumeration techniques, it has often been criticized for its lack of realism. In this thesis, we consider a probabilistic extension of this model involving a logit dicrete choice model. This more realistic model is non-linear and non-concave, but still possesses strong combinatorial features. Our analysis spans three separate articles. In the first we tackle the problem from a theoretical perspective for the case of a single origin-destination pair and develop a first order analysis that exploits the logit assignment analytical properties. We show the validity of simplification rules to the network topology which yield a reduction in the problem dimensionality. This enables us to establish the problem's unimodality for a wide class of topologies. We also establish a parallel with the product-line pricing problem, for which we generalize some of our results. In our second article, we address the problem from a numerical point of view for the case where multiple origin-destination pairs are present. We work out algorithms that exploit both local information and the pricing problem specific combinatorial features. We provide theoretical results which put in perspective the deterministic and probabilistic models, as well as numerical evidence according to which a very simple combinatorial approximation can lead to the best solutions. Also, our experiments clearly indicate that under any reasonable setting, the logit pricing problem is much smoother, and admits less optima then its deterministic counterpart. The third article is concerned with an extension to an heterogeneous demand resulting from a mixed-logit discrete choice model. Commuter price sensitivity is assumed random and the corresponding revenue expression admits no closed form expression. We devise nonlinear and combinatorial approximation schemes for its evaluation and optimization, which allow us to obtain quasi-optimal solutions. Numerical experiments here indicate that the most realistic model yields the best solution, independently of how well the model can actually be solved. We finally illustrate how the output of the model can be used for economic purposes by evaluating the contributions to the revenue of various commuter groups.

No description available.