ICMS

CARIPLO Workshop on Numerical Linear and Nonlinear Stochastic Programming

Sep 3, 2008 - Sep 5, 2008

Ashworth Building, King's Buildings, University of Edinburgh

Organisers

Name	Institution
Cartis, Coralia	University of Edinburgh
Colombo, Marco	University of Edinburgh
Gondzio, Jacek	University of Edinburgh, School of Mathematics
Grothey, Andreas	University of Edinburgh, School of Mathematics

Keynote Plenary Lectures given by:

Giorgio Consigli, University of Bergamo, Italy
Michael Dempster, University of Cambridge, UK
Gautam Mitra, Brunel University, UK
Georg Pflug, University of Vienna, Austria
Alex McNeil, Heriot-Watt University, UK
Marc Steinbach, University of Hannover, Germany

This workshop aims is to bring together, for training and networking purposes, PhD students, young researchers and experts in these diverse aspects of numerical linear and nonlinear stochastic programming.

Many real-life problems involve uncertainty in their data, such as portfolio optimisation with uncertain future asset prices, utility distribution with uncertain demand, or robust network design with uncertain reliability of links. Stochastic programming is a popular approach to decision making under uncertainty, leading to very large-scale problems with challenging solutions. It is also highly interdisciplinary, involving researchers that work on scenario generation, computational and theoretical linear and nonlinear optimization and modeling. The focus of the workshop is to present and discuss in an accessible manner promising mathematical and computational avenues for tackling the current challenges in this area.

Scientific committee
Giorgio Consigli, University of Bergamo (Italy)
Jacek Gondzio, University of Edinburgh (UK)
Andreas Grothey , University of Edinburgh (UK)
Gautam Mitra, Brunel University (UK)
Georg Pflug, University of Vienna (Austria)
Alexei Gaivoronski, University of Trondheim (Norway)

Programme
The workshop will be structured into plenary lectures (of 1h each) that give an overview over the various aspects of numerical linear and nonlinear stochastic programming and sessions of contributed talks by conference participants (of about 30min each).

Scholarships
25 scholarships for a value of up to EUR300 each, to cover travel, accommodation and registration costs are available from the Cariplo foundation through the University of Bergamo. Participants interested in these scholarships should send an abstract of their talk and a short CV to:

Giorgio Consigli (giorgio.consigli@unibg.it) or
Andreas Grothey (A.Grothey@ed.ac.uk)

Please do not use the application form on this page to apply for a scholarship. Applications will be processed as they arrive. The closing date for sponsorship applications is 15 June 2008. Successful sponsorships will be communicated at the latest 4 weeks after their submission.
The registration fee will be automatically deducted from the award and the remainder will be refunded after the event. Receipts will be required.

Supporting institutions
This workshop is supported by the Cariplo Foundation website, as part of a network of stochastic programming research and training meetings, with the first edition being held at the University of Bergamo (Spring School in Stochastic Programming website).
Other sponsors include:
OptiRisk
CARISMA
Edinburgh Mathematical Society
Glasgow Mathematical Journal Trust
Cariplo Foundation
Maxwell Institute

Arrangements

Venue
Lecture Theatre 3, Ashworth Building, Kings Buildings, University of Edinburgh . Lecture Theatre 3 (Room 1.107) is located on the first floor of the Ashworth Building, accessed via Gateway 2 from West Mains Road. It can seat 88 and contains an XGA data projector, a dedicated PC, facilities for laptop input, DVD/VCR playback facilities, a visualiser, a PA radio mic, a stereo amp, audio record facilities, a 400W OHP, a 35mm slide projector, a laser pointer, an induction loop, two screens and a whiteboard.

Participation
You may register your interest in attending this meeting by completing the application form on this page. Please note that this form will close on 15 August 2008. After you have completed the form you will receive an e-mail with instructions on how to pay the registration fee (see below). You will only be accepted as a participant once payment has been received.

If you do not receive an e-mail please contact Irene Moore.

Financial arrangements
There will be a registration fee of 100.00 GBP, payable by all participants.
Late registration (from 1 August 2008): 150.00 GBP.

Accommodation
You are asked to reserve your own accommodation.
A list of Edinburgh accommodation of various sorts and prices is detailed below:

Edinburgh First, The University of Edinburgh, 18 Holyrood Park Road, Edinburgh EH16 5AY
0800 028 7118 (UK only) - +44 (0)131 651 2189 - edfirst1.ednet.co.uk
Edinburgh First offers a range of accommodation from standard single to twin en-suite rooms.

The Northumberland Hotel, 31-33 Craigmillar Park, Edinburgh EH16 5PE
+44 (0)131 668 3131 website

St Christophers Hostel, 9-13 Market Street, Edinburgh EH1 1DE
+44 (0)20 7407 1856 - www.st-christophers.co.uk - bookings@st-christophers.co.uk

Other accommodation can be found at this link

Meals and refreshments
Coffee will be available during dedicated breaks opposite the Lecture Theatre. Please note that this room will only be available during breaks as it is use at all other times.
Lunch vouchers will be provided at registration. These will allow participants to purchase lunch, on Wednesday, Thursday and Friday, at KB House.
A wine reception and buffet will be held in the Raeburn Room at Old College on Wednesday evening followed by a guided tour of Edinburgh.
The workshop dinner will be held at Blonde, 75 St. Leonard’s Street, Edinburgh on Thursday evening.
Directions to all the above will be included in your registration booklet.

Organising committee
Andreas Grothey (chairman)
Coralia Cartis
Marco Colombo
Jacek Gondzio

Programme

Wednesday 3 September

08.30 – 08.55	Registration
08.55 - 09.00	Welcome address
09.00 – 10.00	Plenary talk: Georg Pflug (University of Vienna) The mathematics of scenario generation
10.00 – 10.30	Coffee/Tea
	Contributed talks session - Applications
10.30 – 10.55	Cristina Corchero (Universitat Politecnica de Catalunya) Stochastic optimal day-ahead bid with physical future contracts
10.55 – 11.20	Saverio Giuliani (University of Foggia) A stochastic programming approach for strategic planning with activity based costing
11.20 – 11.45	Thomas Surowiec (Humboldt University Berlin) Analysis of M-stationary points and solutions to an SEPEC modeling oligopolistic competition
11.45 – 12.10	Xinan Yang (University of Edinburgh) Modelling and solving the stochastic top-percentile pricing problem by dynamic technique
12.10 – 12.35	Chris Dent (University of Edinburgh) The security constrained optimal power flow -- not a stochastic optimisation problem
12.35 – 13.45	Lunch
13.45 – 14.45	Plenary talk: Michael Dempster (University of Cambridge) Solution techniques for large scale dynamic stochastic programming problems
14.45 – 15.15	Coffee/Tea
15.15 – 16.30	Contributed talks session – Interger and Global
15.15 - 15.40	Uwe Gotzes (University of Duisburg-Essen) Increasing convex order constraints induced by mixed integer linear recourse
15.40 – 16.05	Thong Nguyen Huu (Ho Chi Minh City University of Pedagogy) A new stochastic algorithm for optimization problems
16.05 – 16.30	Dimitri Drapkin (University of Duisburg-Essen) A cutting plane algorithm for optimization problems with stochastic order
17.30 – 19.00	Wine reception and buffet in the Raeburn Room, Old College, University of Edinburgh
19.00 – 20.00	Guided tour of Edinburgh

Thursday 4 September

09.00 - 10.00	Plenary talk: Gautam Mitra (Brunel University) Software tool for decision making under uncertainty: a combined paradigm of SP and simulation
10.00 – 10.30	Coffee/Tea
10.30 – 12.30	Contributed talks session - Finance
10.30 – 10.55	Csaba Fabian (Kecskemet College and Eotvos Lorand University) An enhanced model for portfolio choice with SSD criteria: a constructive approach
10.55 – 11.20	Sona Kilianova (Comenius University) On solving some problems of dynamic stochastic programming by means of stochastic dynamic programming
11.20 – 11.45	Anne Marie Boiden Pedersen (University of Copenhagen) Integrated mortgage loan and pension planning
11.45 - 12.10	Alessandro Staino (University of Palermo) A stochastic programming approach to the optimal insurance of government bonds
12.10 – 12.35	David Wozabal (University of Vienna) A new method for Value-at-Risk constrained optimization using the difference of convex algorithm
12.35 – 13.45	Lunch
13.45 – 14.45	Plenary talk: Marc Steinbach (Leibniz Universität Hannover) Interior point algorithms for nonconvex multistage stochastic programs
14.45 – 15.15	Coffee/Tea
	Contributed talks session - Algorithms
15.15 – 15.40	Martin Branda (Charles University in Prague) Software for multistage stochastic linear programming problems
15.40 – 16.05	Kian Ping Chan (Imperial College London) An iterative primal-dual aggregation algorithm for multi-stage stochastic quadratic programs
16.05 – 16.30	Marco Colombo (University of Edinburgh) OOPS: A structure-exploiting parallel solver
16.30 – 16.55	Kristian Woodsend (University of Edinburgh) A structure-conveying modelling language
16.55 – 17.10	Break
	Contributed talks session – Scenario Generation
17.10 - 1735	Gaetano Iaquinta (University of Bergamo) A forward method for scenario generation with linear and nonlinear stochastic programs
17.35 – 18.00	Stefan Vigerske (Humboldt University Berlin) Decomposition of multistage stochastic programs with recombining scenario trees
18.00 – 18.25	Michal Kaut (Molde University College) Solution methods for a multi-item newsvendor model with substitution
19.30	Workshop dinner at Blonde, 75 St Leonard’s Street, Edinburgh

Friday 5 September

09.00 - 10.00	Plenary talk: Giorgio Consigli (University of Bergamo) SP-based dynamic optimization of a corporate portfolio subject to credit risk
10.00 – 10.30	Coffee/Tea
	Contributed talks session - Applications
