A gaussian upper bound for gaussian multi-stage stochastic linear programs

This paper deals with two-stage and multi-stage stochastic programs in which the right-hand sides of the constraints are Gaussian random variables. Such problems are of interest since the use of Gaussian estimators of random variables is widespread. We introduce algorithms to find upper bounds on the optimal value of two-stage and multi-stage stochastic (minimization) programs with Gaussian right-hand sides. The upper bounds are obtained by solving deterministic mathematical programming problems with dimensions that do not depend on the sample space size. The algorithm for the two-stage problem involves the solution of a deterministic linear program and a simple semidefinite program. The algorithm for the multi-stage problem invovles the solution of a quadratically constrained convex programming problem.     

A bicriteria solid transportation problem with fixed charge under stochastic environment

In this paper, a bicriteria solid transportation problem with stochastic parameters is investigated. Three mathematical models are constructed for the problem, including expected value goal programming model, chance-constrained goal programming model and dependent-chance goal programming model. A hybrid algorithm is also designed based on the random simulation algorithm and tabu search algorithm to solve the models. At last, some numerical experiments are presented to show the performance of models and algorithm.     

Optimal Security Liquidation Algorithms

This paper develops trading strategies for liquidation of a financial security, which maximize the expected return. The problem is formulated as a stochastic programming problem that utilizes the scenario representation of possible returns. Two cases are considered, a case with no constraint on risk and a case when the risk of losses associated with trading strategy is constrained by Conditional Value-at-Risk (CVaR) measure. In the first case, two algorithms are proposed; one is based on linear programming techniques, and the other uses dynamic programming to solve the formulated stochastic program. The third proposed algorithm is obtained by adding the risk constraints to the linear program. The algorithms provide path-dependent strategies, i.e., the fraction of security sold depends upon price sample-path of the security up to the current moment. The performance of the considered approaches is tested using a set of historical sample-paths of prices.     

二阶段随机规划问题基于随机模拟的遗传算法

利用遗传算法不过多依赖目标函数性质．适应于全局搜索的特点．提出了求解二阶段随机规划的基于随机模拟的遗传算法，算法采用随机模拟技术利用样本均值近似代替期望值，使计算得以简化，计算实例表明该算法是有效和可行的。     

Valid inequalities and restrictions for stochastic programming problems with first order stochastic dominance constraints

Stochastic dominance relations are well studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance constraints can be solved by linear programming. However, problems involving first order stochastic dominance constraints are potentially hard due to the non-convexity of the associated feasible regions. In this paper we consider a mixed 0–1 linear programming formulation of a discrete first order constrained optimization model and present a relaxation based on second order constraints. We derive some valid inequalities and restrictions by employing the probabilistic structure of the problem. We also generate cuts that are valid inequalities for the disjunctive relaxations arising from the underlying combinatorial structure of the problem by applying the lift-and-project procedure. We describe three heuristic algorithms to construct feasible solutions, based on conditional second order constraints, variable fixing, and conditional value at risk. Finally, we present numerical results for several instances of a real world portfolio optimization problem. This research was supported by the NSF awards DMS-0603728 and DMI-0354678.     

二层随机规划基于随机模拟的遗传算法

本提出了二层随机规划模型，给出了求解二层随机规划问题的基于随机模拟的遗传算法。实际算例表明算法是可行的、有效的。     

Probability maximization models for portfolio selection under ambiguity

This paper considers several probability maximization models for multi-scenario portfolio selection problems in the case that future returns in possible scenarios are multi-dimensional random variables. In order to consider occurrence probabilities and decision makers’ predictions with respect to all scenarios, a portfolio selection problem setting a weight with flexibility to each scenario is proposed. Furthermore, by introducing aspiration levels to occurrence probabilities or future target profit and maximizing the minimum aspiration level, a robust portfolio selection problem is considered. Since these problems are formulated as stochastic programming problems due to the inclusion of random variables, they are transformed into deterministic equivalent problems introducing chance constraints based on the stochastic programming approach. Then, using a relation between the variance and absolute deviation of random variables, our proposed models are transformed into linear programming problems and efficient solution methods are developed to obtain the global optimal solution. Furthermore, a numerical example of a portfolio selection problem is provided to compare our proposed models with the basic model.     

L-shaped decomposition of two-stage stochastic programs with integer recourse

We consider two-stage stochastic programming problems with integer recourse. The L-shaped method of stochastic linear programming is generalized to these problems by using generalized Benders decomposition. Nonlinear feasibility and optimality cuts are determined via general duality theory and can be generated when the second stage problem is solved by standard techniques. Finite convergence of the method is established when Gomory’s fractional cutting plane algorithm or a branch-and-bound algorithm is applied.     

Rollout Algorithms for Stochastic Scheduling Problems

Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.     

The traveling purchaser problem with stochastic prices: Exact and approximate algorithms

The paper formulates an extension of the traveling purchaser problem where multiple types of commodities are sold at spatially distributed locations with stochastic prices (each following a known probability distribution). A purchaser’s goal is to find the optimal routing and purchasing strategies that minimize the expected total travel and purchasing costs needed to purchase one unit of each commodity. The purchaser reveals the actual commodity price at a seller upon arrival, and then either purchases the commodity at the offered price, or rejects the price and visits a next seller. In this paper, we propose an exact solution algorithm based on dynamic programming, an iterative approximate algorithm that yields bounds for the minimum total expected cost, and a greedy heuristic for fast solutions to large-scale applications. We analyze the characteristics of the problem and test the computational performance of the proposed algorithms. The numerical results show that the approximate and heuristic algorithms yield near-optimum strategies and very good estimates of the minimum total cost.     

