Several attempts on network interdiction have been made by different authors in the past due to its application in military operations, supply chain management, pre- vention of illicit drug trade and other related areas. The problem is NP-complete and various techniques have been proposed for solving this problem. In this work we propose a greedy heuristic for the sequential disruption of edges in a network constrained by edge capacity. Because of a few shortcomings in this algorithm, we further include a stochastic component in the selection of edges. The solution was originally developed for the problem statement of the 8thAIMMS - MOPTA Opti- mization Modeling Competition and therefore, the applicability of the technique is shown on the network provided for the competition. Introduction In the network interdiction problem, an ’interdictor’ is provided with limited resources for disrupting a network through which the adversary operates its sup- ply. The goal of the supplier is to maximize its proﬁt using the existing network. This problem is an example of a Stackelberg game [14] where the interdictor ﬁrst Corresponding author Email address: sridharkrn@iitm.ac.in (Sridharakumar Narasimhan ) Preprint submitted to Operations Research Letters June 26, 2017 chooses its disruption policy followed by the supplier choosing its optimal supply policy. One of the earliest works in this ﬁeld was reported by Wollmer [12]. Here, an algorithm was proposed for the removal of arcs from a graph such that the maxi- mum ﬂow between a source and a sink was minimized. Later, Ratliff [9] extended this to the case of narcs. Ghare et al. [6] proposed a branch and bound algo- rithm for a similar problem that is encountered by military commanders. Studying this problem in the context of illegal drug trade, Wood [13] showed that even a simpler version of the problem is NP-complete and developed an integer program- ming model for the problem. An extension of the model was also provided for continuous interdiction of the arcs. Parallel to these, Fulkerson & Harding [4] and Golden [7] worked on maximizing the length of the shortest s-tpath in a network and showed this problem to be equivalent to a minimum cost ﬂow problem. Fur- ther, the problem of a single evader travelling between two nodes and an interdictor setting up inspection points for detection of this was addressed by Washburn and Wood [11]. For a continuous interdiction problem, Lim and Smith [8] showed that the op- timum would have a maximum of one partially disrupted edge as all other edges chosen for disruption would be completely disrupted. As the problem was still dif- ﬁcult to solve, a heuristic was proposed for solving this. Though it provided quick solution is certain cases, the technique was not always reliable. Meanwhile, Cormi- canet al. introduced uncertainties into arc capacities and developed a stochastic integer program for solving it [2]. A connectivity interdiction problem was also modeled and solved by Zenklusen [15]. In a more recent work, Bertsimas et al. have proposed a new modeling framework where the interdictor chooses one of the multiple pure strategies available based on probabilities assigned to them [1]. The authors have referred to this as the randomized network interdiction problem . In 2 the mean time, the model has also seen applications on domains other than military such as multicommodity ﬂow networks [8], communication networks and electric power grids [10]. The exact problem description is given in the next section followed by the solution technique. An alternate interpretation for the theorem given by Lim and Smith [8] is provided and a novel solution technique using a sequential greedy algorithm is discussed. The results obtained while applying this technique on a network is given in the continuing section. Few variations of the parameters used in the algorithm are tried and their performances are reported. Problem description In this section, a resource transportation network with a supplier agent that gen- erates proﬁt by transporting resources from production centers to demand nodes is described. The network used for this paper is adopted from 8th AIMMS-MOPTA competition held at Lehigh university in 2016. The dataset consisting of individual demands for each nodes, edge capacities and cost per unit for edge traversal can be dowloaded from the competition website http://coral.ie.lehigh.edu/ mopta /com- petition. All the nodes are demand points except nodes 15,16 and 20 which are supplier nodes as shown in ﬁgure (1). The supplier agent tries to maximize the transport of resources from the supply points to the demand nodes though the edges. For every unit of goods transported through any edge, the supplier has to pay a transportation cost (which is different for different edges). In addition, the edges are conﬁned by a capacity. Unlimited goods can be generated from the supply points, therefore the trafﬁc in the network is constrained by the maximum capacity on these edges. The goal of the supplier agent is to maximize its proﬁt earned by transporting the 3 goods from the supply nodes to the demand nodes. The interdictor on the other Figure 1: Transportation network hand tries to minimize the supplier’s proﬁt. For this purpose, the interdictor is al- lowed to make reductions in the edge capacities of the network, but with a limited budget constraints. This means that the total amount of edge capacity reductions the interdictor can make to the network is bounded. Solution methodology The interdictor’s problem is to determine the capacity reduction that has to be caused on various edges in the network and this is a combonatorially difﬁcult prob- lem to solve. As discussed earlier, even a simpler version of this problem is shown to be NP complete [13]. Therefore, a greedy heuristic that sequentially chooses the edges for interdiction is used for solving the problem. After each step, the heuristic solves the suppliers problem before choosing the next edge for interdiction. The implementation of this technique is fairly simple due to the relative ease of solving the suppliers problem. 4 The supplier agent in the network tries to maximize its proﬁt by directing re- sources to the demand centers. This proﬁt maximization problem can be formu- lated as a linear program ( P1). Here the objective function (proﬁt) is deﬁned as the difference between the revenue earned from the nodes and the transportation cost. The constraints are similar to that of the popular max-ﬂow problem. It includes the ﬂow conservation at nodes, edge capacity constraints and the limits on the maxi- mum demand that can be handled by the sink nodes. It has to be noted that the edge capacity constraints allow ﬂow though the edges in either direction subject to the limit on maximum ﬂow allowable. (P1) Max x;ypTxbTjyj s:t Flow balance constraint :Ayx=0 A: Incidence matrix Maximum demand constraint :xidi i2N Non negative demand constraint :xi0 i2Nnf15;16;20g Edge capacity constraints :wjyjwj j2E Though the problem necessitates that the ﬂows have to be integral, such a con- straint is not explicitly made. The reason being that even in the absence of the constraint, the solution to P1 would still remain integral as long as the maximum demand at the nodes and the edge capacities are integral. An intuitive proof for the claim given above can be made by adding a super sink to the graph. All demand nodes of the original graph has to be connected to this super sink by edges with capacity equal to the demand of the respective node. The supplier’s problem can now be reformulated for the modiﬁed graph 5 with all the demand constraints dropped, but with the capacity constraints for the new edges added. The constraints for this problem are exactly same as that of the max-ﬂow problem which is already proven to have an integral solution. Therefore, the original problem would also have an integral solution. Here it is assumed that the supplier agent has access to complete information of the available network and shows a rational behavior by trying to maximize its proﬁt according to the solution of P1. The interdictor now has to reduce or dis- able the capacities of individual edges in the graph. Accordingly, the supplier will reroute (or reduce) the ﬂows. The problem can be viewed as a Stackelberg game with the interdictor (leader) reducing and/or disabling the routes according to the total budget and the suppliers (follower) trying to maximize its proﬁt under new available graph. The interdictor’s problem can now be formulated as a min-max problem ( P2). Here the objective is to minimize the maximum proﬁt that can be achieved by the supplier agent. (P2) Min cMax x;ypTxbTjyj s:t Ayx=0 xidi i2N xi0 i2Nnf15;16;20g (wjcj)yjwjcj j2E wjcj0 cj0 Budget constraints : å jcjbudget Among constraints, in comparison to P1, the only addition in P2 is the limit on 6 maximum disruption that can be caused by the interdictor. The variable cjis used to denote the extend by which capacity of edge jis reduced by the interdictor. The huge solution space available for simultaneous disruptions limits the pos- sibility of an exhaustive search to ﬁnd the best solution to (P2), even for a small network. Prior to discussing a heuristic to solve this problem, we establish a spe- cial property of the system that signiﬁcantly decreases the search space and allows us to ﬁnd faster solutions. This has already been proved by Lim and Smith [8] based on the results of Dantzig [3]. Here we provide two propositions that further elucidates the claim. Proposition 1. The marginal damages caused by disruption is a non-increasing function of edge capacity w j;j2E. Proof. From Theorem IV-3 [5], the objective function of P1 is a concave and a piecewise afﬁne function of capacity, wj;j2E. Additionally, as the proﬁt never reduces with increase in capacity of an edge, the function is non-decreasing. Hence the marginal reduction in proﬁt is a non-increasing, piece wise constant function of edge capacity. Figure 2: Illustration for proposition 1. 7 Proposition 2. At most one edge is partially cut in the solution to P 2, i.e., given a disrupting budget l, in the optimal solution to P 2, amongst all edges with c >0, at most one edge has c <wj. Proof. Let us assume to the contrary, i.e., that when P2 is solved, there are two least edges iand jthat are partially disabled, i.e., 0 <cj<wjand 0 <ci<wi. Letliandljbe the Lagrange multiplies corresponding to the respective capacity constraints. Wlog, we may assume li>lj>0. Hence, it is possible to reduce the capacity of edge ibye;e>0 and increase the capacity of edge jbyewith no change in the budget. Since li>lj, this results in overall reduction in proﬁt. Since liandljare non-increasing functions of capacity (Proposition 1), this can be continued further till edge iis completely disrupted, i.e., ci=wior edge jis not disrupted at all, i.e., cj=0. This can be continued until there exists at most one edge with c>0 amongst the edges which are disrupted. Proposition 2 greatly reduces the search space for the given problem. Now the candidate solutions are the ones that have at most one edge partially disrupted (and all other edges chosen for disruption to be completely disabled). However, the total number of possible network disruptions are still large. In the following section, we propose a greedy algorithm that sequentially disables the edges in the network. A meta heuristic is introduced that make use of the dual variables of the edge capacity constraints. Initially, a deterministic edge selection strategy is discussed. This is followed by a variant of this algorithm that has a stochastic component included. Deterministic algorithm Letz1andz2be the dual variables corresponding to the edge capacity con- straints in P1. These are indicators of the importance of the corresponding con- straints to the LP. Since the ﬂow is considered non directional, z=z1+z2denotes 8 the limiters to the LP. The algorithm proceeds by the following : Problem P1 is executed and the corresponding dual variables ( z) are obtained. The edge with the highest dual variable is chosen for disruption and this is completely disrupted subject to availability of budget. With the updated capacities, P1 is exe- cuted and the dual variables are obtained. The process continues until the budget constraints are met. If capacity of a certain edge cannot be fully disabled, maxi- mum reduction is caused to the edge subject to budget constraint. The pseudo code is given below as Algorithm 1. Algorithm 1: wcur=0 ==wcur= sum of all current capacity reductions while wcur<Budget do Solve P1 Select edge fjz(f)is the highest8f2E Update w(f)as max(0, wcur- Budget) and wcurappropriately end while The disruption strategy discussed above need not be optimal as the dual vari- ables indicates the best edge only for an e-cut. For a complete edge disruption, the one chosen using the dual variables need not be the best. Even if the edge cho- sen turns out to be the best available, this need not remain valid as the disruption progresses. To overcome this shortcoming, we introduce a stochastic component in the sequential selection of edges for disruption. This is discussed in the next section. 9 Randomized algorithm Due to the shortcomings of the deterministic algorithm discussed earlier, we now introduce a stochastic component for the selection of edges for disruption. Instead of selecting edges strictly on the basis of the value of the dual variables, an edge is selected with a probability proportional to the value of its dual variable. A non zero probability (1- p) for picking an edge with its dual variable zero is also included. Choosing edges for disruption continues until the capacity constraints are met. This complete disruption process is repeated multiple times and the best solution amongst them is chosen. The pseudo code for the algorithm is given as Algorithm 2. Algorithm 2: wcur=0 ==wcur= sum of all current capacity reductions while wcur<Budget do Solve P1 Group the set of edges into L12z(f)6=0 and L22z(f) =0 Sort the edges fby the decreasing order of z(f)f2E Compute q(f):=z(f)=Sfz(f) Select randomly an edge ffrom set L1with a probability µqpor an edge f from set L2with a probability µp Update w(f)as max(0, wcur- Budget) and wcurappropriately end while 10 Results The performance of the deterministic and randomized algorithms are tested for the given network for different disruption capacities. The problem was modeled using the AIIMS platform and CPLEX solver was used. A comparison between the solution obtained by both the algorithms are shown in ﬁgure (3). /s53 /s49/s48 /s49/s53 /s50/s48 /s50/s53/s49/s48/s48/s48/s48/s50/s48/s48/s48/s48/s51/s48/s48/s48/s48/s52/s48/s48/s48/s48/s53/s48/s48/s48/s48/s54/s48/s48/s48/s48/s55/s48/s48/s48/s48/s56/s48/s48/s48/s48/s83/s117/s112/s112/s108/s105/s101/s114/s39/s115/s32/s80/s114/s111/s102/s105/s116 /s68/s105/s115/s114/s117/s112/s116/s105/s111/s110/s32/s66/s117/s100/s103/s101/s116/s32/s40/s37/s32/s111/s102/s32/s84/s111/s116/s97/s108/s32/s69/s100/s103/s101/s32/s67/s97/s112/s97/s99/s105/s116/s121/s41/s32/s68/s101/s116/s101/s114/s109/s105/s110/s105/s115/s116/s105/s99 /s32/s80/s114/s111/s98/s97/s98/s105/s108/s105/s115/s116/s105/s99 Figure 3: Comparison of deterministic and randomized algorithm for the test network The randomized algorithm takes about 34.4 seconds for 1000 iterations in an Intel (R) Core (TM) i5-4570 CPU @ 3.20 GHz system. Figure (4) shows the variation of the mean proﬁt generated by the supplier for different values of pa- rameter p. It should be noted here that the mean supplier proﬁt for the randomized algorithm is smaller than the deterministic one for values of pabove 0.9. The proposed method is computationally less intensive owing to its sequential nature with solution quality comparable with those obtained from other techniques such as Bender’s decomposition. The ﬁgures (5) and (6) shows the best cut for 15 % and 20 % budget. It has to be noted that the solution was obtained multiple times even in a single run of 1000 iterations. 11 /s48/s46/s48 /s48/s46/s50 /s48/s46/s52 /s48/s46/s54 /s48/s46/s56 /s49/s46/s48/s52/s48/s48/s48/s48/s54/s48/s48/s48/s48/s56/s48/s48/s48/s48/s83/s117/s112/s112/s108/s105/s101/s114/s39/s115/s32/s80/s114/s111/s102/s105/s116 /s80/s97/s114/s97/s109/s101/s116/s101/s114/s32/s118/s97/s108/s117/s101/s32/s45/s32/s112/s32/s83/s117/s112/s112/s108/s105/s101/s114/s39/s115/s32/s80/s114/s111/s102/s105/s116/s32/s40/s80/s114/s111/s98/s97/s98/s105/s108/s105/s115/s116/s105/s99/s41 /s32/s83/s117/s112/s112/s108/s105/s101/s114/s115/s32/s80/s114/s111/s102/s105/s116/s32/s40/s68/s101/s116/s101/s114/s109/s105/s110/s105/s115/s116/s105/s99/s41Figure 4: Variation with parameter p Figure 5: Best cut for 15 % budget Figure 6: Best cut for 20 % budget Conclusion In this work, a greedy sequential algorithm is proposed for a bilevel network interdiction problem. Initially, a heuristic based on the dual variables correspond- ing to the edge capacity constraints of the supplier’s problem is introduced which is later extended to include a stochastic selection of edges. The technique was tested on a standard network and promising results were obtained without much computational effort. 12