Volume 11, Issue 1 (5-2025)
mmr 2025, 11(1): 99-120 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Tayyebi J, Niksirat M. Minimum spanning tree interdiction problem considering follower strategy stability. mmr 2025; 11 (1) :99-120
URL: http://mmr.khu.ac.ir/article-1-3416-en.html
URL: http://mmr.khu.ac.ir/article-1-3416-en.html
1- Birjand University of Technology
2- Birjand University of Technology ,niksirat@birjandut.ac.ir
2- Birjand University of Technology ,
Abstract: (31 Views)
Introduction: This paper examines a combinatorial optimization interdiction problem, called minimum spanning tree interdiction. From the point of view of game theory, this problem involves two players with different goals. The first player, called the follower, seeks to find a minimum spanning tree. On the other hand, the other player, who is called the leader, increases the cost of arcs, taking into account the budget and the bound constraints, which will make the value of the follower's objective function worse as much as possible, with the hope that the follower will stop doing more. In this article, a special case of the problem is considered in which the initial optimal tree remains optimal even with the change of weights. This assumption guarantees that the leader can be sure that the follower has no motivation to change his strategy, because a better strategy is not available.
Material and Methods: In order to efficiently solve this problem with linear costs, a new model is proposed, which includes a large number of constraints. For this reason, a solution approach based on the row (constraint) generation method is proposed for the problem. Then a numerical example and calculation results on random samples are presented to evaluate the performance of this method.
Results and discussion: The proposed model addresses this problem by utilizing a row generation approach to enhance solving efficiency. Computational results demonstrate its acceptable performance under various conditions, highlighting its potential for practical applications. The computational results indicate that the proposed algorithm computes the optimal solution to the problem within a finite number of iterations and a reasonable execution time.
Material and Methods: In order to efficiently solve this problem with linear costs, a new model is proposed, which includes a large number of constraints. For this reason, a solution approach based on the row (constraint) generation method is proposed for the problem. Then a numerical example and calculation results on random samples are presented to evaluate the performance of this method.
Results and discussion: The proposed model addresses this problem by utilizing a row generation approach to enhance solving efficiency. Computational results demonstrate its acceptable performance under various conditions, highlighting its potential for practical applications. The computational results indicate that the proposed algorithm computes the optimal solution to the problem within a finite number of iterations and a reasonable execution time.
Type of Study: S |
Subject:
Network Flows- Operation Reseach
Received: 2024/08/27 | Revised: 2025/10/6 | Accepted: 2025/07/9 | Published: 2025/05/31 | ePublished: 2025/05/31
Received: 2024/08/27 | Revised: 2025/10/6 | Accepted: 2025/07/9 | Published: 2025/05/31 | ePublished: 2025/05/31
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
