We present StochasticPrograms.jl, a user-friendly and powerful open-source framework for stochastic programming written in the Julia language. The framework includes both modeling tools and structure-exploiting optimization algorithms. Stochastic programming models can be efficiently formulated using an expressive syntax, and models can be instantiated, inspected, and analyzed interactively. The framework scales seamlessly to distributed environments. Small instances of a model can be run locally to ensure correctness, whereas larger instances are automatically distributed in a memory-efficient way onto supercomputers or clouds and solved using parallel optimization algorithms. These structure-exploiting solvers are based on variations of the classical L-shaped, progressive-hedging, and quasi-gradient algorithms. We provide a concise mathematical background for the various tools and constructs available in the framework along with code listings exemplifying their usage. Both software innovations related to the implementation of the framework and algorithmic innovations related to the structured solvers are highlighted. We conclude by demonstrating strong scaling properties of the distributed algorithms on numerical benchmarks in a multinode setup. 

We develop a fast smoothing procedure for solving linear two-stage stochastic programs, which outperforms the well-known L-shaped algorithm on large-scale benchmarks. We derive problem-dependent bounds for the effect of smoothing and characterize the convergence rate of the proposed algorithm. The theory suggests that the smoothing scheme can be sped up by sacrificing accuracy in the final solution. To obtain an efficient and effective method, we suggest a hybrid solution that combines the speed of the smoothing scheme with the accuracy of the L-shaped algorithm. We benchmark a parallel implementation of the smoothing scheme against an efficient parallelized L-shaped algorithm on three large-scale stochastic programs, in a distributed environment with 32 worker cores. The smoothing scheme reduces the solution time by up to an order of magnitude compared to L-shaped.

Stochastic programming is a subfield of mathematical programming concerned with optimization problems subjected to uncertainty. Many engineering problems with random elements can be accurately modeled as a stochastic program. In particular, decision problems associated with hydropower operations motivate the application of stochastic programming. When complex decision-support problems are considered, the corresponding stochastic programming models often grow too large to store and solve on a single computer. This warrants a need for parallel approaches to enable efficient treatment of large-scale stochastic programs in a distributed environment. In this thesis, we develop mathematical and computational tools to efficiently store and solve distributed stochastic programs.

  First, we present a software framework for stochastic programming implemented in the Julia programming language. A key feature of the framework is the support for distributing stochastic programs in memory. Moreover, the framework includes a large set of structure-exploiting algorithms for solving stochastic programming problems. These algorithms are based on the classical L-shaped, progressive-hedging, and quasi-gradient algorithms and can be run in parallel on distributed stochastic programs. The distributed performance of our software framework is improved by exploring algorithmic innovations and software patterns. We present the architecture of the framework and highlight key implementation details. Finally, we provide illustrative examples of stochastic programming functionality and benchmarks on large-scale problems.

  Then, we pursue further algorithmic improvements to the distributed L-shaped algorithm. Specifically, we consider the use of dynamic cut aggregation. We develop theoretical results on convergence and complexity and then showcase performance improvements in numerical experiments. We suggest several aggregation schemes that are based on parameterized selection rules. In brief, cut aggregation can bring major performance improvements to L-shaped algorithms in distributed settings.

  Next, we consider a fast smoothing scheme for large-scale stochastic programming. We derive a smooth approximation of the subproblems in the quasi-gradient algorithm. This allows us to utilize modern acceleration methods for gradient descent. We derive problem-dependent approximation bounds and convergence properties and note a trade-off between accuracy and speed. We then pose a hybrid procedure that is both fast and accurate and show that it is competitive with the L-shaped method on large-scale benchmarks.

  Finally, we consider applications to hydropower operations. We consider three case studies in the Swedish river Skellefteälven. The day-ahead planning problem involves specifying optimal order volumes in a deregulated electricity market, without knowledge of the next-day market price, and then optimizing the hydropower production. We provide a detailed introduction to the day-ahead model and explain how it can be implemented in our framework. Using a sample-based algorithm that internally relies on our structure-exploiting solvers, we obtain tight confidence intervals around the optimal solution of the day-ahead problem. We then consider a maintenance scheduling problem as a variation of the day-ahead problem. Last, we consider a capacity expansion problem with a long planning horizon.

