Optimizing Strategic Planning With Long-term Sequential Decision Making Under Uncertainty: A Decomposition Approach

The operations research literature has seen decision-making methods at both strategic and operational levels, where high-level strategic plans are first devised, followed by long-term policies that guide future day-to-day operations under uncertainties. Current literature studies such problems on a case-by-case basis, without a unified approach. In this study, we investigate the joint optimization of strategic and operational decisions from a methodological perspective, by proposing a generic two-stage long-term strategic stochastic decision-making (LSSD) framework, in which the first stage models strategic decisions with linear programming (LP), and the second stage models operational decisions with Markov decision processes (MDP). The joint optimization model is formulated as a nonlinear programming (NLP) model, which is then reduced to an integer model through discretization.

As expected, the LSSD framework is computationally expensive. Thus, we develop a novel solution algorithm for MDP, which exploit the Benders decomposition with the ``divide-and-conquer'' strategy. We further prove mathematical properties to show that the proposed multi-cut L-shaped (MCLD) algorithm is an exact algorithm for MDP. We extend the MCLD algorithm to solve the LSSD framework by developing a two-step backward decomposition (TSBD) method. To evaluate algorithm performances, we adopt four benchmarking problems from the literature. Numerical experiments show that the MCLD algorithm and the TSBD method outperform conventional benchmarks by up to over 90\% and 80\% in algorithm runtime, respectively.

The practicality of the LSSD framework is further validated on a real-world critical infrastructure systems (CISs) defense problem. In the past decades, ``attacks'' on CIS facilities from deliberate attempts or natural disasters have caused disastrous consequences all over the globe. In this study, we strategically design CIS interconnections and allocate defense resources, to protect the CIS network from sequential, stochastic attacks. The LSSD framework is utilized to model the problem as an NLP model with an alternate integer formulation. We estimate model parameters using real-world CIS data collected from a middle-sized city in the U.S. Previously established algorithms are used to solve the problem with over 45% improvements in algorithm runtime. Sensitivity analyses are conducted to investigate model behaviors and provide insights to practitioners.