Stochastic Programming

A CVaR Scenario-based Framework: Minimizing Downside Risk of Multi-asset Class Portfolios

  • Kartik Krishnan Sivaramakrishnan
  • Robert Stamicar
    • Categories Applications - OR and Management Sciences, Finance and Economics, Stochastic Programming Tags , ,

    Multi-asset class (MAC) portfolios can be comprised of investments in equities, fixed-income, commodities, foreign-exchange, credit, derivatives, and alternatives such as real-estate and private equity. The return for such {\em non-linear} portfolios is {\em asymmetric} with significant tail risk. The traditional Markowitz Mean-Variance Optimization (MVO) framework, that linearizes all the assets in the portfolio and uses … Read more

    Distributionally Robust Optimization with Principal Component Analysis

  • Richard Chen
  • Habib Najm
  • Jean-Paul Watson
  • Jianqiang Cheng
  • Ali Pinar
  • Cosmin Safta
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    Distributionally robust optimization (DRO) is widely used, because it offers a way to overcome the conservativeness of robust optimization without requiring the specificity of stochastic optimization. On the computational side, many practical DRO instances can be equivalently (or approximately) formulated as semidefinite programming (SDP) problems via conic duality of the moment problem. However, despite being … Read more

    Exact Algorithms for the Chance-Constrained Vehicle Routing Problem

  • Thai Dinh
  • Ricardo Fukasawa
  • James R. Luedtke
    • Categories 0-1 Programming, Stochastic Programming, Transportation Tags , ,

    We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle’s capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for … Read more

    Stochastic Dual Dynamic Integer Programming

  • Shabbir Ahmed
  • Xu Andy Sun
  • Jikai Zou
    • Categories Dynamic Programming, Integer Programming, Stochastic Programming Tags , , ,

    Multistage stochastic integer programming (MSIP) combines the difficulty of uncertainty, dynamics, and non-convexity, and constitutes a class of extremely challenging problems. A common formulation for these problems is a dynamic programming formulation involving nested cost-to-go functions. In the linear setting, the cost-to-go functions are convex polyhedral, and decomposition algorithms, such as nested Benders’ decomposition and … Read more

    MIDAS: A Mixed Integer Dynamic Approximation Scheme

  • Joseph Frédéric Bonnans
  • Andrew B. Philpott
  • Faisal Wahid
    • Categories Dynamic Programming, Stochastic Programming Tags ,

    Mixed Integer Dynamic Approximation Scheme (MIDAS) is a new sampling-based algorithm for solving finite-horizon stochastic dynamic programs with monotonic Bellman functions. MIDAS approximates these value functions using step functions, leading to stage problems that are mixed integer programs. We provide a general description of MIDAS, and prove its almost-sure convergence to an epsilon-optimal policy when … Read more

    Scenario Tree Reduction Methods Through Changing Node Values

  • Zhiping Chen
  • Zhe Yan
    • Categories Stochastic Programming Tags , , ,

    To develop practical and efficient scenario tree reduction methods, we introduce a new methodology which allows for changing node values, and an easy-to-calculate distance function to measure the difference between two scenario trees. Based on minimizing the new distance, we first construct a primitive scenario tree reduction model which also minimizes the Wasserstein distance between … Read more

    A Polyhedral Study on Chance Constrained Program with Random Right-Hand Side

  • Kai Huang
  • Bo Zeng
  • Ming Zhao
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Stochastic Programming Tags , , , , ,

    The essential structure of the mixed–integer programming formulation for chance–constrained program (CCP) is the intersection of multiple mixing sets with a $0-1$ knapsack. To improve our computational capacity on CCP, an underlying substructure, the (single) mixing set with a $0-1$ knapsack, has received substantial attentions recently. In this study, we consider a CCP problem with … Read more

    A stochastic program with tractable time series and affine decision rules for the reservoir management problem

  • Erick Delage
  • Charles Gauvin
  • Michel Gendreau
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , , , , ,

    This paper proposes a multi-stage stochastic programming formulation for the reservoir management problem. Our problem specifically consists in minimizing the risk of floods over a fixed time horizon for a multi-dimensional hydro-electrical complex. We consider well-studied linear time series model and enhance the approach to consider heteroscedasticity. Using these stochastic processes under very general distributional … Read more

    Algorithms for stochastic optimization with expectation constraints

  • Guanghui Lan
  • Zhiqiang Zhou
    • Categories Bound-constrained Optimization, Convex and Nonsmooth Optimization, Stochastic Programming Tags , , , ,

    This paper considers the problem of minimizing an expectation function over a closed convex set, coupled with an expectation constraint on either decision variables or problem parameters. We first present a new stochastic approximation (SA) type algorithm, namely the cooperative SA (CSA), to handle problems with the expectation constraint on devision variables. We show that … Read more

    Stochastic geometric optimization with joint probabilistic constraints

  • Zhiping Chen
  • Abdel Lisser
  • Jia Liu
    • Categories Stochastic Programming Tags , , ,

    This paper discusses geometric programs with joint probabilistic constraints. When the stochastic parameters are normally distributed and independent of each other, we approximate the problem by using piecewise polynomial functions with non-negative coefficients, and transform the approximation problem into a convex geometric program. We prove that this approximation method provides a lower bound. Then, we … Read more