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

• Published date: 01 January 2021
• DOI: http://doi.org/10.1111/itor.12680
• Date: 01 January 2021

Intl. Trans. in Op. Res. 28 (2021) 48–69

DOI: 10.1111/itor.12680

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Computational comparisons of different formulations for the

Stackelberg minimum spanning tree game

Martine Labb´

ea,b,MiguelA.Pozo

c,∗and Justo Puertoc

aFaculty of Sciences, Computer Science Department, Universit´

e Libre de Bruxelles, Brussels, Belgium

bINOCS Team, INRIA, Lille, France

cFacultad de Matem´

aticas, Department of Statistics and Operational Research, University of Seville, Sevilla, Spain

E-mail: mlabbe@ulb.ac.be [Labb´

e]; miguelpozo@us.es [Pozo]; puerto@us.es[Puerto]

Received 26 November2018; received in revised form 14 May 2019; accepted 14 May 2019

Abstract

Let G=(V,E)be a given graph whose edge set is partitioned into a set Rof red edges and a set Bof 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 (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 problemand 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.

Keywords:minimum spanning tree; bilevel optimization; Stackelberg game

1. Introduction

Let Gbe a given graph whose edge set is partitioned into a set of red edges and a set 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) consists in 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 (MST) of the

resulting graph is maximized.

The StackMST can be seen as a bilevel optimization problemwhere the second level is a minimum

spanning tree problem (MSTP) and where objective functions are bilinear at both levels. Optimiza-

tion problems related to spanning trees, or simply spanning tree problems, are among the core

problems in combinatorial optimization.On the one hand, the combinatorial object that represents

∗Corresponding author.

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

M. Labb´

e et al. / Intl. Trans. in Op. Res. 28 (2021) 48–69 49

spanning trees has important structural properties (see, e.g., Anazawa, 2001). On the other hand,

from a practitioner’s point of view,spanning trees are found in a wide range of applications (see,e.g.,

Cl´

ımaco & Pascoal, 2012) in many fields (e.g., computer networks design, telecommunications net-

works,and transportation). Furthermore, they often appear as subproblems of other more complex

optimization problems (see, e.g., Consoli et al., 2017).

In game theory, a bilevel optimization problem is known as Stackelberg game (von Stackelberg,

1934) and it consists in a game between a leader and a followerwho play sequentially. Those players

compete with each other: the leader makes the first move, and then the follower reacts optimally

to the leader’s action. This kind of hierarchical game is asymmetric in nature, so that the leader

and the follower cannot be interchanged. The leader knows ex ante that the follower observes

his/her actions before responding in an optimal manner. Therefore, to optimize his/her objective,

the leader anticipates the optimal response of the follower. In this setting, the leader’s optimiza-

tion problem contains a nested optimization task that corresponds to the follower’s optimization

problem.

An example of the StackMST is the following. Suppose a telecommunications company (TC)

owns several connections (blue edges) between different nodes of a network. A new provider wants

to enter into the market building a network that connects all nodes at minimum cost. It may use

the connections of TC or those of its competitors (red edges). The target is to maximize the profit

of the connections that TC could sell to the new provider.

Several papers have been published covering the problem in which the second level consists in

choosing shortest paths between pairs of origins and destinations. The problem was first introduced

by Labb´

e et al. (1998). Roch et al. (2005) show that the problem is strongly NP-hard even when the

second level consists in one single shortest path. More referencesregarding that bilevel optimization

problem can be found in the surveys of van Hoesel (2008) and Labb´

e and Violin (2013).

Gassner (2002) studied a discrete variant of the StackMST where a partition of the set of edges

into leader- and follower-edges is given. The leader’s action is to choose a subset of his edges,

whereas the follower’s reaction is to build up a spanning tree that includes the edges chosen by the

leader. Hence, the leader’s and follower’s decision vectors are discrete.

Cardinal et al. (2011) proved the APX-hardness of the StackMST even when the number of red

edge costs is 2 and gavean approximation algorithm with guaranteed worst-case performance.They

also give an integer programming formulation for the problem and study its linear programming

relaxation. Further, Cardinal et al. (2013) proved that the problem remains NP-hard even if Gis

planar, while it can be solved in polynomial time provided that Ghas bounded treewidth.

Bil`

o et al. (2015) pointed out that the hardness in finding an optimal solution for the StackMST

lies in the selection of the optimal set of blue edges that will be purchased by the follower. Since

once a set of blue edges is part of the final MST, their best possible pricing can be computed in

polynomial time, as shown in Cardinal et al. (2011).

Morais et al. (2016) introduced a reformulation and a Branch-and-Cut-and-Price algorithm for

StackMST.The reformulation was obtained after applying Karush-Kuhn-Tucker (KKT) optimality

conditions to a StackMST noncompact bilevel linear programming formulation and was strength-

ened with a partial rank-1 RLT and with valid inequalities coming from Cardinal et al. (2011).

They also implemented a Branch-and-Cut algorithm for an extended formulation derived from

that in Cardinal et al. (2011), and a preliminary computational study comparing both methods

was presen ted.

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation of OperationalResearch Societies