Search

In this study, we consider a class of linear matroid interdiction problems, where the feasible sets for the upper-level decision-maker (referred to as a leader) and the lower-level decision-maker (referred to as a follower) are induced by two distinct partition matroids with a common weighted ground set. Unlike classical network interdiction models where the leader is subject to a single budget constraint, in our setting, both the leader and the follower are subject to several independent capacity constraints and engage in a zero-sum game. While the problem of finding a maximum weight independent set in a partition matroid is known to be polynomially solvable, we prove that the considered bilevel problem is $NP$-hard even when the weights of ground elements are all binary. On a positive note, it is revealed that, if the number of capacity constraints is fixed for either the leader or the follower, then the considered class of bilevel problems admits several polynomial-time solution schemes. Specifically, these schemes are based on a single-level dual reformulation, a dynamic programming-based approach, and a 2-flip local search algorithm for the leader.

In this note we study multiple-ratio fractional 0--1 programs, a broad class of NP-hard combinatorial optimization problems. In particular, under some relatively mild assumptions we provide a complete characterization of the conditions, which ensure that a single-ratio function is submodular. Then we illustrate our theoretical results with the assortment optimization and facility location problems, and discuss practical situations that guarantee submodularity in the considered application settings. In such cases, near-optimal solutions for multiple-ratio fractional 0--1 programs can be found via simple greedy algorithms.

In this study we consider the shortest path problem, where the arc costs are subject to distributional uncertainty. Basically, the decision-maker attempts to minimize her worst-case expected loss over an ambiguity set (or a family) of candidate distributions that are consistent with the decision-maker's initial information. The ambiguity set is formed by all distributions that satisfy prescribed linear first-order moment constraints with respect to subsets of arcs and individual probability constraints with respect to particular arcs. Under some additional assumptions the resulting distributionally robust shortest path problem (DRSPP) admits equivalent robust and mixed-integer programming (MIP) reformulations. The robust reformulation is shown to be $NP$-hard, whereas the problem without the first-order moment constraints is proved to be polynomially solvable. We perform numerical experiments to illustrate the advantages of the considered approach; we also demonstrate that the MIP reformulation of DRSPP can be solved effectively using off-the-shelf solvers., Comment: 37 pages

We consider a class of sequential network interdiction problem settings where the interdictor has incomplete initial information about the network while the evader has complete knowledge of the network including its structure and arc costs. In each decision epoch, the interdictor can block (for the duration of the epoch) at most $k$ arcs known to him/her. By observing the evader's actions, the interdictor learns about the network structure and costs and thus, can adjust his/her actions in subsequent decision epochs. It is known from the literature that if the evader is greedy (i.e., the shortest available path is used in each decision epoch), then under some assumptions the greedy interdiction policies that block $k$-most vital arcs in each epoch are efficient and have a finite regret. In this paper, we consider the evader's perspective and explore deterministic "strategic" evasion policies under the assumption that the interdictor is greedy. We first study the theoretical computational complexity of the evader's problem. Then we derive basic constructive properties of optimal evasion policies for two decision epochs when the interdictor has no initial information about the network structure. These properties are then exploited for the design of a heuristic algorithm for a strategic evader in a general setting with an arbitrary time horizon and any initial information available to the interdictor. Our computational experiments demonstrate that the proposed heuristic outperforms the greedy evasion policy on several classes of synthetic network instances under either perfect or noisy information feedback. Finally, some interesting insights from our theoretical and computational results conclude the paper.