-

 

 

 




Optimization Online





 

Optimal Crashing of an Activity Network with Disruptions

Haoxiang Yang(haoxiangyang89***at***gmail.com)
David Morton(david.morton***at***northwestern.edu)

Abstract: 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, which has not yet started, 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.

Keywords: Project crashing, Stochastic disruptions, Two-stage stochastic mixed integer programming, Spatial branch-and-cut

Category 1: Stochastic Programming

Citation:

Download: [PDF]

Entry Submitted: 10/02/2019
Entry Accepted: 10/03/2019
Entry Last Modified: 10/02/2019

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society