10.30 – 10.55	Francesca Maggioni (Università degli studi di Bergamo) Stochastic second-order cone programming in mobile ad-hoc networks
10.55 – 11.20	Nicole Nowak (Technische Universität Darmstadt) Production chains: An application from mechanical engineering
11.20 – 11.45	Eva Zampachova (Brno University of Technology) Solution of selected engineering problem modeled by PDE constrained stochastic program
11.45 - 12.10	Yu Yu (University of Edinburgh) Stochastic ship fleet routing with inventory limits
12.10 – 12.35	Natalia Issaeva (University of Edinburgh) Stochastic programming for a problem of incorporation of wind energy to the electricity generation system
12.35 – 13.45	Lunch
13.45 – 14.45	Plenary talk: Alexander McNeil (Heriot-Watt University) Financial risk and capital allocation
14.45 – 15.15	Coffee/Tea
	Contributed talks session – Finance and Algorithm
15.15 – 15.40	Xi Yang (University of Edinburgh) Portfolio selection models with stochastic dominance constraints solved by OOPS
15.40 – 16.05	Alex Weissensteiner (University of Innsbruck) ALM models and the absence of arbitrage
16.05 – 16.30	Mohammad Reza Peyghami (KN Toosi University of Technology) An interior point approach for semidefinite optimization
16.30 – 16.55	Andreas Grothey (University of Edinburgh) Interior point warmstarts applied to stochastic programming
16.55 – 17.05	Concluding remarks

Presentations:

