<p>We analyse several facets of bilevel decision problems under uncertainty. These problems can be interpreted as an extension of stochastic programming problems where part of the uncertainty is attributed to the behaviour of another actor.</p><p>The field of decision making under uncertainty with bilevel features is quite new and most approaches focus on the interactions and relations between the decision makers. In contrast to these studies, the approach of bilevel stochastic programming pursued here stresses the stochastic programming aspect of the problem formulation. The framework enables a direct application of stochastic programming concepts and solution methods to the bilevel relationship between the actors. Thus more complex problem structures can be studied and the aspect of uncertainty can be treated adequately.</p><p>Our analysis covers both theoretical and more practically oriented issues. We study different formulations of one and two stage bilevel stochastic programming problems and state necessary optimality conditions for each of the problem instances. Additionally we present a solution algorithm utilising a stochastic quasi-gradient method. A further study is concerned with the uniqueness of the minima of a convex stochastic programming problem with uncertainty about the decision variables. We state conditions on the distribution of the parameters representing the uncertainty such that the minima of the optimisation problem are unique. We formulate a model of competition and collaboration of two different types of telecom service providers, the owner of a bottleneck facility and a virtual network operator. This represents an application of a bilevel stochastic programming formulation to a liberalised telecommunications environment. Furthermore, the utilisation of the bilevel stochastic programming framework and the developed solution concepts for the analysis of principal agent models is demonstrated. Also here the background of a regulated telecom environment, more specific the relations between a regulator and a regulated telecommunications company, was chosen.</p>

<p>This thesis investigates the second-best toll pricing and capacity expansion problems when stated as mathematical programs with equilibrium constraints (MPEC). Three main questions are rised: First, whether conventional descent methods give sufficiently good solutions, or whether global solution methods are to prefer. Second, how the performance of the considered solution methods scale with network size. Third, how a discretized stochastic mathematical program with equilibrium constraints (SMPEC) formulation of a stochastic network design problem can be practically solved. An attempt to answer these questions is done through a series ofnumerical experiments.</p><p>The traffic system is modeled using the Wardrop’s principle for user behavior, separable cost functions of BPR- and TU71-type. Also elastic demand is considered for some problem instances.</p><p>Two already developed method approaches are considered: implicit programming and a cutting constraint algorithm. For the implicit programming approach, several methods—both local and global—are applied and for the traffic assignment problem an implementation of the disaggregate simplicial decomposition (DSD) method is used. Regarding the first question concerning local and global methods, our results don’t give a clear answer.</p><p>The results from numerical experiments of both approaches on networks of different sizes shows that the implicit programming approach has potential to solve large-scale problems, while the cutting constraint algorithm scales worse with network size.</p><p>Also for the stochastic extension of the network design problem, the numerical experiments indicate that implicit programming is a good approach to the problem.</p><p>Further, a number of theorems providing sufficient conditions for strong regularity of the traffic assignment solution mapping for OD connectors and BPR cost functions are given.</p>

We analyse several facets of bilevel decision problems under uncertainty. These problems can be interpreted as an extension of stochastic programming problems where part of the uncertainty is attributed to the behaviour of another actor. The field of decision making under uncertainty with bilevel features is quite new and most approaches focus on the interactions and relations between the decision makers. In contrast to these studies, the approach of bilevel stochastic programming pursued here stresses the stochastic programming aspect of the problem formulation. The framework enables a direct application of stochastic programming concepts and solution methods to the bilevel relationship between the actors. Thus more complex problem structures can be studied and the aspect of uncertainty can be treated adequately. Our analysis covers both theoretical and more practically oriented issues. We study different formulations of one and two stage bilevel stochastic programming problems and state necessary optimality conditions for each of the problem instances. Additionally we present a solution algorithm utilising a stochastic quasi-gradient method. A further study is concerned with the uniqueness of the minima of a convex stochastic programming problem with uncertainty about the decision variables. We state conditions on the distribution of the parameters representing the uncertainty such that the minima of the optimisation problem are unique. We formulate a model of competition and collaboration of two different types of telecom service providers, the owner of a bottleneck facility and a virtual network operator. This represents an application of a bilevel stochastic programming formulation to a liberalised telecommunications environment. Furthermore, the utilisation of the bilevel stochastic programming framework and the developed solution concepts for the analysis of principal agent models is demonstrated. Also here the background of a regulated telecom environment, more specific the relations between a regulator and a regulated telecommunications company, was chosen.

