Stochastic Programming

On Multidimensonal Disjunctive Inequalities for Chance-Constrained Stochastic Problems with Finite Support

  • Diego Cattaruzza
  • Martine Labbé
  • Matteo Petris
  • Marius Roland
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    We consider mixed-integer linear chance-constrained problems for which the random vector that parameterizes the feasible region has finite support. Our key objective is to improve branch-and-bound or -cut approaches by introducing new types of valid inequalities that improve the dual bounds and, by this, the overall performance of such methods. We introduce so-called primal-dual as … Read more

    Multi-cut stochastic approximation methods for solving stochastic convex composite optimization

  • Jiaming Liang
  • Honghao Zhang
  • Renato D.C. Monteiro
    • Categories Convex Optimization, Stochastic Programming Tags , , ,

    This paper considers the stochastic convex composite optimization problem and presents multi-cut stochastic approximation (SA) methods for solving it, whose models in expectation overestimate its objective function. The multi-cut model obtained by taking the maximum of a finite number of linearizations of the stochastic objective function provides a biased estimate of the objective function, with … Read more

    Convergence of Mean-Field Langevin Stochastic Descent-Ascent for Distributional Minimax Optimization

  • Rui Gao
    • Categories Stochastic Programming

    We study convergence properties of the discrete-time Mean-Field Langevin Stochastic Descent-Ascent (MFL-SDA) algorithm for solving distributional minimax optimization. These problems arise in various applications, such as zero-sum games, generative adversarial networks and distributionally robust learning. Despite the significance of MFL-SDA in these contexts, the discrete-time convergence rate remains underexplored. To address this gap, we establish … Read more

    An Adaptive Stochastic Dual Progressive Hedging Algorithm for Stochastic Programming

  • Di Zhang
  • Yihang Zhang
  • Suvrajeet Sen
    • Categories Stochastic Approaches, Stochastic Programming Tags , , ,

    The Progressive Hedging (PH) algorithm is one of the cornerstones in large-scale stochastic programming. However, its traditional development requires that all scenario subproblems are solved per iteration, and a probability distribution with finitely many outcomes. This paper introduces a stochastic dual PH algorithm (SDPH) to overcome these challenges. We introduce an adaptive sampling process and … Read more

    A Decision Diagram Approach for the Parallel Machine Scheduling Problem with Chance Constraints

  • Nicolás Casassus
  • Margarita P Castro
  • Gustavo Angulo
    • Categories Branch and Cut Algorithms, Scheduling, Stochastic Programming Tags , ,

    The Chance-Constrained Parallel Machine Scheduling Problem (CC-PMSP) assigns jobs with uncertain processing times to machines, ensuring that each machine’s availability constraints are met with a certain probability. We present a decomposition approach where the master problem assigns jobs to machines, and the subproblems schedule the jobs on each machine while verifying the solution’s feasibility under … Read more

    A Survey on the Applications of Stochastic Dual Dynamic Programming and its Variants

  • Bonn Kleiford Seranilla
  • Nils Löhndorf
    • Categories Dynamic Programming, Integer Programming, Stochastic Programming Tags , , ,

    Stochastic Dual Dynamic Programming (SDDP) is widely recognized as the predominant methodology for solving large-scale multistage stochastic linear programming (MSLP) problems. This paper aims to contribute to the extant literature by conducting a comprehensive survey of the literature on SDDP within the realm of practical applications. We systematically identify and analyze the various domains where … Read more

    IPAS: An Adaptive Sample Size Method for Weighted Finite Sum Problems with Linear Equality Constraints

  • Nataša Krejić
  • Nataša Krklec Jerinkić
  • Sanja Rapajić
  • Luka Rutešić
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    Optimization problems with the objective function in the form of weighted sum and linear equality constraints are considered. Given that the number of local cost functions can be large as well as the number of constraints, a stochastic optimization method is proposed. The method belongs to the class of variable sample size first order methods, … Read more

    An interactive optimization framework for incorporating a broader range of human feedback into stochastic multi-objective mixed integer linear programs

  • Damsara Jayarathne
  • Jennifer Pazour
  • John E. Mitchell
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization, Stochastic Programming Tags , , , ,

    Interactive optimization leverages the strengths of optimization frameworks alongside the expertise of human users. Prior research in this area tends to either ask human users for the same type of information, or when varying information is requested, users must manually modify the optimization model directly. These limitations restrict the incorporation of wider human knowledge into … Read more

    Globally Converging Algorithm for Multistage Stochastic Mixed-Integer Programs via Enhanced Lagrangian Cuts

  • Hanbin Yang
  • Haoxiang Yang
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    This paper proposes a globally converging cutting-plane algorithm for solving multistage stochastic mixed-integer programs with general mixed-integer state variables. We demonstrate the generation process of Lagrangian cuts and show that Lagrangian cuts capture the convex envelope of value functions on a restricted region. To approximate nonconvex value functions to exactness, we propose to iteratively add … Read more

    Climate-Resilient Nodal Power System Expansion Planning for a Realistic California Test Case

  • Amelia Musselman
  • Tomas Valencia Zuluaga
  • Elizabeth Glista
  • Minda Monteagudo
  • J Michael Grappone
  • Jean-Paul Watson
    • Categories (Mixed) Integer Linear Programming, Energy, Stochastic Programming Tags , , , ,

    Climate change is increasingly impacting power system operations, not only through more frequent extreme weather events but also through shifts in routine weather patterns. Factors such as increased temperatures, droughts, changing wind patterns, and solar irradiance shifts can impact both power system production and transmission and electric load. The current power system was not designed … Read more