Stokastisk programmering är ett område inom optimeringslära som behandlar beslutsproblem under osäkerhet. Ingenjörsproblem som innehåller slumpmässiga element kan modelleras noggrant med stokastiska program. Planering av vattenkraftsdrift är en specifik tillämpning som har motiverat mycket av arbetet i den här avhandlingen. Komplexa beslutsproblem leder ofta till stokastiska programmeringsproblem vars storlek överskrider kapaciteten hos moderna persondatorer. Det behövs därför skalbara beräkningsmetoder som kan exekveras i en distribuerad miljö bestående av flera samverkande datorer. I denna avhandling utvecklar vi matematiska metoder och beräkningsverktyg som kan användas för att representera och lösa distribuerade stokastiska program effektivt.

  I den första delen av avhandlingen presenterar vi ett ramverk för stokastisk programmering som implementerats i programmeringsspråket Julia. En nyckelfunktion i ramverket är möjligheten att instansiera distribuerade stokastiska program. Ramverket innehåller också en uppsättning optimeringsalgoritmer för att lösa stokastiska program genom att utnyttja problemens struktur. Dessa algoritmer är baserade på metoderna ``L-shaped'', ``progressive-hedging'', och ``quasi-gradient'' och kan appliceras parallellt på distribuerade stokastiska program. Vi presenterar algoritmiska innovationer och designmönster som ger förbättrad prestanda i distribuerade miljöer. Vi redogör även för programpaketes struktur och belyser viktiga detaljer i implementationen. Vi demonstrerar slutligen ramverkets funktionalitet med enkla exempel och tillhandahåller prestandatester utförda på storskaliga problem.

  I följande kapitel fortsätter vi med att undersöka förbättringar av den distribuerade L-shaped metoden. Speciellt undersöker vi dynamisk snittaggregering. Vi utvecklar teori som beskriver algoritmens konvergens och komplexitet och genom numeriska experiment visar vi sedan prestandaförbättringar. Vi föreslår olika aggregeringstrategier baserade på parametriserade urvalsregler. Snittaggregering kan avsevärt förbättra prestandan hos distribuerade L-shaped algoritmer.

  Sedan undersöker vi en slätningsmetod för storskalig stokastisk programmering. We härleder en slät approximation av subproblemen i kvasigradientalgoritmen, vilket låter oss bruka moderna acceleringsmetoder för gradientbaserade algoritmer. We härleder problemberoende approximationsgränser  och konvergensegenskaper och noterar en avvägning mellan noggrannhet och lösningshastighet. We föreslår sedan en hybrid metod som är både snabb och noggrann och visar att den är konkurrenskraftig jämfört med L-shaped i storskaliga experiment.

  Slutligen applicerar vi våra beräkningsmetoder på beslutsproblem från vattenkraftsindustrin. Vi studerar tre fallstudier kring Skellefteälven. Det första problemet berör budstrategier för en vattenkraftsproducent som deltar på en avreglerad elmarknad. Målet är att bestämma optimala bud på en spotmarknad innan marknadspriset är fastställt och sedan optimera kommande dags vattenkraftsproduktion. Vi ger en detaljerad beskrivning av budgivningsproblemet och förklarar sedan hur modellen kan implementeras i vårat ramverk. Genom att använda en stickprovsbaserad metod, som bygger på våra strukturnyttjande algoritmer, så kan vi beräkna ett konfidensintervall kring budgivningsproblemets optimala värde med hög precision. Sedan undersöker vi en version av budgivningsproblemet där vi även schemalägger förebyggande underhåll av kraftstationerna. Slutligen ställer vi upp ett kapacitetsexpansionsproblem med lång planeringshorisont.

This paper presents a methodology for strategic day-ahead planning that uses a combination of deep learning and optimization. A noise-driven recurrent neural network structure is proposed for forecasting electricity prices and local inflow to water reservoirs. The resulting forecasters generate predictions with seasonal variation without relying on long input sequences. This forecasting method is employed in a stochastic program formulation of the day-ahead problem. This results in optimal order strategies for a price-taking hydropower producer participating in the Nordic day-ahead market. Using an open-source software framework for stochastic programming, the model is implemented and distributed over multiple cores. The model is then solved in parallel using a sampling-based algorithm. Tight confidence intervals around the stochastic solution are provided, which show that the gain from adopting a stochastic approach is statistically significant. 

