A Logic-based Decomposition Approach for Multi-Period Network Interdiction Models. (September 2019)

• Record Type: Journal Article
• Authors: Enayaty-Ahangar, Forough; Rainwater, Chase E.; Sharkey, Thomas C.
• Is Part Of: Omega. Volume 87(2019)
• Page Start: 71
• Page End: 85
• Publication Date: 2019-09
• Subjects: Large-scale optimization -- Scheduling -- Multi-period Network Interdiction -- Maximum Flow Problem -- Decomposition Approach -- Constraint Programming; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2018.08.006
• Languages: English
• ISSNs: 0305-0483

Abstract

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.