Stochastic Programming

A scenario decomposition algorithm for strategic time window assignment vehicle routing problems

  • Chrysanthos E. Gounaris
  • Anirudh Subramanyam
  • Akang Wang
    • Categories Stochastic Programming, Transportation Tags , , , , ,

    We study the strategic decision-making problem of assigning time windows to customers in the context of vehicle routing applications that are affected by operational uncertainty. This problem, known as the Time Window Assignment Vehicle Routing Problem, can be viewed as a two-stage stochastic optimization problem, where time window assignments constitute first-stage decisions, vehicle routes adhering … Read more

    Inexact Stochastic Mirror Descent for two-stage nonlinear stochastic programs

  • Vincent Guigues
    • Categories Stochastic Programming

    We introduce an inexact variant of Stochastic Mirror Descent (SMD), called Inexact Stochastic Mirror Descent (ISMD), to solve nonlinear two-stage stochastic programs where the second stage problem has linear and nonlinear coupling constraints and a nonlinear objective function which depends on both first and second stage decisions. Given a candidate first stage solution and a … Read more

    Scenario-based cuts for structured two-stage stochastic and distributionally robust p-order conic mixed integer programs

  • Manish Bansal
  • Yingqiu Zhang
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Stochastic Programming Tags , , , ,

    In this paper, we derive (partial) convex hull for deterministic multi-constraint polyhedral conic mixed integer sets with multiple integer variables using conic mixed integer rounding (CMIR) cut-generation procedure of Atamtürk and Narayanan (Math Prog 122:1–20, 2008), thereby extending their result for a simple polyhedral conic mixed integer set with single constraint and one integer variable. … Read more

    Coalescing Data and Decision Sciences for Analytics

  • Yunxiao Deng
  • Junyi Liu
  • Suvrajeet Sen
    • Categories Stochastic Programming Tags , ,

    The dream of analytics is to work from common, clean, and consistent data sources in a manner that all of its facets (descriptive, predictive, and prescriptive) are sup- ported via a coherent vision of data and decision sciences. To the extent that data and decisions sciences work within logically/mathematically consistent frameworks, and that these paradigms … Read more

    Shortfall Risk Models When Information of Loss Function Is Incomplete

  • Erick Delage
  • Shaoyan Guo
  • Huifu Xu
    • Categories Linear Programming, Robust Optimization, Stochastic Programming Tags , , , , , ,

    Utility-based shortfall risk measure (SR) has received increasing attentions over the past few years for its potential to quantify more effectively the risk of large losses than conditional value at risk. In this paper we consider the case that the true loss function is unavailable either because it is difficult to be identified or the … Read more

    Quantitative Stability of Two-stage Stochastic Linear Programs with Full Random Recourse

  • Zhiping Chen
  • Jie Jiang
    • Categories Stochastic Programming

    In this paper, we use the parametric programming technique and pseudo metrics to study the quantitative stability of the two-stage stochastic linear programming problem with full random recourse. Under the simultaneous perturbation of the cost vector, coefficient matrix and right-hand side vector, we first establish the locally Lipschitz continuity of the optimal value function and … Read more

    Representation of distributionally robust chance-constraints

  • Jean-Bernard Lasserre
  • Tillmann Weisser
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming, Stochastic Programming

    Given $X\subset R^n$, $\varepsilon \in (0,1)$, a parametrized family of probability distributions $(\mu_{a})_{a\in A}$ on $\Omega\subset R^p$, we consider the feasible set $X^*_\varepsilon\subset X$ associated with the {\em distributionally robust} chance-constraint \[X^*_\varepsilon\,=\,\{x\in X:\:{\rm Prob}_\mu[f(x,\omega)\,>\,0]> 1-\varepsilon,\,\forall\mu\in\mathscr{M}_a\},\] where $\mathscr{M}_a$ is the set of all possibles mixtures of distributions $\mu_a$, $a\in A$. For instance and typically, the family … Read more

    Dynamic Risked Equilibrium

  • Michael C. Ferris
  • Andrew B. Philpott
    • Categories Game Theory, Stochastic Programming Tags , , ,

    We revisit the correspondence of competitive partial equilibrium with a social optimum in markets where risk-averse agents solve multistage stochastic optimization problems formulated in scenario trees. The agents trade a commodity that is produced from an uncertain supply of resources which can be stored. The agents can also trade risk using Arrow-Debreu securities. In this … Read more

    Exact converging bounds for Stochastic Dual Dynamic Programming via Fenchel duality

  • Pierre Carpentier
  • Arnaud Lenoir
  • Jean-Philippe Chancelier
  • Vincent Leclère
  • François Pacaud
    • Categories Dynamic Programming, Stochastic Programming

    The Stochastic Dual Dynamic Programming (SDDP) algorithm has become one of the main tools to address convex multistage stochastic optimal control problem. Recently a large amount of work has been devoted to improve the convergence speed of the algorithm through cut-selection and regularization, or to extend the field of applications to non-linear, integer or risk-averse … Read more

    An algorithm for solving infinite horizon Markov dynamic programmes

  • Regan Baucke
    • Categories Convex Optimization, Dynamic Programming, Stochastic Programming Tags , , , ,

    We consider a general class of infinite horizon dynamic programmes where state and control sets are convex and compact subsets of Euclidean spaces and (convex) costs are discounted geometrically. The aim of this work is to provide a convergence result for these problems under as few restrictions as possible. Under certain assumptions on the cost … Read more