News Release

Decomposition algorithms for solving multistage stochastic mixed 0-1 problems

Peer-Reviewed Publication

Elhuyar Fundazioa

This press release is also available in Spanish.

This thesis presents an algorithmic approach for solving multistage stochastic mixed 0-1 models. The problem is modelled as a splitting variable representation of the Deterministic Equivalent Model for the stochastic model, where the 0-1 variables and the continuous variables appear at any stage. The approach uses the Twin Node Family (TNF) concept within the algorithmic framework so-called Branch-and-Fix Coordination for satisfying the nonanticipativity constraints of the 0-1 variables, jointly with a Benders Decomposition scheme for solving lineal models at each TNF integer set and fractional TNF integer set, for satisfying the nonanticipativity constraints of the continuous variables.

Two illustrative cases are presented. The first one consists on structuring a portfolio of Mortgage-Backed Securities under uncertainty in the interest rate path along a given time horizon, where the goal is the minimization of the expected absolute mismatching of the durations of the MBS portfolio and the liabilities over the scenarios. The second one is a model for optimizing a mean-risk function of the terminal wealth and the probability of reaching a given terminal wealth target over the scenarios for a fixed income asset portfolio restructuring with uncertainty in the interest rate path and the liabilities along a given time horizon. The uncertainty is represented by a scenario tree and it is dealt with by a two-stage and multistage stochastic mixed 0-1 model with complete recourse, respectively.

Some computational experience is reported to compare the quality of the solution obtained by our approach and the optimization of the average scenario problem. A comparison is also performed with solving the DEM by a plain use of a state-of-the-art optimization engine. The algorithmic approach has been implemented in a FORTRAN 90 and Visual C++.NET experimental codes. It also uses the optimization engine IBM OSL v2.0 and 3.0 for solving the lineal and mixed 0-1 models.

Several expected values of using the expected value solution for multistage problems with full recourse are defined, where the uncertainty lies in the objective function, as well as in the right-hand-side coe_cients and the constraint matrices.

Finally, we introduce mean and mean-risk functions. We establish three types of objective functions: the maximization of the expected terminal wealth, the one which includes the probability of reaching a given terminal wealth target over the Scenarios and the so-called Value-at-Risk (VaR). Some computational experience is reported to compare the quality of the solution for the Reaching Probability obtained by our approach, the maximization of the expected terminal wealth alone and the maximization of the terminal wealth for the average scenario problem.

###


Disclaimer: AAAS and EurekAlert! are not responsible for the accuracy of news releases posted to EurekAlert! by contributing institutions or for the use of any information through the EurekAlert system.