A general enhancement of the Benders’ decomposition (BD) algorithm can be achieved through the improved use of large neighbourhood search heuristics within mixed-integer programming solvers. While mixed-integer programming solvers are endowed with an array of large neighbourhood search heuristics, few, if any, have been designed for BD. Further, typically the use of large neighbourhood search … Read more
We propose a decomposition algorithm for multistage stochastic programming that resembles the progressive hedging method of Rockafellar and Wets, but is provably capable of several forms of asynchronous operation. We derive the method from a class of projective operator splitting methods fairly recently proposed by Combettes and Eckstein, significantly expanding the known applications of those … Read more
In this paper, we derive deterministic inner approximations for single and joint probabilistic constraints based on classical inequalities from probability theory such as the one-sided Chebyshev inequality, Bernstein inequality, Chernoff inequality and Hoeffding inequality (see Pinter 1989). New assumptions under which the bounds based approximations are convex allowing to solve the problem efficiently are derived. … Read more
We propose a novel way of applying cutting plane techniques to two-stage mixed-integer stochastic programs. Instead of using cutting planes that are always valid, our idea is to apply inexact cutting planes to the second-stage feasible regions that may cut away feasible integer second-stage solutions for some scenarios and may be overly conservative for others. … Read more
We present a scalable branching method for the dual decomposition of stochastic mixed-integer programming. Our new branching method is based on the branching method proposed by Caro e and Schultz that creates branching disjunctions on first-stage variables only. We propose improvements to the process for creating branching disjunctions, including 1) branching on the optimal solutions … Read more
Hydropower is one of the world’s primary renewable energy sources whose usage has profound economic, environmental, and social impacts. We focus on the dispatch of generating units and the storage policy of hydro resources. In this context, an accurate assessment of the water opportunity-cost is cru- cial for driving the sustainable use of this scarce … Read more
We focus on the resource provisioning problem of a cloud consumer from an Infrastructure-as-a-Service type of cloud. The cloud provider offers two deployment options, which can be mixed and matched as appropriate. Cloud instances may be reserved for a fixed time period in advance at a smaller usage cost per hour but require a full … Read more
Stochastic decomposition (SD) has been a computationally effective approach to solve large-scale stochastic programming (SP) problems arising in practical applications. By using incremental sampling, this approach is designed to discover an appropriate sample size for a given SP instance, thus precluding the need for either scenario reduction or arbitrary sample sizes to create sample average … Read more
Motivated by a cybersecurity application, this paper studies a two-stage, stochastic days-off scheduling problem with 1) many types of jobs that require specialized training, 2) many multi-skilled analysts, 3) the ability to shape analyst skill sets through training decisions, and 4) a large number of possible future demand scenarios. We provide a integer linear program … Read more
We consider optimal transport based distributionally robust optimization (DRO) problems with locally strongly convex transport cost functions and affine decision rules. Under conventional convexity assumptions on the underlying loss function, we obtain structural results about the value function, the optimal policy, and the worst-case optimal transport adversarial model. These results expose a rich structure embedded … Read more