A Logic-based Decomposition Approach for Multi-Period Network Interdiction Models. (September 2019) - Enayaty-Ahangar, Forough; Rainwater, Chase E.; Sharkey, Thomas C.
Highlights: This paper offers a large-scale solution approach to the variant of the problem explored by Malaviya et. al. 2012. A novel application of constraint programming which integrates the technique into a decomposition framework that separates the interdiction and scheduling elements of the problem class. Computational impacts of scheduling horizon and network topography show that the proposed methodology can solve 75% of medium/large instances more efficiently than a blackbox solver. Abstract: This research details the creation of a large-scale optimization approach for solving an application of a multi-period bilevel network interdiction problem (NIP). In this class of multi-period NIP, interdiction activities must be scheduled to minimize the cumulative maximum flow over a finite time horizon. A logic-based decomposition (LBD) approach is proposed that utilizes constraint programming to exploit the scheduling nature of this multi-period NIP. Computational results–comparing solutions obtained using the proposed approach versus traditional mixed-integer programming approach–suggest that the LBD approach is more efficient in finding solutions for medium to large problem instances.