Journal
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH
Volume 28, Issue 1, Pages 48-69Publisher
WILEY
DOI: 10.1111/itor.12680
Keywords
minimum spanning tree; bilevel optimization; Stackelberg game
Ask authors/readers for more resources
The paper presents new mathematical programming formulations for the StackMST game based on the properties of the minimum spanning tree problem and bilevel optimization. Theoretical and empirical comparisons are made with the new formulations on random instances of 20-70 nodes, as well as on instances in the literature where the models outperform previous results.
LetG=(V,E)be a given graph whose edge set is partitioned into a setRof red edges and a setBof blue edges, and assume that red edges are weighted and contain a spanning tree ofG. Then, the Stackelberg minimum spanning tree game (StackMST) is that of pricing (i.e., weighting) the blue edges in such a way that the total weight of the blue edges selected in a minimum spanning tree of the resulting graph is maximized. In this paper, we present different new mathematical programming formulations for the StackMST based on the properties of the minimum spanning tree problem and the bilevel optimization. We establish a theoretical and empirical comparison between these new formulations that are able to solve random instances of 20-70 nodes. We also test our models on instances in the literature, outperforming previous results.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available