Stochastic Programming – Page 32

A Shared Mobility Based Framework for Evacuation Planning and Operations under Forecast Uncertainty

Published: 2020/08/07, Updated: 2021/08/12

Network Optimization, Stochastic Programming, Transportation

To meet evacuation needs from carless populations who may require personalized assistance to evacuate safely, we propose a ridesharing-based evacuation program that recruits volunteer drivers before a disaster strikes, and then matches volunteers with evacuees who need assistance once demand is realized. We optimize resource planning and evacuation operations under uncertain spatiotemporal demand, and construct … Read more

An Improved Analysis of Stochastic Gradient Descent with Momentum

Published: 2020/08/04, Updated: 2020/08/17

Yuan Gao

Yanli Liu

Wotao Yin

Stochastic Programming

SGD with momentum (SGDM) has been widely applied in many machine learning tasks, and it is often applied with dynamic stepsizes and momentum weights tuned in a stagewise manner. Despite of its empirical advantage over SGD, the role of momentum is still unclear in general since previous analyses on SGDM either provide worse convergence bounds … Read more

Large Deviation Bounds for Markov Chain Sample Average Approximation via Weak Convergence

Published: 2020/08/04

Arnab Sur

Stochastic Programming consistency, donsker-varadhan entropy, epigraphical and uniform convergence, large deviation principle, markov chain sample average approximation

A common approach to solve stochastic optimization problems with expectations is to replace the expectations by its sample averages. Large sample asymptotic properties of this approximation are well studied when the sample is i.i.d. In many cases, however, i.i.d. samples are not readily available. On the contrary, one can generate a Harris recurrent Markov chain … Read more

Accuracy and fairness trade-offs in machine learning: A stochastic multi-objective approach

Published: 2020/08/03, Updated: 2020/09/03

Suyun Liu

Luis Nunes Vicente

Data-Mining, Multi-Criteria Optimization, Stochastic Programming disparate impact, equal opportunity, fairness, machine learning, multi-objective optimization, nonconvex optimization, pareto fronts, sensitive/protected attributes, stochastic approximation, supervised learning

In the application of machine learning to real life decision-making systems, e.g., credit scoring and criminal justice, the prediction outcomes might discriminate against people with sensitive attributes, leading to unfairness. The commonly used strategy in fair machine learning is to include fairness as a constraint or a penalization term in the minimization of the prediction … Read more

Data-driven sample average approximation with covariate information

Published: 2020/07/24, Updated: 2022/08/01

Rohit Kannan

Güzin Bayraksan

James R. Luedtke

Stochastic Programming covariates, data-driven stochastic programming, jackknife, large deviations, regression, sample average approximation

We study optimization for data-driven decision-making when we have observations of the uncertain parameters within the optimization model together with concurrent observations of covariates. Given a new covariate observation, the goal is to choose a decision that minimizes the expected cost conditioned on this observation. We investigate three data-driven frameworks that integrate a machine learning … Read more

Multi-period investment pathways – Modeling approaches to design distributed energy systems under uncertainty

Published: 2020/07/21

(Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Stochastic Programming

Multi-modal distributed energy system planning is applied in the context of smart grids, industrial energy supply, and in the building energy sector. In real-world applications, these systems are commonly characterized by existing system structures of different age where monitoring and investment are conducted in a closed-loop, with the iterative possibility to invest. The literature contains … Read more

Column-Randomized Linear Programs: Performance Guarantees and Applications

Published: 2020/07/20, Updated: 2023/11/28

Yi-Chun Akchen

Velibor Mišić

Linear Programming, Stochastic Programming

We propose a randomized method for solving linear programs with a large number of columns but a relatively small number of constraints. Since enumerating all the columns is usually unrealistic, such linear programs are commonly solved by column generation, which is often still computationally challenging due to the intractability of the subproblem in many applications. … Read more

Strong Formulations for Distributionally Robust Chance-Constrained Programs with Left-Hand Side Uncertainty under Wasserstein Ambiguity

Published: 2020/07/13, Updated: 2020/12/06

Robust Optimization, Stochastic Programming chance constraints, covering and packing, distributionally robust optimization, mixing inequalities, wasserstein ambiguity

Distributionally robust chance-constrained programs (DR-CCP) over Wasserstein ambiguity sets exhibit attractive out-of-sample performance and admit big-$M$-based mixed-integer programming (MIP) reformulations with conic constraints. However, the resulting formulations often suffer from scalability issues as sample size increases. To address this shortcoming, we derive stronger formulations that scale well with respect to the sample size. Our focus … Read more

Cut-Sharing Across Trees and Efficient Sequential Sampling for SDDP with Uncertainty in the RHS

Published: 2020/07/13

Pedro Borges de Melo

Dynamic Programming, Stochastic Programming

In this paper we show that when a multistage stochastic problem with stage-wise independent realizations has only RHS uncertainties, solving one tree provides a valid lower bound for all trees with the same number of scenarios per stage without any additional computational effort. The only change to the traditional algorithm is the way cuts are … Read more