Stochastic Programming

A Bilevel Optimization Approach for a Class of Combinatorial Problems with Disruptions and Probing

  • Leonardo Lozano
  • Juan Borrero
    • Categories Applications - OR and Management Sciences, Network Optimization, Stochastic Programming Tags , , ,

    \(\) We consider linear combinatorial optimization problems under uncertain disruptions that increase the cost coefficients of the objective function. A decision-maker, or planner, can invest resources to probe the components (i.e., the coefficients) in order to learn their disruption status. In the proposed probing optimization problem, the planner, knowing just the disruptions’ probabilities, selects which … Read more

    Inexact Newton methods with matrix approximation by sampling for nonlinear least-squares and systems

  • Stefania Bellavia
  • Greta Malaspina
  • Benedetta Morini
    • Categories Nonlinear Optimization, Nonlinear Systems and Least-Squares, Stochastic Programming

    We develop and analyze stochastic inexact Gauss-Newton methods for nonlinear least-squares problems and inexact Newton methods for nonlinear systems of equations. Random models are formed using suitable sampling strategies for the matrices involved in the deterministic models. The analysis of the expected number of iterations needed in the worst case to achieve a desired level … Read more

    The Terminator: An Integration of Inner and Outer Approximations for Solving Regular and Distributionally Robust Chance Constrained Programs via Variable Fixing

  • Nan Jiang
  • Weijun Xie
    • Categories Stochastic Programming Tags , ,

    We present a novel approach aimed at enhancing the efficacy of solving both regular and distributionally robust chance constrained programs using an empirical reference distribution. In general, these programs can be reformulated as mixed-integer programs (MIPs) by introducing binary variables for each scenario, indicating whether a scenario should be satisfied. While existing methods have predominantly … Read more

    Gradient-based rho Parameter for Progressive Hedging

  • Ulysse Naepels
  • David L. Woodruff
    • Categories Stochastic Programming Tags , , ,

    \(\) Watson and Woodruff  (2011) developed a heuristic for computing variable-dependent values of the penalty parameter $\rho$ from the model itself. We combine this heuristic with a gradient-based method, in order to obtain a new method for calculating $\rho$ values. We then introduce a method for iteratively computing variable-dependent $\rho$ values. This method is based … Read more

    Distributions and Bootstrap for Data-based Stochastic Programming

  • Xiaotie Chen
  • David L. Woodruff
    • Categories Stochastic Programming Tags , , ,

    In the context of optimization under uncertainty, we consider various combinations of distribution estimation and resampling (bootstrap and bagging) for obtaining samples used to acquire a solution and for computing a confidence interval for an optimality gap. This paper makes three experimental contributions to on-going research in data driven stochastic programming: a) most of the … Read more

    Almost-sure convergence of iterates and multipliers in stochastic sequential quadratic optimization

  • Frank E. Curtis
  • Xin Jiang
  • Qi Wang
    • Categories Constrained Nonlinear Optimization, Data Science Applications, Stochastic Programming Tags , , ,

    Stochastic sequential quadratic optimization (SQP) methods for solving continuous optimization problems with nonlinear equality constraints have attracted attention recently, such as for solving large-scale data-fitting problems subject to nonconvex constraints. However, for a recently proposed subclass of such methods that is built on the popular stochastic-gradient methodology from the unconstrained setting, convergence guarantees have been … Read more

    Enhancing explainability of stochastic programming solutions via scenario and recourse reduction

  • Tushar Rathi
  • Rishabh Gupta
  • Jose M. Pinto
  • Qi Zhang
    • Categories Stochastic Programming Tags , , ,

    Stochastic programming (SP) is a well-studied framework for modeling optimization problems under uncertainty. However, despite the significant advancements in solving large SP models, they are not widely used in industrial practice, often because SP solutions are difficult to understand and hence not trusted by the user. Unlike deterministic optimization models, SP models generally involve recourse … Read more

    Stability of Markovian Stochastic Programming

  • David Wozabal
    • Categories Stochastic Programming Tags , , ,

    Multi-stage stochastic programming is notoriously hard, since solution methods suffer from the curse of dimensionality. Recently, stochastic dual dynamic programming has shown promising results for Markovian problems with many stages and a moderately large state space. In order to numerically solve these problems simple discrete representations of Markov processes are required but a convincing theoretical … Read more

    A Multicut Approach to Compute Upper Bounds for Risk-Averse SDDP

  • Joaquim Dias Garcia
  • Mario Pereira
    • Categories Dynamic Programming, Energy, Stochastic Programming Tags , , , ,

    Stochastic Dual Dynamic Programming (SDDP) is a widely used and fundamental algorithm for solving multistage stochastic optimization problems. Although SDDP has been frequently applied to solve risk-averse models with the Conditional Value-at-Risk (CVaR), it is known that the estimation of upper bounds is a methodological challenge, and many methods are computationally intensive. In practice, this … Read more

    Duality of upper bounds in stochastic dynamic programming

  • Bernardo Freitas Paulo da Costa
  • Vincent Leclère
    • Categories Convex Optimization, Dynamic Programming, Stochastic Programming Tags , , , ,

    For multistage stochastic programming problems with stagewise independent uncertainty, dynamic programming algorithms calculate polyhedral approximations for the value functions at each stage.  The SDDP algorithm provides piecewise linear lower bounds, in the spirit of the L-shaped algorithm, and corresponding upper bounds took a longer time to appear.  One strategy uses the primal dynamic programming recursion … Read more