This thesis describes a stochastic ship routing problem with inventory management. The problem involves finding a set of least costs routes for a fleet of ships transporting a single commodity when the demand for the commodity is uncertain. Storage at consumption and supply ports is limited and inventory levels are monitored in the model. Consumer demands are at a constant rate within each time period in the deterministic problem, and in the stochastic problem, the demand rate for a period is not known until the beginning of that period. The demand situation in each time period can be described by a scenario tree with corresponding probabilities. Several possible solution approaches for solving the problem are studied in the thesis. This problem can be formulated as a mixed integer programming (MIP) model. However solving the problem this way is very time consuming even for a deterministic problem with small problem size. In order to solve the stochastic problem, we develop a decomposition formulation and solve it using a Branch and Price framework. A master problem (set partitioning with extra inventory constraints) is built, and the subproblems, one for each ship, involve solving stochastic dynamic programming problems to generate columns for the master problem. Each column corresponds to one possible tree of schedules for one ship giving the schedule for the ship for all demand scenarios. In each branch-and-bound node, the node problem is solved by iterating between the master problem and the subproblems. Dual variables can be obtained solving the master problem and are used in the subproblems to generate the most promising columns for the master problem. Computational results are given showing that medium sized problems can be solved successfully. Several extensions to the original model are developed, including a variable speed model, a diverting model, and a model which allows ships to do extra tasks in return for a bonus. Possible solution approaches for solving the variable speed and the diverting model are presented and computational results are given.

