A Simple Greedy Heuristic For Linear Assignment Interdiction

Keywords

Assignment interdiction; Bilevel programming; Linear assignment

Abstract

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 NP-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.

Publication Date

2-1-2017

Publication Title

Annals of Operations Research

Volume

249

Issue

1-2

Number of Pages

39-53

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s10479-016-2118-3

Socpus ID

84975744791 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84975744791

This document is currently not available here.

Share

COinS