Decomposition-based Stochastic Programming Models and Algorithms for Discrete-event Dynamic Systems
Abstract
We often encounter periodic planning and operations decisions taken in an uncertain and dynamic environment. Multistage stochastic,programming (MSP) has proven to be highly effective in handling such time-driven decision processes. In many applications of practic,al interest, however, we also encounter situations when we make decisions in response to events that are prompted by exogenous uncer,tain factors. A search and rescue operation serves as a concrete example where decisions are taken in response to uncertain events.,This project aims to develop advanced decomposition-based stochastic programming models and solution methods for such stochastic, dy,namic, and event-driven decision processes. The MSP models for discrete-event dynamic systems (DEDS) include a design stage and mult,iple recourse stages. The recourse stages are analogous to the event epochs where we take adaptive/recourse decisions in response to, the event. The multistage aspect of the models avoids myopic choices by accounting for the continually evolving and uncertain state, of the future. A critical feature of our modeling approach is the representation of sample paths using event relationship graphs th,at have an equivalent mathematical programming form. Since the MSP models for DEDS involve design-dependent sample paths, external s,ampling and static instance-based approaches are not applicable. Therefore, we rely upon internal sampling as the driving principle,of our solution methods. Internal sampling-based algorithms entertain dynamic instances where new sample paths are incorporated conc,urrently within the optimization step of the algorithm. Concurrent simulation and optimization allow these methods to provide high-q,uality solutions while retaining desirable scalability properties. The project will build upon successful experiences with internal,sampling methods in time-driven settings to advance solution methods for the new challenging class of MSP models for DEDS. This pro,ject will also advance the notion of statistical optimality for time-driven for event-driven MSP models. Since internal sampling met,hods involve the addition of new observations (event sample-paths, for example) on the fly, the in-sample stopping rules will determ,ine when the algorithm can be terminated. This will involve the statistical assessment of value function approximations and optimali,ty gaps. The out-of-sample rules will further assess the quality of solutions using independent replications. Statistical inference,tools such as bootstrapping and probability distance metrics will play a significant role in the design and execution of these asses,sment tools. The project unifies concepts from stochastic programming, discrete-event simulation, and statistics. It takes a holisti,c approach that includes both theoretical and computational emphases. The methods developed will be critical tools for strategic pla,nning and operational decision-making under uncertainty in numerous military and civilian settings.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 08, 2022
- Source ID
- N000142212603
Entities
People
- Harsha Gangammanavar
Organizations
- Office of Naval Research
- Southern Methodist University
- United States Navy