A. Torrejón Valenzuela, M. Labbé, M. A. Pozo Montaño, J. Puerto Albandoz
In a given network, connections between points can be owned and thus sold. This situation opens up a wide range of combinatorial problems. Let G = (V, E) be a given graph whose edge set is partitioned into a set R of red edges and a set B of blue edges, and assume that red edges are weighted and contain a spanning tree of G. Then, the Stackelberg Minimum Spanning Tree Game (StackMST) is that of pricing 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 talk we present different enhancements to the state-of-the-art 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.
Keywords: Combinatorial Optimization, Minimum Spanning Tree, Bilevel optimization, Stackelberg game
Scheduled
GT12.GELOCA2 Invited Session
November 10, 2023 4:00 PM
CC2: Conference Room