A simple greedy heuristic for linear assignment interdiction

作者：Stozhkov Vladimir; Boginski Vladimir; Prokopyev Oleg A; Pasiliao Eduardo L

来源：Annals of Operations Research, 2017, 249(1-2): 39-53.

DOI：10.1007/s10479-016-2118-3

• Bilevel programming
• Assignment interdiction
• Linear assignment

We consider a bilevel extension of the classical linear assignment problem motivated by network interdiction applications. Specifically, given a bipartite graph with two different (namely, the leader's and the follower's) edge costs, the follower solves a linear assignment problem maximizing his/her own profit, whereas the leader is allowed to affect the follower's decisions by eliminating some of the vertices from the graph. The leader's objective is to minimize the total cost given by the cost of the interdiction actions plus the cost of the assignments made by the follower. The considered problem is strongly -hard. First, we formulate this problem as a linear mixed integer program (MIP), which can be solved by commercial MIP solvers. More importantly, we also describe a greedy-based construction heuristic, which provides (under some mild conditions) an optimal solution for the case, where the leader's and the follower's edge costs are equal to one. Finally, we present the results of our computational experiments comparing the proposed heuristic against an MIP solver.

• 出版日期2017-2