Yongjia Song

Multistage stochastic programming (MSP) is a class of models for sequential decision-making under uncertainty. MSP problems are known for their computational difficulties, and one common approach to find an approximate decision policy is to resort to the rolling-horizon procedure (RHP). The RHP is a method that involves solving an MSP problem at each roll of its procedure, which is referred to as a look-ahead model. The look-ahead model is typically defined with a smaller number of stages than the original MSP, making them computationally less demanding to solve. However, the reduction in the number of stages may compromise the quality of the resulting decision policy. This leads to an important question of how many stages to use for each look-ahead model in the RHP. In this paper, we propose two alternative approaches to address this question. First, we propose a surrogate model to the original MSP as an infinite-horizon MSP problem with a certain discount factor, from which we derive a bound which can be used to prescribe an appropriate number of stages. Alternatively, we propose a supervised learning approach that learns how to choose an appropriate number of stages for each look-ahead model based on the state of the system in each roll of the RHP, using data collected from offline experiments. Our numerical experiments demonstrate the effectiveness of the proposed approaches on these problems.

Hurricanes are among the deadliest annual disasters in the United States, posing significant challenges for disaster response and evacuation planning. Forecasts from the National Hurricane Center are essential for guiding evacuation and logistics decisions, but these forecasts are subject to uncertainty, complicating the modeling of evacuation and relief logistics. This paper proposes a data-driven multi-stage stochastic programming (MSSP) model for integrated hurricane relief and logistics evacuation planning under forecast uncertainty, aimed at improving out-of-sample (OOS) performance. The framework captures the Markovian dynamics of hurricane track and intensity by leveraging historical forecast errors and kernel regression for conditional distribution estimation. We formulate a data-driven MSSP model within a distributionally robust optimization framework, incorporating historical forecast errors to improve decision-making under uncertainty. We present an approach for utilizing Markov chain (MC) discretization to reduce computational complexity with a trade-off in asymptotic optimality. Through extensive experiments based on a case study of Hurricane Florence, we demonstrate that the data-driven approach improves OOS performance in worst-case scenarios compared to the MSSP model with the nominal MC. Finally, we provide insights into how the data-driven model’s performance varies with key problem parameters.

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 .

In this paper, we present a disaster relief logistics planning problem in anticipation of a hurricane landfall. This problem is modeled as a time-expanded multi-period network flow problem where the objective is twofold: minimizing the logistics costs of the network flow and the penalty costs associated with demand shortage. We propose a multistage stochastic programming (MSSP) model to support the sequential decision-making process under demand uncertainty for the prepositioning and post-hurricane allocation of relief items before and after hurricane landfall. The MSSP model could also incorporate deprivation-based penalties to explicitly account for the duration of unmet demand. We assume that the hurricane’s evolution over time can be modeled as a Markov chain, where each Markovian state is characterized by the hurricane’s attributes (location and intensity). To address the challenges brought by travel times that may span multiple time periods, additional state variables are introduced in each stage of the MSSP model to keep track of the in-transit flows. Through out-of-sample evaluation, we assess the performance of the decision policy given by MSSP model in comparison to alternative approaches, including a static policy based on a two-stage stochastic programming model and a rolling-horizon policy. Finally, our numerical results and sensitivity analyses highlight the value of MSSP in hurricane relief logistics planning.

We consider a bilevel network interdiction problem where the follower aims to maximize the amount of flow from the source node to the sink node, and the leader aims to minimize the number of arcs from a critical set that have positive flow on them, that is, active arcs, in the maximum flow solution obtained by the follower. This problem is motivated by an application in human trafficking disruption. We consider both the optimistic and pessimistic variants of this bilevel optimization problem and develop their respective single-level reformulations. We present a tailored solution method to the pessimistic problem, which solves the problem to optimality for one practically important class of networks. Through computational experiments on randomly generated layered network instances, we show the effectiveness of the proposed methods and demonstrate that the tailored method is orders of magnitude faster than existing approaches in the literature. We also conduct computational experiments on randomly generated test instances inspired by domestic human trafficking networks and draw domain-specific insights. History: Accepted by Russell Bent, Area Editor for Network Optimization: Algorithms & Applications. Funding: This work was supported by the National Science Foundation [Grant 2039584]. The computational experiments discussed in this paper were performed on the Palmetto Computing Cluster. The Palmetto Computing Cluster is supported by the National Science Foundation [Grants MRI# 2024205, MRI# 1725573, and CRI# 2010270]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0423 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0423 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Direct disaster housing plays a critical role in mitigating the social costs of displacement and alleviating the suffering of disaster victims. However, effective disaster housing logistics planning remains a significant challenge, as demonstrated by past major disasters. In this paper, we propose a data-driven decision-support framework that integrates disaster housing demand estimation into long-term disaster housing logistics planning through a multi-horizon stochastic programming (MHSP) model. The MHSP model explicitly accounts for both long-term and short-term demand uncertainty. We develop new solution methods tailored for the MHSP model and validate the proposed framework through numerical experiments that demonstrate its advantages over conventional approaches. Our results highlight the value of incorporating short-term uncertainty into long-term logistics planning, providing insights for policymakers to enhance disaster housing preparedness and response.

The purpose of this repository is to share the codes, instances, and results used in the paper ["A Bi-level Network Interdiction Problem to Minimize the Number of Active Special Arcs in the Maximum Flow"] authored by Daniel B. Lopes da Silva, Thomas C. Sharkey and Yongjia Song.