Publications

    • Stochastic Game for Dynamic Operational Planning in Military Campaigns
      with Joseph McCarthy and Chelsea White. Submitted.
      Preprint / arXiv / Show Abstract

      Abstract
      We study a two-player discounted zero-sum stochastic game model for dynamic operational planning in military campaigns. At each stage, the players manage multiple commanders who order military actions on objectives that have an open line of control. When a battle over the control of an objective occurs, its stochastic outcome depends on the actions and the enabling support provided by the control of other objectives. Each player aims to maximize the cumulative number of objectives they control, weighted by their criticality. To solve this large-scale stochastic game, we derive properties of its Markov perfect equilibria by leveraging the logistics and military operational command and control structure. We show the consequential isotonicity of the optimal value function with respect to the partially ordered state space, which in turn leads to a significant reduction of the state and action spaces. We also accelerate Shapley’s value iteration algorithm by eliminating dominated actions and investigating pure equilibria of the matrix game solved at each iteration. We demonstrate the computational value of our equilibrium results on a case study that reflects representative operational-level military campaigns with geopolitical implications. Our analysis reveals a complex interplay between the game’s parameters and dynamics in equilibrium, resulting in new military insights for campaign analysts.
    • Resilient Relay Logistics Network Design: A k-Shortest Path Approach
      with Onkar Kulkarni and Benoit Montreuil. Submitted.
      Preprint / Optimization Online / Show Abstract

      Abstract
      Problem definition: We study the problem of designing large-scale resilient relay logistics hub networks. We propose a model of \emph{$k$-Shortest Path Network Design}, which aims to improve a network’s efficiency and resilience through its topological configuration, by locating relay logistics hubs to connect each origin-destination pair with $k$ paths of minimum lengths, weighted by their forecasted demand share. Methodology: We formulate this problem as a path-based mixed-integer program with an exponential number of variables and constraints, and leverage its structure to design two scalable solution approaches based on tailored implementations of Benders decomposition and branch-and-price, respectively. In the first approach, we analytically characterize the optimal dual solutions of the exponential-sized Benders subproblem and generate feedback cuts in pseudo-polynomial time using single- and multiple-shortest path subroutines. In the second approach, we show using complementary slackness that the pricing subproblem employed within branch-and-price can also be solved in pseudo-polynomial time by computing multiple shortest paths in a carefully defined graph. Results: We apply our methodology to design large-scale resilient relay networks for a China-based parcel delivery partner. Our computational experiments demonstrate that our developed approaches can obtain optimal solutions for practically relevant instances. The resulting logistics networks showcase a significant improvement in capabilities to sustain hub disruptions with marginal compromise on nominal efficiency, in comparison with relay networks designed to only optimize nominal efficiency. Managerial implications: This work offers valuable insights for logistics service providers aiming to design resilient relay networks with limited information regarding future demand and disruption risks. Our analysis provides decision-makers with recommendations on adjusting the topology of network designs to achieve a desired tradeoff between nominal efficiency and performance under disruptions.
    • Integrating Order-to-Delivery Time Sensitivity and Middle-Mile Consolidation Network Design for E-Commerce Profit Maximization
      with Lacy Greening, Jisoo Park, Alan Erera, and Benoit Montreuil. Submitted.
      Preprint / Optimization Online / Show Abstract

      Abstract
      This paper proposes an approach that leverages data on customer purchasing sensitivity to quoted order-to-delivery times (ODTs) when designing middle-mile consolidation networks to maximize the profit of e-commerce retailers. Our approach integrates quoted ODT-dependent sales volume predictions into a new mixed-integer program (MIP) that simultaneously determines ODT quotes and a consolidation plan, characterized by the frequency of load dispatches on each transportation lane. The objective of the MIP is to maximize sales revenue net fulfillment cost while ensuring that quoted ODTs are met with a high probability as set by the retailer. We linearize the ODT chance constraints by approximating the waiting delay incurred between load dispatches using convex piecewise-linear functions. To find high-quality solutions for large, practically sized instances, we build an adaptive IP-based local search heuristic that improves an incumbent solution by iteratively optimizing over a smartly selected subset of commodity ODT and/or route options, which is randomized and adjusted based on solver performance. Results from a U.S.-based e-commerce partner show that our approach leads to a profit increase of 10% when simply allowing a marginal change of one day to the current ODT quotes. In general, we observe that integrating ODT-dependent customer purchasing estimation into a decision model for joint ODT quotation and consolidation network design achieves an optimal trade-off between revenue and fulfillment cost.
    • Strategic Monitoring of Networked Systems with Heterogeneous Security Levels
      with Saurabh Amin, Jezdimir Milošević, and Henrik Sandberg. IEEE Transactions on Control of Network Systems, October 2023.
      Journal / DOI / Show Abstract

      Abstract
      We consider a strategic network monitoring problem involving the operator of a networked system and an attacker. The operator aims to randomize the placement of multiple protected sensors to monitor and protect components that are vulnerable to attacks. We account for the heterogeneity in the components’ security levels and formulate a large-scale maximin optimization problem. After analyzing its structure, we propose a three-step approach to approximately solve the problem. First, we solve a generalized covering set problem and run a combinatorial algorithm to compute an approximate solution. Then, we compute approximation bounds by solving a nonlinear set packing problem. To evaluate our solution approach, we implement two classical solution methods based on column generation and multiplicative weights updates, and test them on real-world water distribution and power systems. Our numerical analysis shows that our solution method outperforms the classical methods on large-scale networks, as it efficiently generates solutions that achieve a close to optimal performance and that are simple to implement in practice.
    • Hide-and-Seek Game with Capacitated Locations and Imperfect Detection
      with Bastián Bahamondes. Decision Analysis, October 2023.
      Journal / DOI / Show Abstract

      Abstract
      We consider a variant of the hide-and-seek game in which a seeker inspects multiple hiding locations to find multiple items hidden by a hider. Each hiding location has a maximum hiding capacity and a probability of detecting its hidden items when an inspection by the seeker takes place. The objective of the seeker (resp. hider) is to minimize (resp. maximize) the expected number of undetected items. This model is motivated by strategic inspection problems, where a security agency is tasked with coordinating multiple inspection resources to detect and seize illegal commodities hidden by a criminal organization. To solve this large-scale zero-sum game, we leverage its structure and show that its mixed strategies Nash equilibria can be characterized using their unidimensional marginal distributions, which are Nash equilibria of a lower dimensional continuous zero-sum game. This leads to a two-step approach for efficiently solving our hide-and-seek game: First, we analytically solve the continuous game and compute the equilibrium marginal distributions. Second, we derive a combinatorial algorithm to coordinate the players’ resources and compute equilibrium mixed strategies that satisfy the marginal distributions. We show that this solution approach computes a Nash equilibrium of the hide-and-seek game in quadratic time with linear support. Our analysis reveals a complex interplay between the game parameters and allows us to evaluate their impact on the players’ behaviors in equilibrium and the criticality of each location.
    • Lead-Time-Constrained Middle-Mile Consolidation Network Design with Fixed Origins and Destinations
      with Lacy Greening and Alan Erera. Transportation Research Part B: Methodological, August 2023.
      Journal / DOI / 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 in consolidated loads to reduce freight costs. We study a middle-mile network design optimization problem with fixed origins and destinations to build load consolidation plans that minimize cost and 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 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.
    • Resilience Assessment of Hyperconnected Parcel Logistic Networks Under Worst-Case Disruptions
      with Onkar Kulkarni and Benoit Montreuil. 9th International Physical Internet Conference (IPIC), June 2023.
      Conference / DOI / Show Abstract

      Abstract
      Logistics networks that shape the Physical Internet’s logistics web are prone to potentially adversarial disruptions that impact their performance severely. In this article, we study a network interdiction problem on a multi-commodity flow network in which an adversary totally disrupts a set of network arcs with an intention to maximize the operational costs of delivering parcels. We formulate it as a two-stage mixed-integer linear program. To solve such complex large-scale program, we use linear programming duality and provide an algorithm based on the structure of the program that computes the set of network arcs that can be interdicted in order to reduce its size. Finally, we use the model and solution framework to evaluate the resilience capabilities of topology optimized hyperconnected networks and compare it with lean networks. We find that our developed solution methodology reduces the size of network interdiction program substantially and showcases superior computational performance against off-the-shelf optimization solvers. Furthermore, the resilience comparison between hyperconnected networks and lean networks depicts enhanced capabilities of the topology optimized hyperconnected networks to sustain worst-case disruptive events as opposed to that of lean logistics networks.
    • Hyperconnected Logistic Service Networks: Bidding-Based Design Framework
      with Simon Kwon, Benoit Montreuil, and Walid Klibi. 9th International Physical Internet Conference (IPIC), June 2023.
      Conference / DOI / Show Abstract

      Abstract
      In hyperconnected urban logistics, all components and stakeholders are connected on multiple layers through standardized interfaces and open networks to achieve seamless responsiveness, efficiency, resilience, and sustainability. Key for high performance is achieving coordination and cooperation of urban stakeholders. In this Paper, we introduce the design of hyperconnected logistic service networks where associated logistic activities to move flows within an urban city are outsourced to third-party logistic service providers (3PL) via a bidding process to create service networks that are highly responsive and flexible at robustly responding to customer demand. We propose a framework for designing such networks that leverages a reverse combinatorial auction mechanism in which a logistic orchestrator serves as the auctioneer, putting out the logistic activities for auction and a set of participating service providers serve as bidders. We describe the design components of hyperconnected service networks and positions them into a comprehensive 3-stage design-making framework. Finally, we identify promising future research avenues for each stage in the proposed framework.
    • Stochastic Service Network Design with Different Relay Patterns for Hyperconnected Relay Transportation
      with Jingze Li, Xiaoyue Liu, and Benoit Montreuil. 9th International Physical Internet Conference (IPIC), June 2023.
      Conference / DOI / Show Abstract

      Abstract
      Hyperconnected relay transportation enables using a relay system of short-haul drivers to deliver long-haul shipments collectively, which helps address root causes of trucker shortage issues by transforming working conditions with potentials of daily returning home, accessing consistent schedules, and facilitating load matching. This Paper investigates hyperconnected relay transportation as a sustainable solution to trucker shortage issues through a logistics platform. We propose a two-stage programming model to optimize consistent working schedules for short-haul drivers while minimizing transportation costs. The first stage involves opening services and contracting truckers under demand uncertainty, where each service has a service route and approximate service schedules adhering to USA federal short-haul hour-of-service regulations. The second stage assigns hauling capacities to open services and manages commodity shipping or outsourcing given the demand realization. We extend the model formulation to account for various operational patterns (e.g., freight loading and unloading or hauler swapping) and schedule consistency requirements (e.g., weekly or daily consistency). A scenario-based approach is employed to solve the model for a case study of automotive delivery in the Southeast USA region. The experimental results validate the proposed approach, and further explore the impact of stochastic demands, operational patterns, consistent schedules, and hauling capacities on hyperconnected service network design. This research aims to offer practical guidance to practitioners in the trucking industry.
    • Infrastructure Inspection with Imperfect Detection Technology
      with J. Haden Boone. American Control Conference (ACC), May 2023.
      Conference / DOI / 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.
    • Middle-Mile Consolidation Network Design: Maximizing Profit Through Flexible Lead Times
      with Lacy Greening, Jisoo Park, Alan Erera, and Benoit Montreuil. Institute of Industrial and Systems Engineers (IISE) Annual Conference & Expo, May 2023.
      Conference / DOI / Show Abstract

      Abstract
      In this work, we propose an approach that leverages historical customer purchase conversion rates when designing a middle-mile consolidation network that aims to maximize the profit of large e-commerce retailers. We embed lead-time dependent sales volume predictions into a new mixed-integer program (MIP) that simultaneously determines shipment lead times and consolidation plans to maximize profit, i.e.. sales revenue net logistics cost. To find high-quality consolidation plans for large, practically-sized instances, we build an adaptive IP-based local search solution approach. Preliminary results from a U.S.-based e-commerce partner show that incorporating historical customer purchase conversion rates into the consolidation network design increase profit by over 20% depending on the retailer’s desired flexibility when selecting lead times.
    • An Asset-Based Causal Loop Model to Improve Corporate Value
      with Romain Ben Taleb, Aurélie Montarnal, Matthieu Lauras, and Romain Miclo. International Conference on Decision Support System Technology, May 2023.
      Conference / DOI / Show Abstract

      Abstract
      Assessing a company’s value is an important leverage for decision-making. Indeed, all decisions made within a company are generally aimed at maximizing the company’s value. In accounting, almost all models for assessing the value of a company are related to the amount of cash the company is able to generate. As a result, maximizing the value of a firm is usually about maximizing cash flow. However, beyond the usual accounting models, several recent initiatives have highlighted the key role of managing all assets, and not only the ones considered by the general accountability, in decision making and cash generation. Unfortunately, these methods are currently limited to conceptual and qualitative proposals that do not lead to a real decision support system thus far. This paper proposes a first step of formalization aiming at providing tools for these asset-oriented decision support approaches. The contribution is a Causal Loop Diagram to Support Decision-Making in order to maximize the value of companies. Based on a dedicated literature review, we design an asset-based causal loop model that formalizes the qualitative results of the literature review. We then develop an instantiation on an illustrative case via simulation in order to verify the relevance of the proposal and to show how such a model can be used in practice for decision making. This will support next research to develop an asset-based decision support system to maximize value of companies.
    • A Value-Oriented Metamodel for Small and Medium Enterprises’ Decision Making
      with Romain Ben Taleb, Aurélie Montarnal, Matthieu Lauras, and Romain Miclo. International Journal of Industrial and Systems Engineering, May 2023.
      Journal / DOI / Show Abstract

      Abstract
      To be competitive and sustainable, any company has to maximize its value. However, unlike listed companies that can assess their values based on market shares, most Small and Medium Enterprises (SMEs) which are non-listed cannot have direct and live access to this critical information. Traditional accounting reports only give limited insights to SME decision-makers about the real impact of their day-to-day decisions on the company’s performance and value. Most of the time, an SME’s financial valuation is made one time a year as the associated process is time and resource-consuming, requiring several months and external expertise to be completed. To solve this issue, we propose in this paper a value-oriented metamodel that enables real-time and dynamic assessment of the SME’s value based on the large definition of their assets. These assets cover a wider scope of resources of the company and better account for immaterial assets. The proposal, which is illustrated in a case study, discusses the benefits of incorporating assets in the SME valuation.
    • Resilient Hyperconnected Parcel Delivery Network Design Under Disruption Risks
      with Onkar Kulkarni and Benoit Montreuil. International Journal of Production Economics, April 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.