This thesis investigates the second-best toll pricing and capacity expansion problems when stated as mathematical programs with equilibrium constraints (MPEC). Three main questions are rised: First, whether conventional descent methods give sufficiently good solutions, or whether global solution methods are to prefer. Second, how the performance of the considered solution methods scale with network size. Third, how a discretized stochastic mathematical program with equilibrium constraints (SMPEC) formulation of a stochastic network design problem can be practically solved. An attempt to answer these questions is done through a series ofnumerical experiments. The traffic system is modeled using the Wardrop’s principle for user behavior, separable cost functions of BPR- and TU71-type. Also elastic demand is considered for some problem instances. Two already developed method approaches are considered: implicit programming and a cutting constraint algorithm. For the implicit programming approach, several methods—both local and global—are applied and for the traffic assignment problem an implementation of the disaggregate simplicial decomposition (DSD) method is used. Regarding the first question concerning local and global methods, our results don’t give a clear answer. The results from numerical experiments of both approaches on networks of different sizes shows that the implicit programming approach has potential to solve large-scale problems, while the cutting constraint algorithm scales worse with network size. Also for the stochastic extension of the network design problem, the numerical experiments indicate that implicit programming is a good approach to the problem. Further, a number of theorems providing sufficient conditions for strong regularity of the traffic assignment solution mapping for OD connectors and BPR cost functions are given.

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

The research subject of the dissertation is the analysis of the model of heterogenous agents and its application for modelling stochastic Nash and Stackelberg equilibriums, applying the Monte Carlo method. The aim of the dissertation is to identify the impact of heterogeneous agents on the formation of the economic bubble, to create and examine algorithms for special bilevel stochastic programming problems and for search of the stochastic Nash equilibrium, applying the Monte Carlo method. The thesis offers a mathematical model for identification of the beginning of the bubble. This model has been applied for the analysis of the real estate bubble in Lithuania. In cases of uncertainty, decisions are often made by several individuals whose interests do not coincide. In such situations one of the concepts of the equilibrium is the stochastic Nash equilibrium. The dissertation examines the stochastic Nash equilibrium and offers the algorithm for gradient search of this equilibrium. The algorithm for gradient search of the stochastic Nash equilibrium was examined by solving the problem of electricity market with precedent agreements. The dissertation offers the algorithm for solving the optimization problem where the objective function and constraints contain conditional value at risk and by solving the test problem the behaviour of the algorithm is investigated. The dissertation proposes the algorithm for solving the two stage stochastic linear problem, employing the method of... [to full text] / Disertacijos objektas – heterogeninių agentų modelio tyrimas ir taikymas stochastinėms Nešo ir Stakelbergo pusiausvyroms modeliuoti Monte Karlo metodu. Darbo tikslas – nustatyti heterogeninių agentų įtaką ekonominio burbulo susidarymui, sukurti ir ištirti dviejų lygių stochastinio programavimo specialių uždavinių bei stochastinės Nešo pusiausvyros paieškos Monte Karlo algoritmus. Netvarių būsenų (burbulų ir jų griūčių) identifikavimas labai svarbus ekonomikai bei finansams. Disertacijoje pateiktas burbulo pradžios identifikavimo matematinis modelis, kurį taikant buvo ištirtas Lietuvos nekilnojamojo turto burbulas. Esant neapibrėžtumui, sprendimus dažnai priima keli individai, kurių interesai nesutampa. Tokiose situacijose taikoma viena iš pusiausvyros koncepcijų, būtent, stochastinė Nešo pusiausvyra. Darbe ištirta stochastinė Nešo pusiausvyra ir pasiūlytas jos gradientinės paieškos algoritmas. Stochastinės Nešo pusiausvyros gradientinės paieškos algoritmas ištirtas sprendžiant elektros rinkos su išankstiniais sandoriais uždavinį. Optimizavimo uždavinys, kurio tikslo funkcijoje ir ribojimuose yra sąlyginės rizikos reikšmė yra dviejų lygių stochastinio programavimo uždavinys. Disertacijoje pasiūlytas tokio uždavinio sprendimo algoritmas ir testiniu uždaviniu ištirta jo elgsena. Jei stochastinis dviejų etapų tiesinis uždavinys sprendžiamas reikšmingų imčių metodu, tai gaunamas dviejų lygių stochastinio programavimo uždavinys. Disertacijoje pasiūlytas stochastinio dviejų etapų... [toliau žr. visą tekstą]

