stochastic programming

Barrier Methods Based on Jordan-Hilbert Algebras for Stochastic Optimization in Spin Factors

  • Baha Alzalg
    • Categories Infinite Dimensional Optimization, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

    We present decomposition logarithmic-barrier interior-point methods based on unital Jordan-Hilbert algebras for infinite-dimensional stochastic second-order cone programming problems in spin factors. The results show that the iteration complexity of the proposed algorithms is independent on the choice of Hilbert spaces from which the underlying spin factors are formed, and so it coincides with the best … Read more

    Robust Generalization despite Distribution Shift via Minimum Discriminating Information

  • Andreas Krause
  • Daniel Kuhn
  • Tobias Sutter
    • Categories Robust Optimization Tags , , , , ,

    Training models that perform well under distribution shifts is a central challenge in machine learning. In this paper, we introduce a modeling framework where, in addition to training data, we have partial structural knowledge of the shifted test distribution. We employ the principle of minimum discriminating information to embed the available prior knowledge, and use … Read more

    Batch Learning in Stochastic Dual Dynamic Programming

  • Daniel Ávila
  • Nils Löhndorf
  • Anthony Papavasiliou
    • Categories Dynamic Programming, Stochastic Programming Tags , , , ,

    We consider the stochastic dual dynamic programming (SDDP) algorithm, which is a widely employed algorithm applied to multistage stochastic programming, and propose a variant using batch learning, a technique used with success in the reinforcement learning framework. We cast SDDP as a type of Q-learning algorithm and describe its application in both risk neutral and … Read more

    Efficient presolving methods for the influence maximization problem in social networks

  • Sheng-Jie Chen
  • Wei-Kun Chen
  • Yu-Hong Dai
  • Jian-Hua Yuan
  • Hou-Shan Zhang
    • Categories (Mixed) Integer Linear Programming Tags , , , , ,

    We consider the influence maximization problem (IMP) which asks for identifying a limited number of key individuals to spread influence in a social network such that the expected number of influenced individuals is maximized. The stochastic maximal covering location problem (SMCLP) formulation is a mixed integer programming formulation that effectively approximates the IMP by the … Read more

    A converging Benders’ decomposition algorithm for two-stage mixed-integer recourse models

  • Ward Romeijnders
  • Niels van der Laan
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    We propose a new solution method for two-stage mixed-integer recourse models. In contrast to existing approaches, we can handle general mixed-integer variables in both stages, and thus, e.g., do not require that the first-stage variables are binary. Our solution method is a Benders’ decomposition, in which we iteratively construct tighter approximations of the expected second-stage … Read more

    Moreau envelope of supremum functions with applications to infinite and stochastic programming

  • Pedro Pérez-Aros
  • Emilio Vilches
    • Categories Convex Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    In this paper, we investigate the Moreau envelope of the supremum of a family of convex, proper, and lower semicontinuous functions. Under mild assumptions, we prove that the Moreau envelope of a supremum is the supremum of Moreau envelopes, which allows us to approximate possibly nonsmooth supremum functions by smooth functions that are also the … Read more

    JuDGE.jl: a Julia package for optimizing capacity expansion

  • Regan Baucke
  • Anthony Downward
  • Andrew B. Philpott
    • Categories Applications - OR and Management Sciences, Optimization Software and Modeling Systems, Stochastic Programming Tags , , , ,

    We present JuDGE.jl, an open-source Julia package for solving multistage stochastic capacity expansion problems using Dantzig-Wolfe decomposition. Models for JuDGE.jl are built using JuMP, the algebraic modelling language in Julia, and solved by repeatedly applying mixed-integer programming. We illustrate JuDGE.jl by formulating and solving a toy knapsack problem, and demonstrate the performance of JuDGE.jl on … Read more

    A Parallel Hub-and-Spoke System for Large-Scale Scenario-Based Optimization Under Uncertainty

  • Bernard Knueven
  • Christopher Muir
  • Jean-Paul Watson
  • David T. Mildebrath
  • John D. Siirola
  • David L. Woodruff
    • Categories Stochastic Programming Tags , , ,

    Efficient solution of stochastic programming problems generally requires the use of parallel computing resources. Here, we describe the open source package mpi-sppy, in which efficient and scalable parallelization is a central feature. We describe the overall architecture and provide computational examples and results showing scalability to the largest instances that we know of for the … Read more

    Modeling Multi-stage Decision Making under Incomplete and Uncertain Information

  • Viktor Bindewald
  • Fabian Dunke
  • Stefan Nickel
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , , , ,

    We propose a new universal framework for multi-stage decision making under limited information availability. It is developed as part of a larger research project which aims at providing analytical methods to compare and evaluate different models and algorithms for multi-stage decision making. In our setting, we have an open time horizon and limited information about … Read more

    Equivalent second-order cone programs for distributionally robust zero-sum games

  • Ayush Agarwal
  • Abdel Lisser
  • Vikas Vikram Singh
  • Navnit Yadav
    • Categories Game Theory, Stochastic Programming Tags , , , ,

    We consider a two player zero-sum game with stochastic linear constraints. The probability distributions of the vectors associated with the constraints are partially known. The available information with respect to the distribution is based mainly on the two first moments. In this vein, we formulate the stochastic linear constraints as distributionally robust chance constraints. We … Read more