Chair: Martin Branda, Charles University in Prague, Czech Republic
Optimal scenario set partitioning for multistage stochastic programming with the progressive hedging algorithm
Michel Gendreau (firstname.lastname@example.org), Pierre-Luc Carpentier (email@example.com), Fabian Bastin (firstname.lastname@example.org)
We propose a new approach to reduce the total running time of the progressive hedging algorithm (PHA) for solving multistage stochastic programs defined on a scenario tree. Instead of using the conventional scenario decomposition scheme, we apply a multi-scenario decomposition scheme and partition the scenario set in order to minimize the number of non-anticipativity constraints (NACs) on which an augmented Lagrangian relaxation must be applied. Our partitioning method is a heuristic algorithm that takes into account the complex branching structure of general multistage scenario trees. Minimizing the number of relaxed NACs (RNACs) enhances the PHA’s convergence rate by decreasing the variability of subproblem solutions at duplicated tree nodes. This is due to the fact that minimizing the RNACs reduces the anticipativity level of subproblems by increasing the branching level of subtrees. This makes RNACs easier to satisfy. Our partitioning method also reduces the total time per iteration in two different ways. Firstly, it decreases the number of linear and quadratic penalty terms that need to be included in subproblem objective function. Secondly, it reduces the total number of duplicated decision variables and constraints at tree nodes that are associated with RNACs. The proposed method is tested on a hydroelectricity generation scheduling problem covering a 52-week planning horizon. Computational results show that the method is extremely effective.
Keywords: Stochastic programming, Progressive hedging, Scenario trees
P-BFC, Parallelized Branch-and-Fix Coordination algorithm for solving large-scale multistage mixed 0-1 problems
Gloria Pérez (email@example.com), Unai Aldasoro (firstname.lastname@example.org), María Merino (email@example.com), Laureano F. Escudero (firstname.lastname@example.org)
A Parallelized Branch-and-Fix Coordination (P-BFC) algorithm is presented for solving medium and large scale multistage mixed 0-1 optimization problems under exogenous uncertainty. The parallelization is performed by combined two paradigms, namely inner and outer parallelization. The first one parallelizes the independent scenario cluster MIP submodels at a given step of the sequential algorithm; the effect of the processor allocation strategies is analyzed. The second one corresponds to simultaneous executions of the algorithm under different initial strategies and information exchange. By creating so named paths of sets of 0-1 variables (i.e. combinations of fixed 0-1 values of the variables), B&B trees can be generated by assigning paths to processors and then being run in parallel; periodically incumbent solution and branching situation are gathered by every processor. Computational results are reported for a broad set of at random generated instances by considering the inner and outer strategies alone as well as a combined inner-outer parallelization strategy, which provides optimal solutions whose computing time is up to one order of magnitude smaller than the time for the sequential version of the BFC algorithm in the difficult instances in our testbed. Message Passing Interface (MPI) has been used for processor communication in the computing cluster ARINA provided by the SGI/IZO-SGIker at the UPV/EHU
Keywords: Multistage Stochastic Optimization, Parallel Computing, Message Passing Interface (MPI)
Stochastic programming approaches to pricing in non-life insurance
Martin Branda (email@example.com)
We focus on rating of non-life insurance contracts. We employ multiplicative models with basic premium levels and specific surcharge coefficients for various levels of selected risk/rating factors. We use generalized linear models (GLM) to describe the probability distribution of total losses for a contract during one year. We show that the traditional frequency--severity approaches based only on GLM with logarithmic link function can lead to estimates which do not fulfil business requirements. For example, a maximal surcharge and monotonicity of coefficient can be desirable. Moreover, our approach can handle total losses, which are based on arbitrary loss distributions, possibly decomposed into several classes, e.g. small and large or property and bodily injury. Various costs and loadings can be also incorporated into the tariff rates. We propose optimization problems for rate estimation which enable hedging against expected losses and taking into account a prescribed loss ratio and other business requirements. Moreover, we introduce a stochastic programming extension with reliability type constraints which incorporate riskiness of each rate cell. In the numerical study, we apply the approaches to Motor Third Party Liability (MTPL) policies and discuss the influence of the number of contracts.
Keywords: stochastic programming, pricing, non-life insurance