In the push for clean and renewable fuels, timber derived biomass is a promising frontier for biofuel production in the United States. This thesis approaches the established timberlands biofuel implementation problem with three different mathematical programming studies, each testing feasibility and sustainability in different economic and supply related situations. In the first study, a competitive game theory approach was utilized to provide new insights into the behavior within a timberlands supply chain. We utilized Stackelberg game theory modeled with bilevel programming to represent the competing harvesting and manufacturing sectors. In the second study, the initial bilevel model was utilized in a larger two stage multiperiod model with parameter uncertainty. In this more realistic model, the first stage contained logistical decisions around biorefinery investments, such as location and capacity, while the second stage was composed of multiple discrete bilevel scenarios representing potential situations in the timberlands system. The final study focused on long term land management strategies for the timberlands supply chain. Introduction of a new biorefinery investment meant that management strategies must be altered to ensure consistent material flows to manufacturers as well as sustain the new production facility. A modified cyclic scheduling formulation was used to model a timberlands system and its planting and harvesting schedule to accommodate a new biorefinery. This cyclic model added an initial startup period to initiate biofuel production and provide time to adapt land management. The overall contribution of these studies was to analyze a biorefinery's impact on the established behavior in a timberlands supply chain. In particular, the goals of these models were to develop introductory decision making tools for timberlands supply chain managers.

Orientador: José Roberto Sanches Mantovani / Resumo: Neste trabalho, o modelo matemático do problema de fluxo de potência ótimo básico não linear é analisado e manipulado algebricamente para obter um modelo de programação convexa, do tipo cônico de segunda ordem. O conceito de envelopes convexos é apresentado para tratar a não linearidade e não convexidade da restrição trigonométrica inversa que surge ao escrever o modelo de FPO como um modelo cônico. Aplicando duas proposições apresentadas neste trabalho a restrição trigonométrica é resolvida em um pré-processamento por um solver de otimalidade local, neste caso o KNITRO, que enumera todas as possibilidades dos pontos de KKT para obter os envelopes convexos e tornar o modelo de FPO totalmente convexo. O modelo é implementado no AMPL e é resolvido com solvers de otimalidade global com sistemas testes da literatura, nesta tese usam-se os sistemas testes IEEE 14, 30, 57 e 118 barras. Os resultados obtidos são validados comparando-os com resultados fornecidos pelo Matpower, que é um simulador para FPO. Como contribuição desta tese, o modelo convexo de FPO obtido é utilizado como exemplo de aplicações no problema de despacho ótimo de potência ativa e reativa, considerando competições via programação binível. São apresentados dois modelos biníveis e dois modelos uníveis. O modelo iterativo convexo utiliza-se do modelo proposto de FPO convexo e as não linearidades são convexificadas fazendo uso dos envelopes de McCormick. O conceito de dualidade forte é empregado afim de obter um mod... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: In this work, the basic nonlinear mathematical model for the optimal power flow (OPF) problem is analyzed and manipulated algebraically in order to obtain a second-order conic convex programming model. The concept of convex envelopes is presented to deal with the nonlinearity and nonconvexity of the inverse trigonometric constraint that arises when transforming the nonconvex OPF model into an equivalent conic model. By applying two propositions presented in this work, the trigonometric constraint is solved in a pre-processing stage by a local optimization solver, in this case, the KNITRO solver, which considers all the possibilities of the KKT points to obtain the convex envelopes and find a completely convex OPF model, is used. The model is implemented in AMPL and is solved via global optimization solvers while to show the effectiveness of the model several IEEE systems such as the IEEE 14-, 30-, 57-, and 118-bus systems are used. The obtained results are validated by comparing them with the results provided by Matpower, which is an OPF solver. As a contribution of this thesis, the obtained convex OPF model is used as an application in the active and reactive optimal power dispatch problem, considering competition via bilevel programming. Two bilevel models and two single-level models are presented. The convex iterative model uses the proposed convex OPF model, and the nonlinearities are convexified using McCormick envelopes. The concept of strong duality is employed to obta... (Complete abstract click electronic access below) / Doutor