We propose a new approach to optimize operations of hydro storage systems with multiple connected reservoirs whose operators participate in wholesale electricity markets. Our formulation integrates short-term intraday with long-term interday decisions. The intraday problem considers bidding decisions as well as storage operation during the day and is formulated as a stochastic program. The interday problem is modeled as a Markov decision process of managing storage operation over time, for which we propose integrating stochastic dual dynamic programming with approximate dynamic programming. We show that the approximate solution converges towards an upper bound of the optimal solution. To demonstrate the efficiency of the solution approach, we fit an econometric model to actual price and in inflow data and apply the approach to a case study of an existing hydro storage system. Our results indicate that the approach is tractable for a real-world application and that the gap between theoretical upper and a simulated lower bound decreases sufficiently fast. (authors' abstract)

In this thesis we consider two research problems, namely, (i) language constructs for modelling stochastic programming (SP) problems and (ii) solution methods for processing instances of different classes of SP problems. We first describe a new design of an SP modelling system which provides greater extensibility and reuse. We implement this enhanced system and develop solver connections. We also investigate in detail the following important classes of SP problems: singlestage SP with risk constraints, two-stage linear and stochastic integer programming problems. We report improvements to solution methods for single-stage problems with second-order stochastic dominance constraints and two-stage SP problems. In both cases we use the level method as a regularisation mechanism. We also develop novel heuristic methods for stochastic integer programming based on variable neighbourhood search. We describe an algorithmic framework for implementing decomposition methods such as the L-shaped method within our SP solver system. Based on this framework we implement a number of established solution algorithms as well as a new regularisation method for stochastic linear programming. We compare the performance of these methods and their scale-up properties on an extensive set of benchmark problems. We also implement several solution methods for stochastic integer programming and report a computational study comparing their performance. The three solution methods, (a) processing of a single-stage problem with second-order stochastic dominance constraints, (b) regularisation by the level method for two-stage SP and (c) method for solving integer SP problems, are novel approaches and each of these makes a contribution to knowledge.

This thesis deals with multi-stage stochastic linear programming and its ap- plictions in the portfolio selection problem. It presents several models of invest- ment planning, the emphasis is on the basic model with transaction costs and risk adjusted model for every investment level. Random returns entering the above models are modelled by the scenario trees which are generated using the moment- matching method. The thesis presents the optimal investment strategy for each model. It then examines distance of optimal values of objective functions in de- pendence on the nested distance of these generated trees. All calculations were performed using Mathematica software version 9. 1

This work is concerned with the study of nonlinear nonconvex stochastic programming, in particular in the context of trust-region approaches. We first explore how to exploit the structure of multistage stochastic nonlinear programs with linear constraints, in the framework of primal-dual interior point methods. We next study consistency of sample average approximations (SAA) for general nonlinear stochastic programs. We also develop a new algorithm to solve the SAA problem, using the statistical inference information to reduce numercial costs, by means of an internal variable sample size strategy. We finally assess the numerical efficiency of the proposed method for the estimation of discrete choice models, more precisely mixed logit models, using our software AMLET, written for this purpose.

Dans cette thèse, nous étudions différents modèles, déterministes et stochastiques, pour les problèmes de dimensionnement de réseaux. Nous examinons également le problème du sac-à-dos stochastique ainsi que, plus généralement, les contraintes de capacité en probabilité. Dans une première partie, nous nous consacrons à des modèles de dimensionnement de réseaux déterministes, possédant de nombreuses contraintes techniques s'approchant de situations réalistes. Nous commençons par étudier deux modèles de réseaux de télécommunications. Le premier considère des réseaux multi-couches et des capacités sur les arcs, tandis que le second étudie des réseaux mono-couche, sans capacité, où les commodités doivent être acheminées sur un nombre K de chemins disjoint de taille au plus L. Nous résolvons ces deux problèmes grâce à un algorithme de ``branch-and-cut' basé sur la décomposition de Benders de formulations linéaires pour ces problèmes. La nouveauté de notre approche se situe principalement dans l'étude empirique de la fréquence optimale de génération de coupes au cours de l'algorithme. Nous étudions ensuite un problème d'expansion de réseaux de transmission électrique. Notre travail étudie différents modèles et formulations pour le problème, les comparant sur des réseaux brésiliens réels. En particulier, nous montrons que le re-dimensionnement permet des réductions de coût importantes. Dans une seconde partie, nous examinons des modèles de programmation stochastique. Premièrement, nous prouvons que trois cas particuliers du problème de sac-à-dos avec recours simple peuvent être résolu par des algorithmes de programmation dynamique. Nous reformulons ensuite le problème comme un programme non-linéaire en variables entières et testons un algorithme ``branch-and-cut' basé l'approximation extérieure de la fonction objective. Cet algorithme est ensuite transformé en un algorithme de ``branch-and-cut-and-price', utilisé pour résoudre un problème de dimensionnement de réseau stochastique avec recours simple. Finalement, nous montrons comment linéariser des contraintes de capacité en probabilité avec variables binaires lorsque les coefficients sont des variables aléatoires satisfaisant certaines propriétés.

Over the last year or so, we have witnessed the global effects and repercussions related to the field of finance. Supposed blue chip stocks and well-established companies have folded and filed for bankruptcy, an event that might have thought to been absurd two years ago. In addition, finance and investment science has grown over the past few decades to include a plethora of investment options and regulations. Now more than ever, developments in the field are carefully examined and researched by potential investors. This thesis involves an investigation and quantitative analysis of key money management problems. The primary area of interest is Portfolio Selection, where we develop advanced financial models that are designed for investment problems of the 21st century. Portfolio selection is the process involved in making large investment decisions to generate a collection of assets. Over the years the selection process has evolved dramatically. Current portfolio problems involve a complex, yet realistic set of managing constraints that are coupled to general historic risk and return models. We identify three well-known portfolio problems and add an array of practical managing constraints that form three different types of Mixed-Integer Programs. The product is advanced mathematical models related to risk-return portfolios, index tracking portfolios, and an integrated stock-bond portfolio selection model. The numerous sources of uncertainty are captured in a Stochastic Programming framework, and Goal Programming techniques are used to facilitate various portfolio goals. The designs require the consideration of modelling elements and variables with respect to problem solvability. We minimize trade-offs in modelling and solvability issues found in the literature by developing problem specific algorithms. The algorithms are tailored to each portfolio design and involve decompositions and heuristics that improve solution speed and quality. The result is the generation of portfolios that have intriguing financial outcomes and perform well with respect to the market. Portfolio selection is as dynamic and complex as the recent economic situation. In this thesis we present and further develop the mathematical concepts related to portfolio construction. We investigate the key financial problems mentioned above, and through quantitative financial modelling and computational implementations we introduce current approaches and advancements in field of Portfolio Optimization.

Over the last year or so, we have witnessed the global effects and repercussions related to the field of finance. Supposed blue chip stocks and well-established companies have folded and filed for bankruptcy, an event that might have thought to been absurd two years ago. In addition, finance and investment science has grown over the past few decades to include a plethora of investment options and regulations. Now more than ever, developments in the field are carefully examined and researched by potential investors. This thesis involves an investigation and quantitative analysis of key money management problems. The primary area of interest is Portfolio Selection, where we develop advanced financial models that are designed for investment problems of the 21st century. Portfolio selection is the process involved in making large investment decisions to generate a collection of assets. Over the years the selection process has evolved dramatically. Current portfolio problems involve a complex, yet realistic set of managing constraints that are coupled to general historic risk and return models. We identify three well-known portfolio problems and add an array of practical managing constraints that form three different types of Mixed-Integer Programs. The product is advanced mathematical models related to risk-return portfolios, index tracking portfolios, and an integrated stock-bond portfolio selection model. The numerous sources of uncertainty are captured in a Stochastic Programming framework, and Goal Programming techniques are used to facilitate various portfolio goals. The designs require the consideration of modelling elements and variables with respect to problem solvability. We minimize trade-offs in modelling and solvability issues found in the literature by developing problem specific algorithms. The algorithms are tailored to each portfolio design and involve decompositions and heuristics that improve solution speed and quality. The result is the generation of portfolios that have intriguing financial outcomes and perform well with respect to the market. Portfolio selection is as dynamic and complex as the recent economic situation. In this thesis we present and further develop the mathematical concepts related to portfolio construction. We investigate the key financial problems mentioned above, and through quantitative financial modelling and computational implementations we introduce current approaches and advancements in field of Portfolio Optimization.

La posada en marxa del Mercat Ibèric de l'Electricitat va introduir al sector elèctric espanyol un seguit de nous mecanismes de participació que han forçat els agents a renovar les seves polítiques de gestió. D'aquesta nova situació sorgeix l'oportunitat d'estudiar noves estratègies d'oferta a curt termini per a companyies de generació price-taker que participin diàriament al Mercat Ibèric de l'Electricitat. Aquestes estratègies se centraran al mercat diari, ja que és aquí on es negocia un 80% de l'electricitat que es consumeix diàriament a Espanya i on s'integren gran part de la resta de mecanismes de participació. La liberalització dels mercats elèctrics obre a noves tècniques d'optimització els problemes clàssics de gestió de l'energia. En particular, atesa la incertesa que l'existència del mercat ocasiona als preus, les tècniques de programació estocàstiques es converteixen en la forma més natural per abordar aquests problemes. Als mercats elèctrics el preu es fixa horàriament com a resultat d'un procés de casació , és a dir que quan l'agent ha d'efectuar la seva oferta desconeix el preu al qual li vindrà remunerada l'energia. Aquesta incertesa fa imprescindible l'ús de tècniques estadístiques per obtenir informació del mercat i introduir-la als models d'optimització. En aquest aspecte, una de les contribucions d'aquesta tesi és l'estudi dels preus del mercat de l'electricitat a Espanya i el seu modelat mitjançant models factorials. D'altra banda, s'hi es descriuen els nous mecanismes presents al Mercat Ibèric de l'Electricitat que afecten directament la producció física de les unitats. En particular, s'inclou el modelat detallat dels contractes de futurs físics i bilaterals i de la seva inclusió a l'oferta del mercat diari per part de les companyies de generació. Als models presentats, es tenen en compte explícitament les regles del mercat, així com les clàssiques restriccions d'operació de les unitats, tant tèrmiques com de cicle combinat. A més, es deriva i es demostra l'expressió de la funció d'oferta. Per tant, els models construïts són una eina per decidir l'assignació de les unitats, la generació dels contractes de futurs físics i bilaterals a través seu i l'oferta òptima d'una companyia de generació. Un cop s'han cobert aquests objectius, es presenta una millora dels models mitjançant la inclusió de la seqüència de mercats de molt curt termini per tal de modelar la influència que tenen en l'oferta al mercat diari. Aquests mercats es casen just abans i durant el dia en què l'energia ha de ser consumida, i això permetrà veure com la possibilitat d'augmentar els beneficis participant-hi afecta directament les estratègies d'oferta òptima del mercat diari. Els models presentats en aquest treball han estat provats amb dades reals provinents del Mercat Ibèric de l'Electricitat i d'una companyia de generació que hi opera. Els resultats obtinguts són adequats i es discuteixen al llarg del document / La puesta en marcha del Mercado Ibérico de la Electricidad introdujo en el sector eléctrico español una serie de nuevos mecanismos de participación que han forzado a los agentes a renovar sus políticas de gestión. De esta nueva situación surge la oportunidad de estudiar nuevas estrategias de oferta para las compañías de generación. Esta tesis se enmarca en las estrategias de oferta a corto plazo para compañías de generación price-taker que participen diariamente en el Mercado Ibérico de la Electricidad. Estas estrategias se centraran en el mercado diario ya que es donde se negocia un 80% de la electricidad consumida diariamente en España y es donde se integran gran parte del resto de los mecanismos de participación. La liberalización de los mercados eléctricos permite aplicar nuevas técnicas de optimización a los problemas clásicos de gestión de la energía. En concreto, dada la incertidumbre en el precio existente en el mercado, las técnicas de programación estocástica se convierten en la forma más natural para abordar estos problemas. En los mercados eléctricos el precio se fija horariamente como resultado de un proceso de casación, es decir, cuando el agente debe efectuar sus ofertas desconoce el precio al que la energía le será pagada. Esta incertidumbre hace imprescindible el uso de técnicas estadísticas para obtener información del mercado e introducirla en los modelos de optimización. En este aspecto, una de las contribuciones de esta tesis es el estudio del precio de la electricidad en España y su modelado mediante modelos factoriales. Se describen los nuevos mecanismos presentes en el Mercado Ibérico de la Electricidad que afectan directamente a la producción física de las unidades. En particular, se incluye una modelización detallada de los contratos de futuros físicos y bilaterales y su inclusión en la oferta enviada al mercado diario por las compañías de generación. En los modelos presentados se tiene en cuenta explícitamente las reglas del mercado así como las clásicas restricciones de operación de las unidades, tanto térmicas como de ciclo combinado. La expresión de la función de oferta óptima se deriva y se demuestra. Por lo tanto, los modelos construidos son una herramienta para decidir la asignación de unidades, la generación de los contratos de futuros físicos y bilaterales a través de ellas y la oferta óptima de una compañía de generación. Una vez alcanzados estos objetivos, se presenta una mejora del modelo con la inclusión de la secuencia de mercados de muy corto plazo. El objetivo es modelar la influencia que esta tiene en la oferta al mercado diario. Estos mercados se casan justo antes y durante el día en el que la energía va a ser consumida y se verá cómo la posibilidad de aumentar los beneficios participando en ellos afecta a las estrategias de oferta óptima del mercado diario. Los modelos presentados en este trabajo se han probado con datos reales procedentes del Mercado Ibérico de la Electricidad y de una compañía de generación que opera en él. Los resultados obtenidos son adecuados y se discuten a lo largo del documento. / The start-up of the Iberian Electricity Market introduced a set of new mechanisms in the Spanish electricity sector that forced the agents participating in the market to change their management policies. This situation created a great opportunity for studying the bidding strategies of the generation companies in this new framework. This thesis focuses on the short-term bidding strategies of a price-taker generation company that bids daily in the Iberian Electricity Market. We will center our bidding strategies on the day-ahead market because 80% of the electricity that is consumed daily in Spain is negotiated there and also because it is the market where the new mechanisms are integrated. The liberalization of the electricity markets opens the classical problems of energy management to new optimization approaches. Specifically, because of the uncertainty that the market produces in the prices, the stochastic programming techniques have become the most natural way to deal with these problems. Notice that, in deregulated electricity markets the price is hourly fixed through a market clearing procedure, so when the agent must bid its energy it is unaware of the price at which it will be paid. This uncertainty makes it essential to use some statistic techniques in order to obtain the information coming from the markets and to introduce it in the optimization models in a suitable way. In this aspect, one of the main contributions of this thesis has been the study the Spanish electricity price time series and its modeling by means of factor models. In this thesis, the new mechanism introduced by the Iberian Market that affects the physical operation of the units is described. In particular, it considers in great detail the inclusion of the physical futures contracts and the bilateral contracts into the day-ahead market bid of the generation companies. The rules of the market operator have been explicitly taken into account within the mathematical models, along with all the classical operational constraints that affect the thermal and combined cycle units. The expression of the optimal bidding functions are derived and proved. Therefore, the models built in this thesis provide the generation company with the economic dispatch of the committed futures and bilateral contracts, the unit commitment of the units and the optimal bidding strategies for the generation company. Once these main objectives were fulfilled, we improved the previous models with an approach to the modeling of the influence that the sequence of very short markets have on optimal day-ahead bidding. These markets are cleared just before and during the day in which the electricity will be consumed and the opportunity to obtain benefits from them changes the optimal day-ahead bidding strategies of the generation company, as it will be shown in this thesis. The entire models presented in this work have been tested using real data from a generation company and Spanish electricity prices. Suitable results have been obtained and discussed.

Based on the recent successes in stochastic linear programming and mixed integer programming, in this thesis we combine these two important areas of mathematical programming; specifically we study stochastic integer programming. We first study a simple and important stochastic integer programming problem, called stochastic uncapacitated lot-sizing (SLS), which is motivated by production planning under uncertainty. We describe a multi-stage stochastic integer programming formulation of the problem and develop a family of valid inequalities, called the (Q, S) inequalities. We establish facet-defining conditions and show that these inequalities are sufficient to describe the convex hull of integral solutions for two-period instances. A separation heuristic for (Q, S) inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the inequalities as cuts. Then, motivated by the polyhedral study of (Q, S) inequalities for SLS, we analyze the underlying integer programming scheme for general stochastic integer programming problems. We present a scheme for generating new valid inequalities for mixed integer programs by taking pair-wise combinations of existing valid inequalities. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some special cases, we identify combination sequences that lead to a manageable set of all non-dominated inequalities. For the general scenario tree case, we identify combination sequences that lead to non-dominated inequalities. We also analyze the conditions such that the inequalities generated by our approach are facet-defining and describe the convex hull of integral solutions. We illustrate the framework for some deterministic and stochastic integer programs and we present computational results which show the efficiency of adding the new generated inequalities as cuts.