Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems

By Jean-Paul Watson, David L. Woodruff. Computational Management Science, 2011

378 citations recorded by the source corpus.

Numerous planning problems can be formulated as multi-stage stochastic programs and many possess key discrete (integer) decision variables in one or more of the stages. Progressive hedging (PH) is a scenario-based decomposition technique that can be leveraged to solve such problems. Originally devised for problems possessing only continuous variables, PH has been successfully applied as a heuristic to solve multi-stage stochastic programs with integer variables. However, a variety of critical issues arise in practice when implementing PH for the discrete case, especially in the context of very difficult or large-scale mixed-integer problems. Failure to address these issues properly results in either non-convergence of the heuristic or unacceptably long run-times. We investigate these issues and describe algorithmic innovations in the context of a broad class of scenario-based resource allocation problem in which decision variables represent resources available at a cost and constraints enforce the need for sufficient combinations of resources. The necessity and efficacy of our techniques is empirically assessed on a two-stage stochastic network flow problem with integer variables in both stages.

Subfields: Finance, Management Information Systems, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/0e3641b7232efff95f7487b96fdcc47a27fed8e3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Finance

In Management Information Systems

In Management Science and Operations Research

Citations in the corpus

Mobile Emergency Generator Pre-Positioning and Real-Time Allocation for Resilient Response to Natural Disasters (2018, background): “The consensus criteria can also be set based on other metrics such as normalized average per-scenario deviation from the average [36] and overall cost discrepancy [37].”
Learning Fast Optimizers for Contextual Stochastic Integer Programs (2018, methodology): “We implement the progressive hedging algorithm [Watson and Woodruff, 2011] that is based on the dual decomposition approach.”
Decentralized Energy Management System for Networked Microgrids in Grid-Connected and Islanded Modes (2016, methodology): “In this paper, we propose an algorithm based on the deterministic decomposition algorithm introduced in [16] and the concept of progressive hedging [18].”
Pyomo — Optimization Modeling in Python (2012, methodology): “For example, in one-sided diet problems, feasibility can be maintained during slamming by fixing a variable value at the maximum level observed across scenarios (assuming a minimization objective) [60].”
Enhancing Distribution System Resilience With Mobile Energy Storage and Microgrids (2019, methodology): “To solve this problem efficiently, we apply the PH algorithm [18] to the proposed planning problem.”