TY - JOUR
T1 - Optimal crashing of an activity network with disruptions
AU - Yang, Haoxiang
AU - Morton, David P.
N1 - Funding Information:
This research is based upon work supported, in part, by the U.S. Department of Homeland Security under Grant Award Number, 2017-ST-061-QA0001. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the U.S. Department of Homeland Security. The Center for Nonlinear Studies at Los Alamos National Laboratory supported Haoxiang Yang’s work. The authors thank two anonymous referees and an associate editor, along with the area editor Dr. Alper Atamtürk, for comments and suggestions that improved the paper.
Funding Information:
This research is based upon work supported, in part, by the U.S. Department of Homeland Security under Grant Award Number, 2017-ST-061-QA0001. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the U.S. Department of Homeland Security. The Center for Nonlinear Studies at Los Alamos National Laboratory supported Haoxiang Yang’s work. The authors thank two anonymous referees and an associate editor, along with the area editor Dr. Alper Atamtürk, for comments and suggestions that improved the paper.
Publisher Copyright:
© 2021, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.
PY - 2022/7
Y1 - 2022/7
N2 - In this paper, we consider an optimization problem involving crashing an activity network under a single disruption. A disruption is an event whose magnitude and timing are random. When a disruption occurs, the duration of an activity that has yet to start—or alternatively, yet to complete—can change. We formulate a two-stage stochastic mixed-integer program, in which the timing of the stage is random. In our model, the recourse problem is a mixed-integer program. We prove the problem is NP-hard, and using simple examples, we illustrate properties that differ from the problem’s deterministic counterpart. Obtaining a reasonably tight optimality gap can require a large number of samples in a sample average approximation, leading to large-scale instances that are computationally expensive to solve. Therefore, we develop a branch-and-cut decomposition algorithm, in which spatial branching of the first stage continuous variables and linear programming approximations for the recourse problem are sequentially tightened. We test our decomposition algorithm with multiple improvements and show it can significantly reduce solution time over solving the problem directly.
AB - In this paper, we consider an optimization problem involving crashing an activity network under a single disruption. A disruption is an event whose magnitude and timing are random. When a disruption occurs, the duration of an activity that has yet to start—or alternatively, yet to complete—can change. We formulate a two-stage stochastic mixed-integer program, in which the timing of the stage is random. In our model, the recourse problem is a mixed-integer program. We prove the problem is NP-hard, and using simple examples, we illustrate properties that differ from the problem’s deterministic counterpart. Obtaining a reasonably tight optimality gap can require a large number of samples in a sample average approximation, leading to large-scale instances that are computationally expensive to solve. Therefore, we develop a branch-and-cut decomposition algorithm, in which spatial branching of the first stage continuous variables and linear programming approximations for the recourse problem are sequentially tightened. We test our decomposition algorithm with multiple improvements and show it can significantly reduce solution time over solving the problem directly.
KW - Project crashing
KW - Spatial branch-and-cut
KW - Stochastic disruptions
KW - Two-stage stochastic mixed-integer programming
UR - http://www.scopus.com/inward/record.url?scp=85109161869&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85109161869&partnerID=8YFLogxK
U2 - 10.1007/s10107-021-01670-x
DO - 10.1007/s10107-021-01670-x
M3 - Article
AN - SCOPUS:85109161869
SN - 0025-5610
VL - 194
SP - 1113
EP - 1162
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -