Stochastic Programming

Data-Driven Approximation of Contextual Chance-Constrained Stochastic Programs

  • Hamed Rahimian
  • Bernardo K. Pagnoncelli
    • Categories Stochastic Programming Tags , , ,

    Uncertainty in classical stochastic programming models is often described solely by independent random parameters, ignoring their dependence on multidimensional features. We describe a novel contextual chance-constrained programming formulation that incorporates features, and argue that solutions that do not take them into account may not be implementable. Our formulation cannot be solved exactly in most cases, … Read more

    Compromise Policy for Multi-stage Stochastic Linear Programming: Variance and Bias Reduction

  • Jiajun Xu
  • Suvrajeet Sen
    • Categories Applications - Science and Engineering, Dynamic Programming, Stochastic Programming Tags , , , , ,

    This paper focuses on algorithms for multi-stage stochastic linear programming (MSLP). We propose an ensemble method named the “compromise policy”, which not only reduces the variance of the function approximation but also reduces the bias of the estimated optimal value. It provides a tight lower bound estimate with a confidence interval. By exploiting parallel computing, … Read more

    The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

  • Ricardo Fukasawa
    • Categories Combinatorial Optimization, Integer Programming, Stochastic Programming Tags , ,

    The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains … Read more

    A Machine Learning Approach to Solving Large Bilevel and Stochastic Programs: Application to Cycling Network Design

  • Bo Lin
    • Categories Integer Programming, Stochastic Programming, Transportation Tags , , , ,

    We present a novel machine learning-based approach to solving bilevel programs that involve a large number of independent followers, which as a special case include two-stage stochastic programming. We propose an optimization model that explicitly considers a sampled subset of followers and exploits a machine learning model to estimate the objective values of unsampled followers. … Read more

    Optimizing Vaccine Distribution in Developing Countries under Natural Disaster Risk

  • Bonn Kleiford Seranilla
  • Nils Löhndorf
    • Categories (Mixed) Integer Linear Programming, Dynamic Programming, Stochastic Programming Tags , , ,

    For many developing countries, COVID-19 vaccination roll-out programs are not only slow but vaccination centers are also exposed to the risk of natural disaster, like flooding, which may slow down vaccination progress even further. Policy-makers in developing countries therefore seek to implement strategies that hedge against distribution risk in order for vaccination campaigns to run … Read more

    A Simplified Convergence Theory for Byzantine Resilient Stochastic Gradient Descent

  • Lindon Roberts
    • Categories Optimization in Data Science, Stochastic Programming Tags , ,

    In distributed learning, a central server trains a model according to updates provided by nodes holding local data samples. In the presence of one or more malicious servers sending incorrect information (a Byzantine adversary), standard algorithms for model training such as stochastic gradient descent (SGD) fail to converge. In this paper, we present a simplified … Read more

    Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method for Empirical Risk Minimization

  • Zikai Xiong
  • Robert M. Freund
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Stochastic Programming Tags , , , , ,

    The Frank-Wolfe method has become increasingly useful in statistical and machine learning applications, due to the structure-inducing properties of the iterates, and especially in settings where linear minimization over the feasible set is more computationally efficient than projection. In the setting of Empirical Risk Minimization — one of the fundamental optimization problems in statistical and … Read more

    Software for data-based stochastic programming using bootstrap estimation

  • Xiaotie Chen
  • David L. Woodruff
    • Categories Other Topics, Stochastic Programming

    In this paper we describe software for stochastic programming that uses only sampled data to obtain both a consistent sample-average solution and a consistent estimate of confidence intervals for the optimality gap using bootstrap and bagging. The underlying distribution whence the samples come is not required. ArticleDownload View PDF

    Stochastic nested primal-dual method for nonconvex constrained composition optimization

  • Ling-Zi Jin
  • Xiao Wang
    • Categories Constrained Nonlinear Optimization, Data Science Algorithms, Stochastic Programming Tags , , , , , , ,

    In this paper we study the nonconvex constrained composition optimization, in which the objective contains a composition of two expected-value functions whose accurate information is normally expensive to calculate. We propose a STochastic nEsted Primal-dual (STEP) method for such problems. In each iteration, with an auxiliary variable introduced to track the inner layer function values … Read more

    Statistical performance of subgradient step-size update rules in Lagrangian relaxations of chance-constrained optimization models

  • Charlotte Ritter
  • Bismark Singh
    • Categories Stochastic Programming Tags , , , ,

    Published in Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-031-47859-8_26 Lagrangian relaxation schemes, coupled with a subgradient procedure, are frequently employed to solve chance-constrained optimization models. The subgradient procedure typically relies on a step-size update rule. Although there is extensive research on the properties of these step-size update rules, there is little consensus on which rules are … Read more