Scenario cluster Lagrangean decomposition for risk averse in multistage stochastic optimization

In this work we present a decomposition approach as a mixture of dualization and Lagrangean Relaxation for obtaining strong lower bounds on large-sized multistage stochastic mixed 0–1 programs with a time stochastic dominance risk averse measure. The objective function to minimize is a composite function of the expected cost along the time horizon over the scenarios and the penalization of the expected cost excess on reaching the set of thresholds under consideration, subject to a bound on the expected cost excess for each threshold and a bound on the failure probability of reaching it. The main differences with some other risk averse strategies are presented. The problem is represented by a mixture of the splitting representation up to a given stage, so-called break stage, and the compact representation for the other stages along the time horizon. The dualization of the nonanticipativity constraints for the node-based and risk averse variables up to the break stage and the Lagrangean Relaxation of the cross node constraints of the risk averse strategy result in a model that can be decomposed into a set of independent scenario cluster submodels. Three Lagrangean multipliers updating schemes as the Subgradient method, the Lagrangean Progressive Hedging algorithm and the Dynamic Constrained Cutting Plane are computationally compared. We have observed in the randomly generated instances we have experimented with that the smaller the number of clusters, the stronger the lower bound provided for the original problem (even, frequently, it is the solution value) obtained with an affordable computing time.     

Step decision rules for multistage stochastic programming: A heuristic approach

Stochastic programming with step decision rules (SPSDR) aims to produce efficient solutions to multistage stochastic optimization problems. SPSDR, like plain multistage Stochastic Programming (SP), operates on a Monte Carlo “computing sample” of moderate size that approximates the stochastic process. Unlike SP, SPSDR does not strive to build a balanced event tree out of that sample. Rather, it defines a solution as a special type of decision rule, with the property that the decisions at each stage are piecewise constant functions on the sample of scenarios. Those pieces define a partition of the set of scenarios at each stage t, but the partition at t+1 need not be refinement of the partition at t. However, the rule is constructed so that the non-anticipativity condition is met, a necessary condition to make the rules operational. To validate the method we show how to extend a non-anticipatory decision rule to arbitrary scenarios within a very large validation sample of scenarios. We apply three methods, SPSDR, SP and Robust Optimization, to the same 12-stage problem in supply chain management, and compare them relatively to different objectives and performance criteria. It appears that SPSDR performs better than SP in that it produces a more accurate estimate (prediction) of the value achieved by its solution on the validation sample, and also that the achieved value is better.     

Valuation of electricity swing options by multistage stochastic programming

Electricity swing options are Bermudan-style path-dependent derivatives on electrical energy. We consider an electricity market driven by several exogenous risk factors and formulate the pricing problem for a class of swing option contracts with energy and power limits as well as ramping constraints. Efficient numerical solution of the arising multistage stochastic program requires aggregation of decision stages, discretization of the probability space, and reparameterization of the decision space. We report on numerical results and discuss analytically tractable limiting cases.     

An effective heuristic for multistage linear programming with a stochastic right-hand side

The multistage Stochastic Linear Programming (SLP) problem may become numerically intractable for huge instances, in which case one can solve an approximation for example the well known multistage Expected Value (EV) problem. We introduce a new approximation to the SLP problem that we call the multistage Event Linear Programming (ELP) problem. To obtain this approximation the SLP constraints are aggregated by means of the conditional expectation operator. Based on this new problem we derive the ELP heuristic that produces a lower and an upper bound for the SLP problem. We have assessed the validity of the ELP heuristic by solving large scale instances of the network revenue management problem, where the new approach has clearly outperformed the EV approach. One limitation of this paper is that it only considers randomness on the right-hand side, which is assumed to be discrete and stagewise independent.     

Fuzzy differential inclusions as substitutes for stochastic differential equations in population biology

The familiar procedure of adding white noise to deterministic systems of equations may not be appropriate or even possible in some modelling problems arising in the biological sciences. Although some mathematical handle on indeterminant factors (i.e. “noise”) may be necessary, sometimes the probabilistic requirements involved cannot be rigorously verified for the data set in hand. As an alternative, we discuss here the modelling utility of fuzzy differential inclusions associated with given systems of nonlinear ODE's. We give concrete examples and give account of the conservative stochastic mechanics of E. Nelson applied to growth of a dimorphic clone, and its fuzzy differential inclusion analogue.     

Efficient constraint reduction in multistage stochastic programming problems with endogenous uncertainty

Multistage stochastic programming with endogenous uncertainty is a new topic in which the timing of uncertainty realization is decision-dependent. In this case, the number of nonanticipativity constraints (NACs) increases very quickly with the number of scenarios, making the problem computationally intractable. Fortunately, a large number of NACs are typically redundant and their elimination leads to a considerable reduction in the problem size. Identifying redundant NACs has been addressed in the literature only in the special case where the scenario set is equal to the Cartesian product of all possible outcomes for endogenous parameters; however, this is a scarce condition in practice. In this paper, we consider the general case where the scenario set is an arbitrary set; and two approaches, able to identify all redundant NACs, are proposed. The first approach is by mixed integer programming formulation and the second one is an exact polynomial time algorithm. Proving the fact that the proposed algorithm is able to make the uppermost reduction in the number of NACs is another novelty of this paper. Computational results evaluate the efficiency of the proposed approaches.     

Existence results for impulsive neutral stochastic functional integro-differential inclusions with nonlocal initial conditions

In this paper, we prove the existence of mild solutions for a class of impulsive neutral stochastic functional integro-differential inclusions with nonlocal initial conditions and resolvent operators. Sufficient conditions for the existence are derived with the help of the fixed point theorem for multi-valued operators due to Dhage and the fractional power of operators. An example is provided to illustrate the theory.     