Stochastic programming is a subfield of mathematical programming concerned with optimization problems subjected to uncertainty. Many engineering problems with random elements can be accurately modeled as a stochastic program. In particular, decision problems associated with hydropower operations motivate the application of stochastic programming. When complex decision-support problems are considered, the corresponding stochastic programming models often grow too large to store and solve on a single computer. This clarifies the need for parallel approaches that could enable efficient treatment of large-scale stochastic programs in a distributed environment. In this thesis, we develop mathematical and computational tools in order to facilitate distributed stochastic programs that can be efficiently stored and solved.

First, we present a software framework for stochastic programming implemented in the Julia language. A key feature of the framework is the support for distributing stochastic programs in memory. Moreover, the framework includes a large set of structure-exploiting algorithms for solving stochastic programming problems. These algorithms are based on the classical L-shaped and progressive-hedging algorithms and can run in parallel on distributed stochastic programs. The distributed performance of our software tools is improved by exploring algorithmic innovations and software patterns. We present the architecture of the framework and highlight key implementation details. Finally, we provide illustrative examples of stochastic programming functionality and benchmarks on large-scale problems.

Then, we pursue further algorithmic improvements to the distributed L-shaped algorithm. Specifically, we consider the use of dynamic cut aggregation. We develop theoretical results on convergence and complexity and then showcase performance improvements in numerical experiments. We suggest several aggregation schemes that are based on parameterized selection rules. Before we perform large-scale experiments, the aggregation parameters are determined by a tuning procedure. In brief, cut aggregation can yield major performance improvements to L-shaped algorithms in distributed settings.

Finally, we consider an application to hydropower operations. The day-ahead planning problem involves specifying optimal order volumes in a deregulated electricity market, without knowledge of the next-day market price, and then optimizing the hydropower production. We provide a detailed introduction to the day-ahead model and explain how we can implement it with our computational tools. This covers a complete procedure of gathering data, generating forecasts from the data, and finally formulating and solving a stochastic programming model of the day-ahead problem. Using a sample-based algorithm that internally relies on our structure-exploiting solvers, we obtain tight confidence intervals around the optimal solution of the day-ahead problem.

We present POLO. j1- a Julia package that helps algorithm developers and machine-learning practitioners design and use state-of-the-art parallel optimization algorithms in a flexible and efficient way. POLO. j1 extends our C+ + library POLO, which has been designed and implemented with the same intentions. POLO. j1 not only wraps selected algorithms in POLO and provides an easy mechanism to use data manipulation facilities and loss function definitions in Julia together with the underlying compiled C+ + library, but it also uses the policy-based design technique in a Julian way to help users prototype optimization algorithms from their own building blocks. In our experiments, we observe that there is little overhead when using the compiled C+ + code directly within Julia. We also notice that the performance of algorithms implemented in pure Julia is comparable with that of their C+ + counterparts. Both libraries are hosted on GitHub(1)under the free MIT license, and can be used easily by pulling the pre-built 64-bit architecture Docker images.(2)

We present LShapedSolvers.jl, a suite of scalable stochastic programming solvers implemented in the Julia programming language. The solvers, which are based on the L-shaped algorithm, run efficiently in parallel, exploit problem structure, and operate on distributed data. The implementation introduces several flexible high-level abstractions that result in a modular design and simplify the development of algorithm variants. In addition, we demonstrate how the abstractions available in the Julia module for distributed computing are exploited to simplify the implementation of the parallel algorithms. The performance of the solvers is evaluated on large-scale problems for finding optimal orders on the Nordic day-ahead electricity market. With 16 worker cores, the fastest algorithm solves a distributed problem with 2.5 million variables and 1.5 million linear constraints about 19 times faster than Gurobi is able to solve the extended form directly.

A general trajectory planner for optimal control problems is presented and applied to a robot system. The approach is based on timed elastic bands and nonlinear model predictive control. By exploiting the sparsity in the underlying optimization problems the computational effort can be significantly reduced, resulting in a real-time capable planner. In addition, a localization based switching strategy is employed to enforce convergence and stability. The planning procedure is illustrated in a robotics application using a realistic SCARA type robot.

In this paper, we present a toolbox for structured model reduction developed for MATLAB. In addition to structured model reduction methods using balanced realizations of the subsystems, we introduce a numerical algorithm for structured model reduction using a subgradient optimization algorithm. We briefly present the syntax for the toolbox and its features. Finally, we demonstrate the applicability of various model reduction methods in the toolbox on a structured mass-spring mechanical system.