Improved x-space Algorithm for Min-Max Bilevel Integer Programming with an Application to Misinformation Spread in Social Networks

• Published in: arXiv.org 2021-05
• Main Authors: Tanınmış, Kübra, Aras, Necati, İ Kuban Altınel
• Format: Article
• Language: English
• Subjects: Algorithms; False information; Integer programming; Knapsack problem; Lower bounds; Social networks
• ISSN: 2331-8422
• DOI: 10.48550/arxiv.2005.08039

In this work we propose an improvement of the \(x\)-space algorithm developed for solving a class of min--max bilevel optimization problems (Tang Y., Richard J.P.P., Smith J.C. (2016), A class of algorithms for mixed-integer bilevel min--max optimization. Journal of Global Optimization, 66(2), 225--262). In this setting, the leader of the upper level problem aims at restricting the follower's decisions by minimizing an objective function, which the follower intends to maximize in the lower level problem by making decisions still available to her. The \(x\)-space algorithm solves upper and lower bound problems consecutively until convergence, and requires the dualization of an approximation of the follower's problem in formulating the lower bound problem. We first reformulate the lower bound problem using the properties of an optimal solution to the original formulation, which makes the dualization step unnecessary. The reformulation makes possible the integration of a greedy covering heuristic into the solution scheme, which results in a considerable increase in the efficiency. The new algorithm referred to as the improved \(x\)-space algorithm is implemented and applied to a recent min--max bilevel optimization problem that arises in the context of reducing the misinformation spread in social networks. It is also assessed on the benchmark instances of two other bilevel problems: zero-one knapsack problem with interdiction and maximum clique problem with interdiction. Numerical results indicate that the performance of the new algorithm is superior to that of the original algorithm, and also compares favorably with a recent algorithm developed for mixed-integer bilevel linear programs.