Conditional Value-at-Risk in Stochastic Programs with Mixed-Integer Recourse

In classical two-stage stochastic programming the expected value of the total costs is minimized. Recently, mean-risk models - studied in mathematical finance for several decades - have attracted attention in stochastic programming. We consider Conditional Value-at-Risk as risk measure in the framework of two-stage stochastic integer programming. The paper addresses structure, stability, and algorithms for this class of models. In particular, we study continuity properties of the objective function, both with respect to the first-stage decisions and the integrating probability measure. Further, we present an explicit mixed-integer linear programming formulation of the problem when the probability distribution is discrete and finite. Finally, a solution algorithm based on Lagrangean relaxation of nonanticipativity is proposed. Received: April, 2004     

An SQP algorithm for extended linear-quadratic problems in stochastic programming

Extended Linear-Quadratic Programming (ELQP) problems were introduced by Rockafellar and Wets for various models in stochastic programming and multistage optimization. Several numerical methods with linear convergence rates have been developed for solving fully quadratic ELQP problems, where the primal and dual coefficient matrices are positive definite. We present a two-stage sequential quadratic programming (SQP) method for solving ELQP problems arising in stochastic programming. The first stage algorithm realizes global convergence and the second stage algorithm realizes superlinear local convergence under a condition calledB-regularity.B-regularity is milder than the fully quadratic condition; the primal coefficient matrix need not be positive definite. Numerical tests are given to demonstrate the efficiency of the algorithm. Solution properties of the ELQP problem underB-regularity are also discussed.Supported by the Australian Research Council.     

Stochastic scheduling to minimize expected maximum lateness

This paper is concerned with the problems in scheduling a set of jobs associated with random due dates on a single machine so as to minimize the expected maximum lateness in stochastic environment. This is a difficult problem and few efforts have been reported on its solution in the literature. In this paper, we first derive a deterministic equivalent to the expected maximum lateness and then propose a dynamic programming algorithm to obtain the optimal solutions. The procedures to compute optimal solutions are initially developed in the case of deterministic processing times, and then extended to stochastic processing times following arbitrary probability distributions. Moreover, several heuristic rules are suggested to compute near-optimal solutions, which are shown to be highly efficient and accurate by computer-based experiments.     

Exact Algorithms for Large-Scale Unconstrained Two and Three Staged Cutting Problems

In this paper we propose two exact algorithms for solving both two-staged and three staged unconstrained (un)weighted cutting problems. The two-staged problem is solved by applying a dynamic programming procedure originally developed by Gilmore and Gomory [Gilmore and Gomory, Operations Research, vol. 13, pp. 94–119, 1965]. The three-staged problem is solved by using a top-down approach combined with a dynamic programming procedure. The performance of the exact algorithms are evaluated on some problem instances of the literature and other hard randomly-generated problem instances (a total of 53 problem instances). A parallel implementation is an important feature of the algorithm used for solving the three-staged version.     

Stochastic linear knapsack programming problem and its application to a portfolio selection problem

In this paper a probability maximization model of a stochastic linear knapsack problem is considered where the random variables consist of several groups with mutually correlated ones. We propose a solution algorithm to the equivalent nonlinear fractional programming problem with a simple ranking method. This approach will be effectively applied to one of the portfolio selection problems.     

Interactive multiobjective fuzzy random linear programming: Maximization of possibility and probability

This paper considers multiobjective linear programming problems with fuzzy random variables coefficients. A new decision making model is proposed to maximize both possibility and probability, which is based on possibilistic programming and stochastic programming. An interactive algorithm is constructed to obtain a satisficing solution satisfying at least weak Pareto optimality.     

Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

We show that a particular pivoting algorithm, which we call the lexicographic Lemke algorithm, takes an expected number of steps that is bounded by a quadratic inn, when applied to a random linear complementarity problem of dimensionn. We present two probabilistic models, both requiring some nondegeneracy and sign-invariance properties. The second distribution is concerned with linear complementarity problems that arise from linear programming. In this case we give bounds that are quadratic in the smaller of the two dimensions of the linear programming problem, and independent of the larger. Similar results have been obtained by Adler and Megiddo.Research partially funded by a fellowship from the Alfred Sloan Foundation and by NSF Grant ECS82-15361.     

Cross decomposition applied to the stochastic transportation problem

In this paper we give a solution method for the stochastic transportation problem based on Cross Decomposition developed by Van Roy (1980). Solution methods to the derived sub and master problems are discussed and computational results are given for a number of large scale test problems. We also compare the efficiency of the method with other methods suggested for the stochastic transportation problem: The Frank-Wolfe algorithm and separable programming.     

Two-stage stochastic linear programs with incomplete information on uncertainty

Two-stage stochastic linear programming is a classical model in operations research. The usual approach to this model requires detailed information on distribution of the random variables involved. In this paper, we only assume the availability of the first and second moments information of the random variables. By using duality of semi-infinite programming and adopting a linear decision rule, we show that a deterministic equivalence of the two-stage problem can be reformulated as a second-order cone optimization problem. Preliminary numerical experiments are presented to demonstrate the computational advantage of this approach.