Publications

    • Infrastructure Inspection with Imperfect Detection Technology
      with J. Haden Boone. Submitted.
      Conference / Show Abstract

      Abstract
      We consider a two-player zero-sum inspection game, in which a limited number of detectors are coordinated in an infrastructure system according to a probability distribution to detect multiple attacks from a strategic opponent. Detection is assumed to be imperfect and depends on the detectors’ technology and the infrastructure’s properties. We analytically characterize Nash equilibria of this large-scale game for problem instances where each component is detected from one detector location and the attacker has limited resources. Our equilibrium analysis provides a new criticality assessment of the infrastructure’s components in strategic settings. It also demonstrates new equilibrium behavior from the players that intricately depends on their amount of resources, as well as the detection technology and infrastructure topology.
    • Lead-Time-Constrained Middle Mile Consolidation Network Design with Fixed Origins and Destinations
      with Lacy Greening and Alan Erera. Submitted.
      Preprint / Optimization Online / Show Abstract

      Abstract
      Many large e-commerce retailers move sufficient freight volumes to operate private middle mile consolidation networks for order fulfillment, transporting customer shipments from stocking locations to last mile delivery partners by building consolidated freight transportation loads to reduce outbound logistics cost. In this article, we study a middle mile network design problem with fixed origins and destinations to determine minimum cost consolidation plans that satisfy customer shipment lead-time constraints. We propose models that extend traditional flat network service network design problems to capture waiting delays between load dispatches and ensure that shipment lead-time requirements are satisfied with a desired probability. We approximate these chance constraints using hyperparameterized linear constraints, resulting in new mixed-integer programs (MIPs) for service network design. To find high-quality solutions to the proposed difficult-to-solve MIPs, we develop an effective integer-programming-based local search (IPBLS) heuristic that iteratively improves a solution by optimizing over a smartly selected subset of commodities. For the largest problem instances, we propose a two-phase IPBLS heuristic that first utilizes a simplified, restricted MIP that constrains leg waiting delays individually. Computational experiments using data from a large U.S.-based e-commerce partner demonstrate the significant impact of tight lead-time constraints on the structure of the consolidation network designs and their concomitant operating costs. Notably, tighter constraints lead to solutions with increased shipment consolidation and higher dispatch frequencies on selected key transportation lanes. Such solutions trade off higher shipment transit times with significantly reduced shipment waiting times to meet lead-time constraints at lower cost.
    • Resilient Hyperconnected Parcel Delivery Network Design Under Disruption Risks
      with Onkar Kulkarni and Benoit Montreuil. International Journal of Production Economics, September 2022.
      Journal / DOI / Show Abstract

      Abstract
      Logistics networks are prone to disruptions inducing an increase in delivery costs and delays. Motivated by new opportunities introduced by the Physical Internet, this article studies the problem of designing resilient hyperconnected logistics hub networks. We propose two solution approaches based on integer programs (IPs) that aim to open logistics hubs in order to connect a set of origin-destination pairs using (i) multiple shortest paths and (ii) multiple shortest edge-disjoint paths. To address the inherent computational tractability issues of the first solution approach, we develop a matheuristic that leverages the structure of the problem and iteratively improves the solution by solving the same but restricted IP. To estimate the resilience of the designed networks, we propose graph-theoretic measures involving the maximum number of edge-disjoint paths connecting each origin-destination pair, and the number of short paths traversing each edge. We then develop a case study to design a class of hyperconnected parcel delivery networks in China and evaluate the impact of various disruption scenarios on the resulting distance traveled by parcels. Our results show a significant increase in the designed networks’ capability to sustain disruptions in comparison to traditional lean logistics meshed networks, with marginal compromise in performance in the absence of disruptions. This study validates the relevance of the proposed resilience measures in estimating network resilience and demonstrates the value of hyperconnectivity in designing efficient and resilient logistics networks.
    • Network Inspection from Locations with Imperfect Detection Capabilities
      with Bastián Bahamondes. American Control Conference (ACC), June 2022.
      Conference / DOI / Show Abstract

      Abstract
      We consider a two-player network inspection game, in which a defender positions a limited number of detectors according to a probability distribution in order to detect multiple attacks caused by an attacker. We assume that detection is imperfect, and each detector location is associated with a probability of detecting attacks within its set of monitored network components. The objective of the defender (resp. attacker) is to minimize (resp. maximize) the expected number of undetected attacks. Under mild assumptions on the detection capabilities and the number of attacks, we analytically characterize Nash equilibria of this zero-sum game when the monitoring sets are mutually disjoint. Our equilibrium analysis shows how the criticality of network components jointly depends on both players’ resources, detection rates, and the network topology. We leverage our results in the disjoint case to provide heuristic solutions to the general case by solving a minimum weighted set cover problem. Our computational results on a benchmark distribution network illustrate the performance and scalability of our solution approach.
    • Network Inspection for Detecting Strategic Attacks
      with Saurabh Amin and Lina Sela. Operations Research, January 2022.
      Journal / DOI / Show Abstract

      Abstract
      We study the generic problem of strategic network inspection, in which a defender (inspection agency) is tasked with detecting the presence of multiple attacks in the network. The defender has access to a limited number of detectors that she can randomly position in the network to monitor its components. We address the question of determining a randomized inspection strategy with minimum number of detectors that ensures a target expected attack detection rate. To address this question, we formulate a mathematical program with constraints involving the Nash equilibria of a large-scale strategic game between the defender and attacker. We develop a novel approach to construct an approximate equilibrium strategy profile of the game by utilizing solutions of minimum set cover and maximum set packing problems. This construction can be viewed as a generalization of some of the previously known results in security games, and is scalable to large-scale networks. Importantly, by using game-theoretic and combinatorial arguments, we provide optimality guarantees of our solution to the inspection problem in terms of the number of detectors and attack detection rate. We also derive a structural result on the attack detection rate in equilibrium, which can be applied to further improve these guarantees through a column generation procedure.
    • Network Inspection Using Heterogeneous Sensors for Detecting Strategic Attacks
      with Bobak McCann. Hawaii International Conference on System Sciences (HICSS), Virtual, January 2022.
      – Finalist, HICSS-55 Best Paper Award
      Conference / URI / PDF / Show Abstract

      Abstract
      We consider a two-player network inspection game, in which a defender allocates sensors with potentially heterogeneous detection capabilities in order to detect multiple attacks caused by a strategic attacker. The objective of the defender (resp. attacker) is to minimize (resp. maximize) the expected number of undetected attacks by selecting a potentially randomized inspection (resp. attack) strategy. We analytically characterize Nash equilibria of this large-scale zero-sum game when every vulnerable network component can be monitored from a unique sensor location. We then leverage our equilibrium analysis to design a heuristic solution approach based on minimum set covers for computing inspection strategies in general. Our computational results on a benchmark cyber-physical distribution network illustrate the performance and computational tractability of our solution approach.
    • Probability Distributions on Partially Ordered Sets and Network Interdiction Games
      with Saurabh Amin and Patrick Jaillet. Mathematics of Operations Research, December 2021.
      Journal / DOI / Show Abstract

      Abstract
      We consider the following problem: Does there exist a probability distribution over subsets of a finite partially ordered set (poset), such that a set of constraints involving marginal probabilities of the poset’s elements and maximal chains is satisfied? In this article, we present a combinatorial algorithm to positively resolve this question. We show that this result plays a crucial role in the equilibrium analysis of a generic security game on a capacitated flow network. The game involves a routing entity that sends its flow through the network while facing path transportation costs, and an interdictor who simultaneously interdicts one or more edges while facing edge interdiction costs. The first (resp. second) player seeks to maximize the value of effective (resp. interdicted) flow net the total transportation (resp. interdiction) cost. Using our existence result on posets and strict complementary slackness in linear programming, we show that the equilibrium properties of this game can be described using primal and dual solutions of a minimum cost circulation problem. Our analysis provides a new characterization of the critical network components.
    • Resilient Hyperconnected Logistics Hub Network Design
      with Onkar Kulkarni, Yaarit M. Cohen, and Benoit Montreuil. IPIC 2021, Virtual, June 2021.
      Conference / PDF / Show Abstract

      Abstract
      Logistics networks frequently face disruptions inducing an increase in delivery costs and delays. This paper studies the design of resilient hyperconnected logistics hub networks for the Physical Internet, modeled as an integer programming problem. The objective is to open logistics hubs in order to connect each origin and destination using multiple minimum length edge-disjoint paths. To estimate the resilience of the designed networks, we propose graph-theoretic measures involving (i) the maximum number of edge-disjoint paths connecting each origin and destination, and (ii) the number of short paths traversing each edge. We develop a case study to design a class of parcel delivery networks in China and evaluate the impact of various disruption scenarios on the resulting distance traveled by parcels. Our results show the relevance of the proposed resilience measures and the increased capability of the designed networks to sustain disruptions in comparison to traditional logistics networks.
    • Design of a Simulation-Based Experiment for Assessing the Relevance of the Physical Internet Concept for Humanitarian Supply Chains
      with Manon Grest, Mahmut Metin Inan, Yaarit M. Cohen, Ali V. Barenji, Matthieu Lauras, and Benoit Montreuil. IPIC 2021, Virtual, June 2021.
      Conference / PDF / Show Abstract

      Abstract
      The challenges faced in delivering relief items to victims of natural disasters and the growing external pressures urge humanitarian supply chain organizations to initiate some change. In this regard, the physical internet concept can offer a paradigm shift in relief organization and resource mobilization. To convince humanitarian actors to embrace this path, we propose a rigorous methodology leveraging a prototypical agent-oriented discrete-events simulator built within the AnyLogic platform, to conduct scientific experiments enabling to investigate the suitability and relevance of PI concepts for HSCs by systematically quantifying their benefits and drawbacks on HSC performance, sustainability, and resilience. We provide preliminary experimental results contrasting the baseline shaped by the current HSC structures, behaviors and practices, notably relative to sourcing, transporting, and warehousing, with those of hyperconnected HSCs in line with the Physical Internet at distinct degrees of maturity. In the experiment, we study past disaster scenarios that occurred in Indonesia and response efforts under different behaviors simulated with this platform. Initial results show that PI concepts are smoothly fitted to HSCs and the performance of hyperconnected HSCs is better than the current baseline.
    • Toward an Innovative Risk- and Opportunity-Oriented System for SMEs’ Decision-Makers
      with Romain Ben Taleb, Aurélie Montarnal, Matthieu Lauras, and Romain Miclo. CIGI QUALITA 2021, Virtual, May 2021.
      Conference / HAL_ID / Show Abstract

      Abstract
      The COVID-19 crisis has demonstrated numerous weaknesses in Small- and Medium-sized Enterprises (SMEs). Among them, the incapability of top management to make robust strategic decisions in an uncertain environment composed of risks and opportunities, is probably one of the most critical. Unfortunately, such a disrupted context is now the norm. By analyzing the situation, we notice that most of these top management decision-makers use traditional Strategy and Management Accounting methods to make decisions for their business. However, these methods have numerous limits regarding the management of uncertainties. Notably, most of them are deterministic and reactive (i.e., a posteriori analysis) and they often manage risks through pure qualitative approaches. Based on these limitations, this article develops the fundamentals of a first innovative model focused on the management of assets and inspired by Industrial Engineering and Artificial Intelligence risk- and opportunity-oriented tools. The proposed approach intends to support more robust strategic decisions in disrupted contexts. An illustrative case is then developed in order to highlight the potentiality of our approach. Finally, some avenues for future research are exposed regarding the current work which is currently in its infancy.
    • A Network Monitoring Game with Heterogeneous Component Criticality Levels
      with Saurabh Amin, Jezdimir Milošević, and Henrik Sandberg. 58th IEEE Conference on Decision and Control (CDC), Nice, France, December 2019.
      Conference / DOI / Show Abstract

      Abstract
      We consider an attacker-operator game for monitoring a large-scale network that is comprised of components that differ in their criticality levels. In this zero-sum game, the operator seeks to position a limited number of sensors to monitor the network against the attacker who strategically targets a network component. The operator (resp. attacker) seeks to minimize (resp. maximize) the network loss. To study the properties of mixed-strategy Nash Equilibria of this game, we first study two simple instances: When component sets monitored from individual sensor locations are mutually disjoint; When only a single sensor is positioned, but with possibly overlapping monitoring component sets. Our analysis reveals new insights on how criticality levels impact the players equilibrium strategies. Next, we extend a previously developed approach to obtain an approximate Nash equilibrium in the general case. This approach uses solutions to minimum set cover and maximum set packing problems to construct an approximate Nash equilibrium. Finally, we implement a column generation procedure to improve this solution and numerically evaluate the performance of our approach.
    • Strategic and Analytics-Driven Inspection Operations for Critical Infrastructure Resilience
      Doctoral Thesis, June 2019.
      Thesis / PDF / Show Abstract

      Abstract
      Resilience of infrastructure networks is a key requirement for a functioning modern society. These networks work continuously to enable the delivery of critical services such as water, natural gas, and transportation. However, recent natural disasters and cyber-physical security attacks have demonstrated that the lack of effective failure detection and identification capabilities is one of the main contributors of economic losses and safety risks faced by service utilities. This thesis focuses on both strategic and operational aspects of inspection processes for large-scale infrastructure networks, with the goal of improving their resilience to reliability and security failures. We address three combinatorial problems: (i) Strategic inspection for detecting adversarial failures; (ii) Strategic interdiction of malicious network flows; (iii) Analytics-driven inspection for localizing post-disaster failures. We exploit the structural properties of these problems to develop new and practically relevant solutions for inspection of large-scale networks, along with approximation guarantees.

      Firstly, we address the question of determining a randomized inspection strategy with minimum number of detectors that ensures a target detection performance against multiple adversarial failures in the network. This question can be formulated as a mathematical program with constraints involving the Nash equilibria of a large strategic game. We solve this inspection problem with a novel approach that relies on the submodularity of the detection model and solutions of minimum set cover and maximum set packing problems.

      Secondly, we consider a generic network security game between a routing entity that sends its flow through the network, and an interdictor who simultaneously interdicts multiple edges. By proving the existence of a probability distribution on a partially ordered set that satisfies a set of constraints, we show that the equilibrium properties of the game can be described using primal and dual solutions of a minimum-cost circulation problem. Our analysis provides a new characterization of the critical network components in strategic flow interdiction problems.

      Finally, we develop an analytics-driven approach for localizing failures under uncertainty. We utilize the information provided by failure prediction models to calibrate the generic formulation of a team orienteering problem with stochastic rewards and service times. We derive a compact mixed-integer programming formulation of the problem that computes an optimal a-priori routing of the inspection teams. Using the data collected by a major gas utility after an earthquake, we demonstrate the value of predictive analytics for improving their response operations.

    • Leveraging sUAS for Infrastructure Network Exploration and Failure Isolation
      with Saurabh Amin, Andrew C. Lee, and Andrew J. Weinert. Journal of Intelligent & Robotic Systems, April 2018.
      Journal / DOI / Show Abstract

      Abstract
      Large-scale infrastructures are prone to simultaneous faults when struck by a natural or man-made event. The current operating procedure followed by many utilities needs improvement, both in terms of monitoring performance and time to repair. Motivated by the recent technological progress on small Unmanned Aerial Systems (sUAS), we propose a practical framework to integrate the monitoring capabilities of sUAS into standard utility repair operations. A key aspect of our framework is the use of monitoring locations for sUAS-based inspection of failures within a certain spatial zone (called a localization set). This set is defined based on the alerts from fixed sensors or customer calls. The positioning of monitoring locations is subject to several factors such as sUAS platform, network topology, and airspace restrictions. We formulate the problem of minimizing the maximum time to respond to all failures by routing repair vehicles to various localization sets and exploring these sets using sUAS. The formulation admits a natural decomposition into two sub-problems: the sUAS Network Exploration Problem (SNEP); and the Repair Vehicle Routing Problem (RVRP). Standard solvers can be used to solve the RVRP in a scalable manner; however, solving the SNEP for each localization set can be computationally challenging. To address this limitation, we propose a set cover based heuristic to approximately solve the SNEP. We implement the overall framework on a benchmark network.
    • Integration of sUAS-Enabled Sensing for Leak Identification with Oil and Gas Pipeline Maintenance Crews
      with Saurabh Amin and Andrew C. Lee. 2017 International Conference on Unmanned Aircraft Systems, Miami, FL, June 2017.
      Conference / DOI / Show Abstract

      Abstract
      The U.S. Department of Energy and Transportation considers pipeline security and the timely containment of leaks as a top priority for the oil and natural gas industry. However, despite significant investment in network sensing and maintenance, utilities still incur significant delays (and associated losses) in managing failures. This article focuses on the use of small Unmanned Aerial Systems (sUASs) for the inspection of network components and to facilitate timely repair of failures. Our framework integrates sUAS-enabled sensing with fixed sensing systems and ground-based maintenance crews, and aims to minimize the time to repair multiple network failures. It also reduces human effort in network inspection (e.g. manned reconnaissance, ground patrols, and leak surveys). We consider inspection tasks on a set of failure regions (localization sets) that are generated from fixed sensors installed on the network (e.g. pressure sensors). We focus on the problem of routing a set of available maintenance vehicles at specified yard (base) locations carrying sUASs to optimally identify and repair the network failures. To address this problem, we propose two Mixed-Integer Programming (MIP) formulations: (a) the multi-trip sUAS exploration problem, and (b) maintenance vehicle routing problem. We show that these formulations can be integrated to optimally route the sUASs for identification of multiple network failures that may occur anywhere within the localization sets (MIP-a); and to optimally dispatch maintenance vehicles to repair the identified network failures (MIP-b). We illustrate this approach on a benchmark pipeline network, and demonstrate the inherent tradeoffs between sUAS exploration time and maintenance vehicle travel time in our solution.
    • Network Sensing for Security Against Link Disruption Attacks
      with Saurabh Amin and Lina Sela Perelman. 54th Allerton Conference on Communication, Control and Computing, Urbana, IL, October 2016.
      ConferenceDOI / Show Abstract

      Abstract
      We consider the problem of detecting security failures caused by a resource-constrained attacker using randomized sensing strategies. We propose a game-theoretic model in which the objective of the attacker (resp. defender) is to maximize the number of undetected attacks (resp. detections) on the network. Our game is strategically equivalent to a zero-sum game. Thus, the Nash Equilibria (NE) solution can be found by solving two linear programming (LP) problems. Still, characterization of equilibrium strategies is not tractable for large-scale networks. We assume that the defender’s (resp. attacker’s) detection (resp. attack) budget is limited relative to the size of the network. Under this assumption, we provide structural results on the equilibrium payoffs based on the players’ resources and the size of the minimum set covers. We show that an equilibrium strategy of the defender is to choose a randomized sensing strategy that spans a minimum set cover. This result significantly improves the tractability of NE computation, and provides some practical insights on network sensing in adversarial environments.
    • Network Security and Min-Cost Max-Flow Problem
      Masters Thesis, February 2016.
      Thesis / DSpace / Show Abstract

      Abstract
      Network optimization has widely been studied in the literature for a variety of design and operational problems. This has resulted in the development of computational algorithms for the study of classical operations research problems such as the maximum flow problem, the shortest path problem, and the network interdiction problem. However, in environments where network components are subject to adversarial failures, the network operator needs to strategically allocate at least some of her resources (e.g., link capacities, network flows, etc.) while accounting for the presence of a strategic adversary. This motivates the study of network security games. This thesis considers a class of network security games on flow networks, and focuses on utilizing well-known results in network optimization toward the characterization of Nash equilibria of this class of games.

      Specifically, we consider a 2-player strategic game for network routing under link disruptions. Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. Linear programming duality and the Max-Flow Min-Cut Theorem are applied to obtain properties that are satisfied in any Nash equilibrium. Using graph theoretic arguments, we give a characterization of the support of the equilibrium strategies. Finally, we study the conditions under which these results extend to a revised version of the game where both players face budget constraints. Thus, our contribution can be viewed as a generalization of the classical minimum cost maximum flow problem and the minimum cut problem to adversarial environments.

    • Network Flow Routing under Strategic Link Disruptions
      with Saurabh Amin. 53rd Allerton Conference on Communication, Control and Computing, Urbana, IL, October 2015.
      ConferenceDOI / Show Abstract

      Abstract
      This paper considers a 2-player strategic game for network routing under link disruptions. Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. This game is strategically equivalent to a zero-sum game. Linear programming duality and the max-flow min-cut theorem are applied to obtain properties that are satisfied in any mixed Nash equilibrium. In any equilibrium, both players achieve identical payoffs. While the defender’s expected transportation cost decreases in attacker’s marginal value of lost flow, the attacker’s expected cost of attack increases in defender’s marginal value of effective flow. Interestingly, the expected amount of effective flow decreases in both these parameters. These results can be viewed as a generalization of the classical max-flow with minimum transportation cost problem to adversarial environments.