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.

The evolving nature of electricity production, transmission and consumption necessitates an update to the IEEE's Reliability Test System, which was last modernized in 1996. The update presented here introduces a generation mix more representative of modern power systems, with the removal of several nuclear and oil generating units and the addition of natural gas, wind, solar photovoltaics, concentrating solar power, and energy storage. The update includes assigning the test system a geographic location in the southwestern United States to enable the integration of spatio-temporally consistent wind, solar, and load data with forecasts. Additional updates include common RTS transmission modifications in published literature, definitions for reserve product requirements and market simulation descriptions to enable benchmarking of multi-period power system scheduling problems. The final section presents example results from a production cost modeling simulation on the updated RTS system data.

We present a mixed-integer programming (MIP) formulation for sensor placement optimization in municipal water distribution systems that includes the temporal characteristics of contamination events and their impacts. Typical network water quality simulations track contaminant concentration and movement over time, computing contaminant concentration time series for each junction. Given this information, we can compute the impact of a contamination event over time and determine affected locations. This process quantifies the benefits of sensing contamination at different junctions in the network. Ours is the first MIP model to base sensor placement decisions on such data, compromising over many individual contamination events. The MIP formulation is mathematically equivalent to the well-known p -median facility location problem. We can exploit this structure to solve the MIP exactly or to approximately solve the problem with provable quality for large-scale problems.

We present a model for optimizing the placement of sensors in municipal water networks to detect maliciously injected contaminants. An optimal sensor configuration minimizes the expected fraction of the population at risk. We formulate this problem as a mixed-integer program, which can be solved with generally available solvers. We find optimal sensor placements for three test networks with synthetic risk and population data. Our experiments illustrate that this formulation can be solved relatively quickly and that the predicted sensor configuration is relatively insensitive to uncertainties in the data used for prediction.