Presentation Details
Branda, Martin
Software for multistage stochastic linear programming problems
View Abstract Hide Abstract
The contribution deals with software for multistage stochastic linear programming problems. First, possible formulations of the multistage problems are reviewed. After that, basic languages (AML, SAMPL) and imput formats (SMPS, OSiL) are described. Then, available interfaces (SPiNE, SLP-IOR, COIN-SMI, AIMMS ... ) for solving stochastic programming problems are introduced and their main advantages and disadvantages are proposed. Unfortunately, one of the best software SETSTOCH was not available for us. Finally, special purpose solvers based on Benders decomposition are reviewed.
Chan, Kian Ping
An Iterative Primal-Dual Aggregation Algorithm for Multi-stage Stochastic Quadratic Programs
View Abstract Hide Abstract
We aim to solve the multi-stage stochastic quadratic programs with general uncertainties where randomness may occur anywhere in the objective function, right-hand side or constraint matrix. An alternative formulation is built to guarantee strict feasibility. The upper and lower bounds are derived from its constraint and decision aggregated counterparts. These bounds can be interpreted as the sum of expected infeasibility from primal and dual constraints. This principle is consistent with optimality condition in Linear Programming which states that an optimal solution is achieved only when both primal and dual feasibility are present. In our successive refinement algorithm, we solve the aggregated primal and dual problems and evaluate how close our aggregated problems to the original problem. The gap between those bounds is used as a termination criterion and can be sharpened by refining the partitions in the subsequent iterations. The scenario tree refinement is guided by the infeasibility contributed by each node. We will also discuss the convergence of the algorithm under the general framework of epi-convergence and present the numerical results.
Colombo, Marco
OOPS: A structure-exploiting parallel solver
View Abstract Hide Abstract
We describe the object-oriented parallel interior point solver OOPS, which is designed to exploit the block structure inherent in many types of problem, such as stochastic programming problems. Structure-exploitation allows to solve much larger problems that what can be achieved by general purpose solvers; also, it provides an ideal framework to be exploited with parallelism. In this talk we will present the advantages of exploiting structure in the solution method, and the implementation within OOPS.
Consigli, Giorgio
SP-based dynamic optimization of a corporate portfolio subject to credit risk
View Abstract Hide Abstract
We consider a dynamic credit portfolio optimization problem based on a universe of corporate bonds traded in the Eurobond market and describe the methodological steps linking the mathe-matical formulation of the problem, the adoption of a financial stochastic model to represent its underlying uncertainty and the discretization steps leading to the problem stochastic program (SP) representation and solution. The paper will focus on the critical steps of problem formula-tion and scenario generation and present preliminary results on optimal dynamic strategies under alternative assumptions on the financial variables stochastic dynamics. The adopted methodology integrates a Monte Carlo risk management internal based modelling approach (widely adopted in the industry due to regulatory reasons) with the SP event tree approximation to emphasize the potentials of an SP-based control strategy directly interfaced with the risk management tools developed by the financial industry. The described development is based on a set of Matlab 7.0 modules integrated with the model generator and the set of solvers provided by GAMS 25.2. The adopted interfaces and implementations steps will be analysed in the presentation.
Corchero, Cristina
Stochastic optimal day-ahead bid with physical future contracts
View Abstract Hide Abstract
The reorganization of electricity industry in Spain has finished a new step with the start-up of the Derivatives Market. Nowadays, all electricity transactions in Spain and Portugal are managed jointly through the MIBEL. This new framework requires important changes in the short-term optimization strategies of the Generation Companies. One main characteristic of MIBEL's Derivative Market is the existence of physical futures contracts; they imply the obligation to settle physically the energy. The market regulation establishes the mechanism for including those physical futures in the Day-Ahead bidding. Thus, the participation in the Derivatives Market changes the incomes function and it could imply changes in the optimal planning. The goal of this work is the optimization of the coordination between the physical futures contracts and the Day-Ahead bidding following this regulation. We propose a stochastic quadratic mixed-integer programming model which maximizes the expected profits taking into account futures contracts settlement. The model gives the simultaneous optimization for the Day-Ahead Market bidding strategy and power planning production for the thermal units of a price-taker Generation Company. The uncertainty of the day-ahead market price is included in the stochastic model through a scenario set.
Dempster, Michael
Solution techniques for large scale dynamic stochastic programming problems
View Abstract Hide Abstract
This talk will survey decomposition and related techniques for practical large scale dynamic stochastic programmes. Beginning with current implementations of nested Benders decomposition the talk will go on to discuss EVPI based importance sampling algorithms and their application in finance and logistics.
Dent, Chris
The security constrained optimal power flow -- not a stochastic optimisation problem
View Abstract Hide Abstract
Many optimal network design problems may be formulated with survivability constraints, to ensure that customers' needs can be met following one more more component outages. The minimum generation cost network flow problem in power systems is known as the `Optimal Power Flow' (OPF) problem. To protect against line overloads following a component outage, sets of power flow equations are added to the optimisation problem for the post-outage (`contingency') networks. Differently from many network survivability problems, this is an operational problem rather than a planning one. This security-constrained OPF (SCOPF) has the block structure of a stochastic optimisation problem, but the objective function depends only on the intact network variables; feasibility alone is required in the contingency networks. The full alternating current power flow equations are intrinsically nonlinear. Hence SCOPF problems, even on relatively small networks, can be extremely large nonlinear programs (possibly with 100,000 variables and constraints in a network with fewer than 100 nodes). Efficient solution methods for solving this very hard problem will therefore be discussed.
Drapkin, Dimitri
A cutting plane algorithm for optimization problems with stochastic order
View Abstract Hide Abstract
We consider optimization problems whose constraints involve stochastic order relations between decision-dependent random variables and fixed random benchmarks. The decision-dependent random variables are given by the total costs arising in two-stage stochastic programs with linear recourse. With finite probability spaces, we propose a cutting plane algorithm for this class of problems,enabling decomposition into single-scenario subproblems. We conclude with computational results indicating that our method is favourable over the application of general-purpose mixed-integer linear programming solvers.
Fabian, Csaba I.
An enhanced model for portfolio choice with SSD criteria: a constructive approach
View Abstract Hide Abstract
By Csaba I. Fabian, Gautam Mitra, Diana Roman, Victor Zviarovich Second-order Stochastic Dominance (SSD) is widely recognised as an important criterion for portfolio selection. The multi-objective model of Roman, Darby-Dowman, and Mitra (2006) successfully applies this criterion. The resulting problems were found to be computationally demanding, though. In the first part of this talk we propose a cutting-plane based method for the solution of problems resulting from this multi-objective model. We present algorithmic description, implementation details, and a computational study that demonstrates efficiency of the approach. In the second part, we formulate an enhanced version of the multi-objective model proposed by Roman, Darby-Dowman, and Mitra. The enhancement lies in a special scaling of the different objectives. The enhanced model can be formulated as risk minimisation with the use of a convex risk measure. We characterise this risk measure and the resulting optimisation problem. We outline a solution method and present a computational study demonstrating that the resulting portfolios have superior return distributions.
Giuliani, Saverio
A stochastic programming approach for strategic planning with activity based costing
View Abstract Hide Abstract
The development of a stochastic programming model for strategic planning based on Activity Based Costing (ABC) and the study of their connections is the main task of our research. The traditional model of ABC is widely described in literature, using the concepts of activities, cost drivers, activity cost rates and taking into account the differences with traditional cost accounting. A fundamental definition concerns the resources, whose concepts are replaced from the theory of the "Resource Based View of the Firm". The critical step is the use of ABC in developing forecasts of how costs will vary as functions of the cost drivers. In developing such functions, we distinguish between those for which the cost driver is a resource that may be scarce and therefore may constrain an optimal strategy, and those for which the cost driver is merely an accounting device and not a resource that will constrain the strategy. We focus our analysis on service companies which are ideal candidates for ABC, even more than manufacturing companies, because most of the costs are indirect. The chance constrained stochastic optimization problem is considered minimizing the objective function, which includes costs of activities, raw materials, accounting and sustaining resources with the probabilistic constraint for feasibility of resource planning under random demand. Results of application of the stochastic nonlinear programming approach to solve this problem are discussed on the basis of a small data set inspired by a real health care service context.
Gotzes, Uwe
Increasing convex order constraints induced by mixed integer linear recourse
View Abstract Hide Abstract
We propose a new class of stochastic integer programs whose special features are increasing convex order constraints induced by mixed-integer linear recourse. We establish closedness of the constraint set mapping with the underlying probability measure as parameter. In the case of finite probability spaces, the models are shown to be equivalent to large mixed-integer linear programs. We propose a decomposition algorithm for the latter and discuss computational results.
Grothey, Andreas
Interior point warmstarts applied to stochastic programming
View Abstract Hide Abstract
We describe a method of generating a crash-start point for interior point methods in the context of stochastic programming. We construct a small-scale version of the problem corresponding to a reduced scenario tree and use its solution to generate an advanced starting point for the complete problem. The reduced tree is constructed by scenario aggregation. Interior point methods in general struggle to take advantage of such information. We derive conditions on the reduced tree that guarantee a successful interior point warmstart. We present numerical results on a range of test problems which show remarkable advantages of this approach.
Iaquinta, Gaetano
A forward method for scenario generation with linear and nonlinear stochastic programs
View Abstract Hide Abstract
The formulation of dynamic stochastic programs for a general class of financial applications does generally require the definition of a risk-reward objective function and a financial stochastic model to represent the uncertainty underlying the decision problem. The solution of the optimal problem and the quality of the resulting strategy depend on the accurate description of a possibly extended set of financial variables. The canonical approach to describe financial dynamics considers a source of risk modeled by a continuous time random vector process, whose analytical specification need to be consistent with observed market dynamics and suitable for an accurate assessment of the current strategy risk exposure. The required scenario tree approximation associated with the problem mathematical programming formulation is on one hand expected to preserve the statistical properties of the underlying continuous process and on the other be relevant for the resulting optimal decision problem. Adopting a risk management philosophy, we present a recursive scenario generation approach leading to a minimal but sufficient representation of the stochastic program uncertainty underlying a dynamic financial planning problem. The associated decision problem will be characterized as a Markov decision problem whose dimensionality increases exponentially as the number of scenarios and stages of the optimization problem increase. The presented methodology, claimed to be problem-independent, leads to a remarkable problem size reduction relative to previous approaches opening the way to model refinement and extensions and avoiding the curse of dimensionality. (joint work with G Consigli, V Moriggia)
Issaeva, Natalia
Stochastic programming for a problem of incorporation of wind energy to the electricity generation system
View Abstract Hide Abstract
Let us consider a problem of electricity generation using a combination of different energy sources. Within the electricity market, suppliers undertake firm energy contracts with generators to meet their anticipated energy requirements, and submit the data to the National Grid one hour ahead of real time. The aim of our research is to determine how to minimise losses of a generating company by combining wind and conventional generation while applying instruments of stochastic programming. Wind speed is hard to forecast, especially at a time frame of ten minutes or half an hour and it adds up to the uncertainty of short-term electricity generation. One way to resolve this is to introduce a scenario tree with possible outcomes of the load curve. The aim is to balance supply and demand in the electricity market while minimising operational cost of generating companies. Although there were made several simplifying assumptions concerning a process of electricity generation, considered model retains some essential features of the problem and helps to study its dynamic nature.
Kaut, Michal
Solution methods for a multi-item newsvendor model with substitution
View Abstract Hide Abstract
We have a stochastic multi-item newsboy model with the following modification: if a customer who wants to buy one item arrives and the item is not available, there is some (specified) probability that he or she will be willing to buy a different item instead. It turns out that a straightforward LP implementation does not work, as it assumes that we can optimize customers' behaviour. This issue can be remedied by introducing extra binary variables, but such a model is solvable only for very small examples. Instead, we show that the problem can be solved using a derivative-free solver (in our case Ganso), using the second stage of the stochastic program as a simulator. This approach allows us to solve significantly larger models than the stochastic-MIP formulation. In addition, the solution can be expected to be approximately linear in the number of scenarios.
Kilianova, Sona
On solving some problems of dynamic stochastic programming by means of stochastic dynamic programming
View Abstract Hide Abstract
The motivation comes from a CVaRD=E-CVaR optimization problem applied to pension planning. Even if pension planning is a long-term investment (40 years), we approximate the 40 stages by only five, to keep the number of scenarios on a manageable level. The approximation changes the problem into a large-scale nonlinear program. In our recent paper, we suggested an iterative numerical scheme to solve it. In this talk, we propose to use methods of Stochastic Dynamic Programming instead of a scenario tree approach, to overcome the difficulties faced in the scenario tree approach.
Maggioni, Francesca
Stochastic second-order cone programming in mobile ad-hoc networks
View Abstract Hide Abstract
We study the semidefinite stochastic location-aided routing (SLAR) model described in Ariyawansa and Zhu [3] and Allevi et al [2], and formulate it as a two-stage stochastic second-order cone programming (SSOCP), see Alizadeh, D. Goldfarb [1] for second-order cone programming, where the main first-stage decision variables are the position of the destination node and its distance from the sender node. The random movements of the destination node are represented by ellipsoid scenarios randomly generated by a uniform distribution in a neighbourhood of the starting position of the destination node. The MOSEK solver (under GAMS environment) allows to solve problems with a large number of scenarios (say 4040) versus the ten scenarios of MINOS solver. Stability results for the optimal first-stage solutions and the optimal function value are obtained. Key Words. Stochastic Second-order cone programming, mobile ad-hoc networks. References [1] F. Alizadeh, D. Goldfarb (2003) Second-order cone programming, Math. Program., Ser. B, 95, 3-51. [2] E. Allevi, M. Bertocchi, F. Maggioni (2007) Stochastic Semidefinite Programs in mobile ad hoc networks, Rapporti di Ricerca, 289, Dipartimento Metodi Quantitivi, Università degli Studi di Brescia. [3] K.A. Ariyawansa, Y. Zhu (2006 ) Stochastic semidefinite programming a new paradigm for stochastic optimization, Online, Springer.
McNeil, Alexander
Financial risk and capital allocation
View Abstract Hide Abstract
I will give an overview of the problem of capital adequacy in financial institutions. I will explain how risk measures are used to define capital and describe the procedure that is used to allocate capital to business units and asset classes. I will mention some of the computational challenges involved.
Mitra, Gautam
Software tool for decision making under uncertainty: a combined paradigm of SP and simulation
View Abstract Hide Abstract
SAMPL is an extended version of AMPL, developed to facilitate the modelling of SP problems with recourse. SPInE (Stochastic Programming Integrated Environment) is the software system that interprets the language, assists in solving them and interprets the results. We report on the work in progress in the enhancement of SPInE. The following topics will be presented: a) Modelling of SP problems with SAMPL b) Use of SPInE as an ex-ante decision tool c) Rationale of language extensions to express Chance Constraints, Integrated Chance Constraints and Robust Optimization problems. d) Design and implementation insights of the new scenario generator library e) Design of the back testing, simulation and stress testing facilities
Nguyen Huu, Thong
A new stochastic algorithm for optimization problems
View Abstract Hide Abstract
This paper proposes a new stochastic algorithm for global optimization, Search Via Probability (SVP) algorithm. The SVP algorithm uses probabilities to control the process in search of optimal solutions. We calculate probabilities of the appearance of a better solution than the current one on each iteration, and on the performance of SVP algorithm we create good conditions for its appearance. We test this approach by implementing the SVP algorithm on some test continuous optimization problems, and we find very stable results.
Nowak, Nicole
Production chains: an application from mechanical engineering
View Abstract Hide Abstract
There are many uncertainties arising in production chains from mechanical engineering. We will present stochastic mixed integer models in particular for the process of drilling and for the production process chain as a whole. In process chains from a production context one encounters uncertainties that arise from various sources. Looking at the production process as a whole, one faces random sales forecasts, random prices, quality or even availability of resources. When considering the production process in finer granularity there arise uncertainties in every step of manufacturing. Taking as an example the process of drilling. While clamping the component, that is being worked on, uncertainties occur concerning deformation of that component. Further there may be randomness in the position of the drill. Even the speed of drilling may have an unpredictable impact on the final anatomy of the hole. Trying to handle these uncertainties we will present models for both perspectives concerning the detailedness, giving insight into problems we encountered and approaches for solution strategies.
Pedersen, Anne Marie Boiden
Integrated mortgage loan and pension planning
View Abstract Hide Abstract
Buying a house and pension savings are, for most household, the two largest financial transactions. Traditionally these two investment problems have been solved separately. In this paper we investigate the effects of consid- ering the mortgage and pension investments in an integrated fashion. As an application we consider the Danish mortgage and pension markets. We generate a number of cashflow scenarios for a number of mortgages and a stock index using a Vector Autoregressive (VAR) model. On top of that we develop a single period stochastic program and show that most household benefit from diversification effects when planning for their mortgage loan and pension savings.
Peyghami, Mohammad Reza
An interior point approach for semidefinite optimization
View Abstract Hide Abstract
Kernal functions play an important role in the interior point methods for solving optimization problems to define a new search direction. We consider primal-dual algorithms for solving Semidefinite Optimization (SDO) problems based on a new class of kernal functions defined on the positive definite cone. Using some appealing and mild conditions of the new class, we prove with simple analysis that the new class based large-update primal-dual interior point methods enjoy the so far best known complaxity result for SDO problems too.
Pflug, Georg
The mathematics of scenario generation
View Abstract Hide Abstract
It is a widespread opinion that scenario generation for stochastic optimization problems is more an art than a science. In this talk we develop the mathematics behind it, i.e. approximation theory, probability quantization and some probability theory. While optimal scenarios require the solution of nonlinear hard problems, some heuristic techniques exhibit good compromises between quality and effort. We discuss results on approximation quality for "optimal" and "nearly optimal" scenario methods as well as for quasi-MC and MC scenarios, the latter mostly for comparison.
Staino, Alessandro
A stochastic programming approach to the optimal issuance of government bonds
View Abstract Hide Abstract
Sovereign states issue fixed income securities to fund their expenses. The value of such portfolios strongly depends on the fluctuations of the term structure of interest rates. This is a typical example of planning under uncertainty, where decisions have to be drawn on the base of the key stochastic economic factors underneath the model. We propose a multistage stochastic programming model to select portfolios of bonds, where the aim of the decision maker is that of minimizing the cost of the decision process. At the same time, we bound the conditional Value-at-Risk, a measure of risk which accounts for the losses of the tail distribution. We build an efficient frontier to trade-off the optimal cost versus the conditional Value-at-Risk and analyse the results obtained.
Steinbach, Marc
Interior point algorithms for nonconvex multistage stochastic programs
View Abstract Hide Abstract
Multistage stochastic programming models are becoming vital in decision support for planning under uncertainty in areas like computational finance and energy. While convex multistage models are widely used, very well understood, and solvable by mature large scale optimization codes, comparably well developed solvers for nonconvex stochastic models do not yet exist. However, increasingly complex models arising, for instance, in combined power generation and trading, create a growing demand for such solvers. A promising approach consists in combining suitable interior point methods (handling nonconvexity) with a tree-sparse KKT solver for the expensive linear-indefinite Newton step subproblems (handling the excessive size of multistage models by exploiting their rich structure). We report on the coupling of the interior point code IPOPT with problem-specific tree-sparse KKT solvers. Computational results from several application areas will be presented.
Surowiec, Thomas
Analysis of M-stationary points and solutions to an SEPEC modeling oligopolistic competition
View Abstract Hide Abstract
A simplified model of oligopolistic competition in an electricity spot market is derived where network topology, transmission losses, and stochastic demand are taken into consideration. This takes the form of a so-called stochastic equilibrium problem with equilibrium constraints, SEPEC, whose specific structure allows one to show its well-definedness. Under the assumption that demand is discretely distributed, a reduction of the SEPEC to an, albeit larger, deterministic EPEC is possible, thus implying that results pertaining to our model with deterministic demand can be easily carried over to the case when demand is a (discretely-distributed) random vector. Specific solution types are considered leading to localizations of the considered EPEC. In doing so, structural properties of these EPECs are demonstrated, e.g., strong regularity of the equilibrium constraint. Finally, so-called M-stationarity conditions are used to make characterizing observations in regards to local solutions of certain localized (S)EPECs. The usage of these stationarity conditions has been historically rather difficult in that one needs to calculate the Mordukhovich co-derivative of the normal cone mapping. Using new developments from the non-smooth calculus of B. Mordukhovich, we are able to alleviate some of these problems.
Vigerske, Stefan
Decomposition of multistage stochastic programs with recombining scenario trees
View Abstract Hide Abstract
We consider multistage stochastic programs with recombining scenario trees. Discretization of a stochastic process by a recombining scenario tree allows to use a set of nodes which size is growing linearly with the number of timestages to represent a set of scenarios which size is growing exponentially. However, since due to the presence of timecoupling constraints the solution process does in general not follow the recombining nature of the stochastic process, a modification of the Nested Benders Decomposition algorithm has been developed that circumvents this problem and allows to take time coupling constraints into account. The algorithm can be interpreted as a dynamic recombination of scenarios which recombines the solution process during the approximation process whenever possible and this way avoids an exponentially growing number of subproblem evaluations. We present numerical results on power scheduling problems showing the efficiency of our method.
Weissensteiner, Alex
ALM models and the absence of arbitrage
View Abstract Hide Abstract
Following standard neoclassical finance theory, Klaassen (1997) shows that the construction of scenario trees for financial applications requires the absence of arbitrage. Without restrictions on the asset allocation any arbitrage opportunities present in the scenario tree will render the optimization problem unbounded. If such restrictions are present, e.g., in the form of short-sale constraints, the solution will be biased. Klaassen (1998) discusses a method to reduce the size of an arbitrage-free scenario tree that maintains the absence of arbitrage also in the ''downsized'' trees. An important ambiguity in applying this method is mentioned only very briefly on page 45 in Klaassen (1998): ''Although the adjustments to the risk-neutral probabilities after an aggregation follow naturally from the way in which the aggregations are performed, this is not the case for the subjective scenario probabilities... There are, however, several alternative ways to define aggregated subjective probabilities...''. We show that for optimization under the physical measure, i.e. after including the so-called market price of risk, the asset allocation may be biased, even if the “downsized” trees are arbitrage-free.
Woodsend, Kristian
A structure-conveying modelling language
View Abstract Hide Abstract
Large-scale optimization problems, in particular stochastic problems, are typically structured: it is possible to subdivide the constraint matrix into blocks. This is due to the underlying generation process, and known to the modeller. Yet traditional modelling languages often scramble the block structure of the problem. We present a new algebraic modelling language for mathematical programming, based on AMPL, that enables this structure to be captured and conveyed to the solver. Object-oriented extensions allow models to be constructed from sub-models. Interior point solvers that exploit block linear algebra and decomposition solvers can therefore directly exploit the structure of the problem. One major advantage of such structure-exploiting solvers is their ease of parallelisation. To keep this advantage, our modelling language is designed to allow sub-model processing to be run in parallel as well. Through this design our modelling language is scalable to model truly large problems.
Wozabal, David
A new method for Value-at-Risk constrained Optimization using the Difference of Convex Algorithm
View Abstract Hide Abstract
Due to regulatory reasons and its intuitive appeal the Value-at-Risk (V@R) is one of the most used risk measures in the industry. Despite of its popularity V@R suffers from serious drawbacks of theoretical and technical nature. The core of these problems is the non-concavity of the V@R functional, which renders optimization problems with a V@R objective or a V@R constraint computationally intractable. We address this problem by representing Value-at-Risk as a difference of convex (D.C.) function for the case where the distribution of the underlying random variable is discrete and has finitely many atoms. The difference of convex algorithm (DCA) - a local solution procedure for unconstrained DCA problems - is used to solve non-convex mean-risk problems with Value-at-Risk as a risk measure. The DCA comes in two flavors: complete (computationally hard) and simple (computationally tractable). A hybrid approach which combines the favorable runtime properties of the simple DCA with the stronger convergence results of the complete DCA is proposed. We demonstrate that the DCA often finds globally optimal solutions and consistently outperforms some of the widely used heuristics for the optimization of Value-at-Risk.
Yang, Xinan
Modelling and solving the stochastic top-percentile pricing problem by dynamic technique
View Abstract Hide Abstract
Multi-homing is a technology used by Internet Service Provider (ISP) to connect to the Internet via different network providers. This connectivity enhance the network reliability and quality of the ISP. However, using multi-networks may imply more cost on the ISP. To make full use of the underlying networks with minimum cost, an optimal routing strategy is required by ISPs. Of course, this study depends on the cost structure applied by network providers. In this paper, we assume that network providers charge the ISP according to the top-percentile pricing policy, which is relatively new but increasingly popular. In the top-percetile pricing scheme, the network provider measures the amount of data sent at fixed time intervals. We call this data as 'traffic', which possess a stochastic nature as it reveals with time. In this paper both stochastic and dynamic programming (DP) techniques are exploited in modelling the problem. However, we choose DP as the final model with the consideration of solution difficulty. The principal idea involves in the DP modelling is discretizing the continous region of traffic volume into several integer levels. State of DP is the usage of networks at every stage. Our decisions are making on the 'additional' volume of traffics -- the amount of traffic which cannot be shipped with no additional cost. Optimal routing strategy is achieved by solving the DP model backwards. Numerical tests on the practical instances shows that our DP model ideally approximates the real problem and gives good solutions on small scale examples. However, it is not applicable for the real world instances as it calls for too much computer memories to run and store the relevant information. Finally, we give some ideas about the Approximate Dynamic Programming algorithm, which is expected to solve huge size DP problems.
Yu, Yu
Stochastic ship fleet routing with inventory limits
View Abstract Hide Abstract
We describe a solution approach for a stochastic shiprouting 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. 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. Dantzig-Wolfe decomposition with column generation is used to solve the problem. We also give computational results and alternative models in the talk.
Zampachova, Eva
Solution of selected engineering problem modeled by PDE constrained stochastic program
View Abstract Hide Abstract
PDE constrained optimization problems with uncertainty arise in a wide range of technical applications. Therefore, PDE constrained stochastic programming problem is formulated as a theoretical model for selected engineering problem with a view to civil engineering. A computational scheme for solving this optimization problem is proposed using the two-stage scenario-based stochastic programming and suitable discretization method. Furthermore, appropriate algorithm and simulation techniques are used for efficient solution and for determining solution quality in this two-stage PDE constrained nonlinear stochastic program. Numerical and graphical solutions of the selected problem are presented.

Participants

Name	Institution
Attard, Natalie	University of Malta
Branda, Martin	Charles University in Prague
Bustreo, Roberto	Brunel University
Cartis, Coralia	University of Edinburgh
Chan, Kian Ping	Imperial College London
Colombo, Marco	University of Edinburgh
Consigli, Giorgio	University of Bergamo
Corchero, Cristina	Universitat Politecnica de Catalunya
Dempster, Michael	University of Cambridge
Dent, Chris	University of Edinburgh
Drapkin, Dimitri	University of Duisburg-Essen
Dunbar, Michelle	University of New South Wales
Ejikeme-Ugwu, Edith	Cranfield University
Fabian, Csaba I.	Kecskemet College and Eotvos Lorand University
Giuliani, Saverio	University of Foggia
Gondzio, Jacek	University of Edinburgh, School of Mathematics
Gotzes, Uwe	University of Duisburg-Essen
Grothey, Andreas	University of Edinburgh, School of Mathematics
Iaquinta, Gaetano	University of Bergamo
Issaeva, Natalia	University of Edinburgh
Kaut, Michal	Molde University College
Kilianova, Sona	Comenius University
Maggioni, Francesca	Università degli studi di Bergamo
Marjani Rasmussen, Kourosh	Technische Universität Darmstadt
McNeil, Alexander	Heriot-Watt University
Mitra, Gautam	Brunel University
Murphy, James	Cambridge Systems Associates / University of Cambridge
Myklebust, Jogeir	NTNU
Nguyen Huu, Thong	Ho Chi Minh City University of Pedagogy
Novotný, Jan	Brno University of Technology
Nowak, Nicole	Technische Universität Darmstadt
Pedersen, Anne Marie Boiden	University of Copenhagen
Peyghami, Mohammad Reza	K.N. Toosi University of Technology
Pflug, Georg	University of Vienna
Ross, Omri	University of Cambridge
Sheikh Hussin, Siti Aida	Brunel University
Staino, Alessandro	University of Palermo
Steinbach, Marc	Leibniz Universität Hannover
Surowiec, Thomas	Humboldt University Berlin
Vigerske, Stefan	Humboldt University Berlin
Weissensteiner, Alex	University of Innsbruck
Woodsend, Kristian	University of Edinburgh
Woodside Oriakhi, Maria	Brunel University
Wozabal, David	University of Vienna
Yang, Xi	University of Edinburgh
Yang, Xinan	University of Edinburgh
Yu, Yu	University of Edinburgh
Zampachova, Eva	Brno University of Technology
Zviarovich, Viktar	Brunel University