Markov Chain–Based Policies for Multistage Stochastic Integer Linear Programming with an Application to Disaster Relief Logistics.

This article focuses on developing an aggregation framework to solve multistage stochastic integer linear programs (MSILPs) with mixed-integer state variables and continuous local variables, particularly when the underlying stochastic process is modeled as a Markov chain (MC). The framework reformulates MSILPs by relocating all integer state variables to the first stage and applying MC-based transformations to aggregate these variables, thereby reducing computational complexity while maintaining solution quality. An exact solution method integrating branch-and-cut (B&C) with stochastic dual dynamic programming (SDDP) is proposed, alongside computationally efficient two-stage linear decision rule (2SLDR) approximations, including a novel MC-based variant. The methodologies are applied to a hurricane disaster relief logistics planning problem involving contingency modality activation, demonstrating that adaptive policies leveraging current and previous MC states yield significant improvements over static approaches, especially in constrained systems or under high penalty costs. The study highlights the importance of operational agility to realize the benefits of adaptive planning and suggests that the framework is broadly applicable to other MSILPs with MC-structured uncertainty.