Ce travail présente une optimisation bi-niveau pour la conception de réseaux durables de ressources dans les parcs éco-industriels (EIP). Tout d'abord, les méthodes d'optimisation multiobjectif sont explorées afin de gérer la nature multicritère des problèmes de conception de réseaux dans les EIP. Ensuite, différents cas d’étude sont explorés et analysés afin de maintenir un équilibre concernant les coûts opératoires des usines, tout en minimisant la consommation des ressources naturelles. Ainsi, le problème est modélisé selon une structure bi-niveau reprenant les concepts de la théorie des jeux, où les usines des entreprises jouent un jeu de Nash entre elles, tout en étant dans une structure de jeu de Stackelberg avec l'autorité environnementale. Cette structure définit un modèle qui doit être transformé en un problème MOPEC (Multiple Optimization Problems with Equilibrium Constraints). Différents cas d’étude sont explorés : le premier cas est le réseau d'eau mono-polluant d’un EIP dans lequel l’influence des paramètres opératoires des usines est étudiée afin de déterminer ceux qui favorisent la symbiose entre les usines. Le réseau d'eau est composé d'un nombre fixe de procédés et d’unités de régénération où les concentrations maximales d’entrée et de sortie des polluants sont définies a priori. L'objectif est alors de déterminer quelles sont les allocations entre procédés et unités de régénération. Les résultats obtenus mettent en évidence les avantages de la structure du modèle proposée par rapport aux approches multiobjectif traditionnelles, en obtenant des gains économiques équilibrés d’usines différentes (gains entre 12-25%) tout en maintenant une faible consommation globale des ressources. Ensuite, d'autres études de cas sont abordées à l'aide de la structure bi-niveau : il s’agit d'inclure simultanément les réseaux d'énergie et d’eau dans une formulation multileader multi-follower où les deux «autorités » environnementales sont supposées jouer un jeu non-coopératif de Nash. Dans un premier cas, le gain économique est plus important en incluant des réseaux d'énergie dans la structure de l’EIP. La deuxième étude de cas industriel explore un modèle de réseau d’utilités offre-demande où l'autorité environnementale vise à minimiser les émissions totales de CO2 dans le parc. La conclusion des différents cas explorés montre des résultats extrêmement favorables en termes de coût et d’impact environnemental ce qui vise à encourager les entreprises à participer à l'EIP. / This work presents a bilevel programming framework for the design of sustainable resource networks in eco-industrial parks (EIP). First, multiobjective optimization methods are explored in order to manage the multi-criteria nature of EIP network design problems. Then, different case studies are modeled in order to minimize and maintain in equilibrium participating plants operating costs while minimizing resource consumption. Thus, the structure of the model is constituted by a bilevel programming framework where the enterprises’ plants play a Nash game between them while being in a Stackelberg game structure with the authority. This structure defines a model which, in order to be solved, has to be transformed into a MOPEC (Multiple Optimization Problems with Equilibrium Constraints) structure. Regarding the case studies, monocontaminant water networks in EIP are studied first, where the influence of plants operating parameters are studied in order to determine the most important ones to favor the symbiosis between plants. The water network is composed of a fixed number of process and water regeneration units where the maximal inlet and outlet contaminant concentrations are defined a priori. The aim is to determine which processes are interconnected and the water regeneration allocation. Obtained results highlight the benefits of the proposed model structure in comparison with traditional multiobjective approaches, by obtaining equilibrate different plants operating costs (i.e. gains between 12-25%) while maintaining an overall low resource consumption. Then, other case studies are approached by using the bilevel structure to include simultaneously energy networks in a multi-leader-multi-follower formulation where both environmental authorities are assumed to play a noncooperative Nash game. In the first case study, economic gain is proven to be more significant by including energy networks in the EIP structure. The second industrial case study explores a supply-demand utility network model where the environmental authority aims to minimize the total equivalent CO2 emissions in the EIP. In all cases, the enterprises’ plants are encouraged to participate in the EIP by the extremely favorable obtained results.

Made available in DSpace on 2016-12-23T14:33:41Z (GMT). No. of bitstreams: 1 dissertacao.pdf: 1222375 bytes, checksum: 25701e5d822c85de67ae48d04a4d24df (MD5) Previous issue date: 2010-03-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work gives a rigorous approach of bilevel problems, especially the linear case. Proofs of known results in the literature are reproduced or remade. As motivation for the reader, classic problems are reformulated as bilevel problems. In theoretical point of view, some contributions are the formalization of relations between models of literature; their extensions to multilevel problems; the result that complements the equivalence between optimal solutions of the models in linear optimistic case; and the generalization of the method of Calamai and Vicente for generation of linear test problems. In practical point of view, the contribution is a new algorithm for local optimal solutions of linear problems, which differs from other methods in generality: treat unlimited problems, and only requires that the problem s polyhedron does not have degenerate faces. / Este trabalho aborda de forma rigorosa o problema de dois níveis, sobretudo o caso linear. Resultados conhecidos da literatura tiveram suas demonstrações reproduzidas, ou refeitas. Como motivaçãoo para o leitor, formulações de problemas clássicos como problemas de dois níveis foram expostas. No aspecto teórico, destacam-se como contribuições a formalizaçãoo das relações entre os modelos usualmente encontrados na literatura; suas extensões para problemas multinível; o resultado que complementa a equivalência entre soluções ótimas dos modelos para o caso linear otimista; e a generalização do método de Calamai e Vicente para geração de problemas-teste lineares. No aspecto prático, destaca-se o novo método para soluções ótimas locais de problemas lineares, cujo diferencial diante de outros métodos é a generalidade: engloba ilimitabilidade, e exige apenas que o poliedro do problema não tenha faces degeneradas.