|
...decrease follower's profit function. When the partial destruction an arc is allowed, we refer to this action as continuous interdiction; otherwise, we call it discrete interdiction. We are particularly concerned with a multicommodity network flow interdiction problem in which revenue is generated by the successful shipment of commodities, and costs are incurred due to arc-flow expenses (see Wood (1993) for example). In this problem, the follower makes a profit by delivering multiple commodities to certain destinations. On the other hand, the leader attempts to minimize the follower's profit by destroying arcs, subject to a budget limitation on the maximum (weighted) number of arcs that can be interdicted. We consider both discrete and continuous interdiction actions in this paper.
The network interdiction problem has been studied for more than four decades with broad applicability to military and homeland security operations. Without considering interdiction costs, Wollmer (1964) proposed an algorithm that discretely interdicts a prescribed number of arcs in a network in order to minimize the follower's maximal flow. Introducing interdiction costs for a planar graph, McMasters and Mustin (1970) generalized this approach to solve a typical military operational problem, in which a daily air strike is planned for interdicting an enemy's supply lines. For a similar situation in which no assumption of graph planarity is made, Ghare et al. (1971) proposed a branch-and-bound method. This problem was further studied by Wood (1993), who provided an integer programming formulation for a discrete interdiction problem. This work also contributed an extension of the model to allow for continuous interdiction, multiple sources and sinks, undirected networks, multiple interdiction resources, and multiple commodities. In particular, the continuous interdiction algorithm exploits the fact that dual variables must be binary valued at optimal dual-extreme-point solutions in the context of maximum flows. Since the problem studied in this paper lacks this binary dual-extreme-point structure, we must explore a different approach.
Fulkerson and Harding (1977) considered maximizing the shortest source-sink path in the presence of arc extension costs that have an equivalent context as interdiction costs. They provided a minimum-cost network flow formulation for this problem that can be solved via network optimization procedures. Instead of restricting the leader's budget, Golden (1978) introduced a length constraint for the shortest path while minimizing the total interdiction cost. He presented a minimum-cost network flow problem formulation for this problem. More recently, Israeli and Wood (2002) proposed two decomposition algorithms for solving a discrete interdiction case using so-called super-valid inequalities and set covering master problems.
Washburn and Wood (1995) considered the case in which the follower selects a single path to traverse, while the leader tries to locate a single sentry device on an arc in order to maximize the probability of detecting the follower's travel. Starting with a two-person zero-sum game formulation, they provided a corresponding maximum flow network problem and an optimal solution recovery scheme for the original game problem. The deterministic interdiction problem of Wood (1993) was extended to a stochastic network interdiction problem by Cormican et al. (1998), in which the leader minimizes the expected maximum flow of the network under uncertain interdiction success and arc capacities. They provided a two-stage stochastic integer program, and proposed a sequential approximation algorithm for its solution.
Aside from military and homeland security applications, network interdiction models have been used in other areas. Assimakopoulos (1987) presented an interdiction model for preventing hospital infections, in which the node set consists of sources, carriers, and entry points of infecting organisms. Anandalingam and Apprey (1991) considered conflict resolution problems that allow multiple followers to react to the leader's decision simultaneously and hierarchically as leaders and followers. They proposed penalty function approaches for solving these problems and presented an application to a water conflict resolution problem for a river that runs through two countries. In this case study, the United Nations plays a role as the leader (or arbitrator) and two countries act as the followers.
Linear multicommodity flow models are well known and have been widely used in practice due to their broad applicability. Assad (1978) and Kennington (1978) provided early comprehensive surveys on the solution of multicommodity flow problems and their variants. Some important approaches to solving large-scale versions of these problems include dual-ascent (Barnhart, 1993) and primal-dual algorithms (Barnhart and Sheffi, 1993), decomposition strategies (Mamer and McBride, 2000) and basis partitioning approaches (McBride, 1985a). The use of interior-point algorithms for solving multicommodity flow problems is addressed in McBride (1985b). Whereas most network interdiction studies are concerned with a single commodity network flow, multicommodity flows are more appropriate in certain situations, as noted in Wood (1993). It is easy to construct scenarios in which an enemy is transporting multiple items through a network, but the best practical use of this research might arise in cases where the follower is trying to ascertain the worst-case scenario that can possibly befall the network under consideration. For instance, multicommodity flow networks are prevalent in airline operations, supply chain networks, and telecommunications applications, and the survivability of these networks is often of paramount importance. One can evaluate the robustness of a multicommodity network by modeling an intelligent leader as a malicious enemy using the techniques developed herein.
In this paper, we consider the case in which the leader minimizes the follower's profit in a multicommodity flow network. While the approach of Wood (1993) forms the basis for our line of investigation, we expand on this research in the specific context of multicommodity flow networks, and provide insights into methods for solving such problems in both discrete and continuous interdiction scenarios.
The remainder of this paper is organized as follows. In Section 2, a formal description of this problem is presented. We first discuss the discrete interdiction case in Section 3 and propose two formulations for its solution. One formulation is an extension of the discussion in Wood (1993) that provided a linearization approach for minimizing the follower's maximum flow, whereas the second introduces a penalty to the follower's objective function that eliminates the leader's variables from the follower's constraints. In Section 4, we consider the continuous interdiction case and present two approaches for optimally solving this problem. One is based on the bilinear programming formulation that can be solved via various solution techniques in the literature, and the other method exploits a tailored partitioning technique that permits an implicit enumeration algorithm. We also propose a heuristic method for solving relatively large-scale problems that are intractable via an exact solution approach. In Section 5, we display detailed computational results for the proposed methods, and we conclude our study in Section 6.
2. Problem description
In this section, we formally describe the Multicommodity Flow Network Interdiction Problem (MFNIP). Consider a directed graph G(N, A), where N and A denote index sets of nodes and arcs, respectively. Suppose that the follower has a set K of commodities to deliver from their supply nodes to their demand nodes. Each commodity k [member of] K can have multiple supply nodes, whose set is denoted by [S.sup.k]. Likewise, let [D.sup.k] be the set of demand nodes for commodity k. The maximum supply at node l [member of] [S.sup.k] is [S.sub.l.sup.k], and the maximum demand at node l [member of] [D.sup.k] is denoted by [d.sub.l.sup.k]. For simplicity, we can create dummy arcs with no flow costs or rewards, and very large interdiction costs. This set of arcs allows us to claim that all supplies must be exhausted and all demands must be supplied.
We use a single index h [member of] A to index our arcs. Each arc has a finite flow capacity [u.sub.h] > 0. The follower receives rewards when delivering commodities to designated destinations. However, conveying commodities through an arc incurs a flow cost. For a compact presentation of these rewards and flow costs, we will use a unified value [r.sub.h.sup.k]. All values [r.sub.h.sup.k] for each h [member of] A and k [member of] K include a (negative) flow cost component when one unit of commodity k is conveyed through this arc. If the to-node of h [member of] A is a demand node of commodity k, a positive reward is added to the flow cost when one unit flow of commodity k is made. Finally, note that a positive flow of commodity k on an arc h whose from-node is one of destinations of commodity k implies that the follower uses this destination as a transhipment node to deliver commodity k to another demand node. Hence, we take back the reward that was gained when this commodity was delivered to the from-node by subtracting this reward from [r.sub.h.sup.k].
The leader destroys arcs...
NOTE: All illustrations and photos
have been removed from this article.
More articles from IIE Transactions
Rebate, returns and price protection policies in channel coordination., February 01, 2007
Hierarchical cross-training in work-in-process-constrained systems.(Au..., February 01, 2007
Risk, risk aversion and the optimal time to produce.(Author abstract), February 01, 2007
Benefits of considering inventory in service parts logistics network d..., February 01, 2007
Strategic network design for multi-zone truckload shipments.(Author ab..., February 01, 2007
Looking for additional articles?
Search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication
name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company
analysis or best practices in managing your organization,
Goliath can help you meet your business needs.
Our extensive business information databases empower business
professionals with both the breadth and depth of credible,
authoritative information they need to support their business
goals. Whether it be strategic planning, sales prospecting,
company research or defining management best practices -
Goliath is your leading source for accurate information.
|
