Stochastic Programming

Valid Inequalities and Restrictions for Stochastic Programming Problems with First Order Stochastic Dominance Constraints

  • Nilay Noyan
  • Andrzej Ruszczyński
    • Categories Stochastic Programming Tags , , ,

    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 (SSD) constraints can be solved by linear programming (LP). However, problems involving first order stochastic dominance … Read more

    Totally Unimodular Stochastic Programs

  • Shabbir Ahmed
  • Andrew J. Schaefer
  • Nan Kong
    • Categories Stochastic Programming

    We consider totally unimodular stochastic programs, that is, stochastic programs whose extensive-form constraint matrix is totally unimodular. We generalize the notion of total unimodularity to apply to sets of matrics and provide properties of such sets. Using this notion, we give several sufficient conditions for specific classes of problems. When solving such problems using the … Read more

    On Rates of Convergence for Stochastic Optimization Problems Under Non-I.I.D. Sampling

  • Tito Homem-de-Mello
    • Categories Optimization of Simulated Systems, Stochastic Programming Tags , , , , , ,

    In this paper we discuss the issue of solving stochastic optimization problems by means of sample average approximations. Our focus is on rates of convergence of estimators of optimal solutions and optimal values with respect to the sample size. This is a well-studied problem in case the samples are independent and identically distributed (i.e., when … Read more

    A robust approach to the chance-constrained knapsack problem

  • Olivier Klopfenstein
  • Dritan Nace
    • Categories 0-1 Programming, Robust Optimization, Stochastic Programming

    Chance-constrained programming is a relevant model for many concrete problems. However, it is known to be very hard to tackle directly. In this paper, the chance-constrained knapsack problem (CKP) is addressed. Relying on the recent advances in robust optimization, a tractable combinatorial algorithm is proposed to solve CKP. It always provides feasible solutions for CKP. … Read more

    A Tractable Approximation of Stochastic Programming via Robust Optimization

  • Xin Chen
  • Peng Sun
  • Jiawei Zhang
  • Melvyn Sim
    • Categories Robust Optimization, Second-Order Cone Programming, Stochastic Programming Tags , , ,

    Stochastic programming, despite its immense modeling capabilities, is well known to be computationally excruciating. In this paper, we introduce a unified framework of approximating multiperiod stochastic programming from the perspective of robust optimization. Specifically, we propose a framework that integrates multistage modeling with safeguarding constraints. The framework is computationally tractable in the form of second … Read more

    A Robust Optimization Framework for Analyzing Distribution Systems with Transshipment

  • Mabel C. Chou
  • Melvyn Sim
  • Rick So
    • Categories Robust Optimization, Stochastic Programming, Supply Chain Management Tags , , ,

    This paper studies a distribution system consisting of multiple retail locations with transshipment operations among the retailers. Due to the difficulty in computing the optimal solution imposed by the transshipment operations and in estimating shortage cost from a practical perspective, we propose a robust optimization framework for analyzing the impact of transshipment operations on such … Read more

    Smooth minimization of two-stage stochastic linear programs

  • Shabbir Ahmed
    • Categories Nonsmooth Optimization, Stochastic Programming Tags ,

    This note presents an application of the smooth optimization technique of Nesterov for solving two-stage stochastic linear programs. It is shown that the original O(1/e) bound of Nesterov on the number of main iterations required to obtain an e-optimal solution is retained. Citation Technical Report, School of Industrial & Systems Engineering, Georgia Institute of Technology, … Read more

    Reformulation and Sampling to Solve a Stochastic Network Interdiction Problem

  • Udom Janjarassuk
  • Jeff Linderoth
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , ,

    The Network Interdiction Problem involves interrupting an adversary’s ability to maximize flow through a capacitated network by destroying portions of the network. A budget constraint limits the amount of the network that can be destroyed. In this paper, we study a stochastic version of the network interdiction problem in which the successful destruction of an … Read more

    Stochastic Programming Approach to Optimization under Uncertainty

  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , , , , ,

    In this paper we discuss computational complexity and risk averse approaches to two and multistage stochastic programming problems. We argue that two stage (say linear) stochastic programming problems can be solved with a reasonable accuracy by Monte Carlo sampling techniques while there are indications that complexity of multistage programs grows fast with increase of the … Read more

    Coherent Risk Measures in Inventory Problems

  • Shabbir Ahmed
  • Ulas Cakmak
  • Alexander Shapiro
    • Categories Production and Logistics, Stochastic Programming Tags , , , ,

    We analyze an extension of the classical multi-period, single-item, linear cost inventory problem where the objective function is a coherent risk measure. Properties of coherent risk measures allow us to offer a unifying treatment of risk averse and min-max type formulations. For the single period newsvendor problem, we show that the structure of the optimal … Read more