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

Problem definition: Multistage stochastic programs involving mixed-integer state variables and continuous local variables (MSILPs) present a challenging class of optimization problems with limited techniques available to obtain high-quality solutions efficiently. These problems arise in many practical applications, including disaster relief logistics planning for natural disasters such as hurricanes, which is increasingly important due to its significant societal impacts. Methodology/results: We introduce an aggregation framework to address MSILPs that impose additional structure on the integer state variables by leveraging information from the underlying stochastic process, which is modeled as a Markov chain (MC). We demonstrate that the aggregated MSILP can be solved exactly via a branch-and-cut algorithm integrated with a variant of the stochastic dual dynamic programming method. To improve tractability, we use this approach to obtain dual bounds. To obtain high-quality decision policies with significantly reduced computational effort, we apply two-stage linear decision rule (2SLDR) approximations, including a new MC-based variant that we propose. Managerial implications: We test the proposed methodologies on an MSILP arising from hurricane disaster relief logistics planning. Our empirical evaluation compares the effectiveness of the various proposed approaches and analyzes the tradeoffs between policy flexibility, solution quality, and computational effort. Specifically, the 2SLDR approximation yields provable high-quality solutions for our test instances, supported by the proposed bounding procedure. We also extract valuable managerial insights from the solution behaviors exhibited by the underlying decision policies: (i) adaptive planning is most valuable in constrained systems; (ii) effective policies incorporate trend indicators to anticipate future needs; and (iii) adaptability can capture the majority of performance gains over static approaches.

Funding: M. Castro was partially supported by the National Center for Artificial Intelligence [Grant CENIA FB210017 (Basal ANID)] and the Agencia Nacional de Investigación y Desarrollo of Chile [Grant ANID-FONDECYT-11230797]. Y. Song was partially supported by the National Science Foundation [Grant Agreement CMMI 2045744]. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Supplemental Material: The online appendices are available at https://doi.org/10.1287/msom.2023.0658.