An algorithmic framework for solving large-scale multistage stochastic mixed 0-1 problems with nonsymmetric scenario trees

In this paper we present a parallelizable Branch-and-Fix Coordination algorithm for solving medium and large-scale multistage mixed 0-1 optimization problems under uncertainty. The uncertainty is represented via a nonsymmetric scenario tree. An information structuring for scenario cluster partitioning of nonsymmetric scenario trees is also presented, given the general model formulation of a multistage stochastic mixed 0-1 problem. The basic idea consists of explicitly rewriting the nonanticipativity constraints (NAC) of the 0-1 and continuous variables in the stages with common information. As a result an assignment of the constraint matrix blocks into independent scenario cluster submodels is performed by a so-called cluster splitting-compact representation. This partitioning allows to generate a new information structure to express the NAC which link the related clusters, such that the explicit NAC linking the submodels together is performed by a splitting variable representation. The new algorithm has been implemented in a C++ experimental code. Some computational experience is reported on a test of randomly generated instances as well as a large-scale real-life problem by using CPLEX as a solver of the auxiliary submodels within the open source engine COIN-OR.     

Analytic models for multistage interconnection networks

Central to all parallel architectures is a switching network which facilitates the communication between a machine's components necessary to support their cooperation. Multistage interconnection networks (MINs) are classified and analytic models are described for both packet-switched and circuit-switched MINs with asynchronous transmission mode. Under strong enough assumptions, packet switching can be modeled by standard queuing methods, hence providing a standard against which to assess approximate models. We describe one such approximate model with much weaker assumptions which is more widely applicable and can be implemented more efficiently. To model circuit switching requires a different approach because of the presence of passive resources, namely multiple links through the MIN which must be held before a message can be transmitted and throughout its transmission. An approximate analysis based upon the recursive structure of a particular MIN topology which yields accurate predictions when compared with simulation is described.     

基于遗传算法分阶段快速寻优

该算法充分利用算法前期搜索的有用信息训练出淘汰模式和优秀模式。交叉产生的新群体与上一代群体竞争后进入下一代。有淘汰模式指导变异提高变异能力。根据优秀模式缩短解空间,提高搜索精度和放大适应度值比例进行快速收敛寻优。仿真试验表明,收敛速度和最优解精度都有大幅度提高。     

On BFC-MSMIP strategies for scenario cluster partitioning, and twin node family branching selection and bounding for multistage stochastic mixed integer programming

In the branch-and-fix coordination (BFC-MSMIP) algorithm for solving large-scale multistage stochastic mixed integer programming problems, we find it crucial to decide the stages where the nonanticipativity constraints are explicitly considered in the model. This information is materialized when the full model is broken down into a scenario cluster partition with smaller subproblems. In this paper we present a scheme for obtaining strong bounds and branching strategies for the Twin Node Families to increase the efficiency of the procedure BFC-MSMIP, based on the information provided by the nonanticipativity constraints that are explicitly considered in the problem. Some computational experience is reported to support the efficiency of the new scheme.     

On reduction of the multistage problem of stochastic programming with quantile criterion to the problem of mixed integer linear programming

Consideration was given to the a priori formulation of the multistage problem of stochastic programming with a quantile criterion which is reducible to the two-stage problem. Equivalence of the two-stage problems with the quantile criterion in the a priori and a posteriori formulations was proved for the general case. The a posteriori formulation of the two-stage problem was in turn reduced to the equivalent problem of mixed integer linear programming. An example was considered.     

Moment Kernels for Regular Distributions

Many machine learning problems in natural language processing, transaction-log analysis, or computational biology, require the analysis of variable-length sequences, or, more generally, distributions of variable-length sequences.Kernel methods introduced for fixed-size vectors have proven very successful in a variety of machine learning tasks. We recently introduced a new and general kernel framework, rational kernels, to extend these methods to the analysis of variable-length sequences or more generally distributions given by weighted automata. These kernels are efficient to compute and have been successfully used in applications such as spoken-dialog classification with Support Vector Machines.However, the rational kernels previously introduced in these applications do not fully encompass distributions over alternate sequences. They are based only on the counts of co-occurring subsequences averaged over the alternate paths without taking into accounts information about the higher-order moments of the distributions of these counts.In this paper, we introduce a new family of rational kernels, moment kernels, that precisely exploits this additional information. These kernels are distribution kernels based on moments of counts of strings. We describe efficient algorithms to compute moment kernels and apply them to several difficult spoken-dialog classification tasks. Our experiments show that using the second moment of the counts of n-gram sequences consistently improves the classification accuracy in these tasks.Editors: Dan Roth and Pascale Fung     

Neural approximations for multistage optimal control of nonlinearstochastic systems

Two main approximations are used to solve a nonlinear-quadratic-Gaussian (LQG) optimal control problem: the control law is assigned a given structure in which a finite number of parameters have to be determined to minimize the cost function (the chosen structure is that of a multilayer feedforward neural network); and the control law is given a “limited memory”. The errors resulting front both assumptions are discussed. Simulation results show that the proposed method may constitute a simple and effective tool for solving, to a sufficient degree of accuracy, optimal control problems traditionally regarded as difficult ones     

A novel approach for multistage inference fuzzy control

This paper presents a methodology to the design of a multistage inference fuzzy controller in which the consequence in an inference stage is passed to the next stage as fact, and so forth. A new general method which is based on a performance index of the control system is used to generate fuzzy rule bases for the multistage inference. This proposed method can reduce the design cycle time. In order to reduce the computation time, a method for precomputing the match-degrees of fuzzy values is adopted. Thus, the number of operations that must be carried out at execution time can be significantly reduced. The new method has been applied to two applications, a two-trailer-and-truck system and a three-trailer-and-truck system. The simulation studies showed that the proposed method is feasible.