Computational comparisons of different formulations for the Stackelberg minimum spanning tree game

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.

Automated summary

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.