Computational comparisons of different formulations for the Bilevel Minimum Spanning Tree Problem

Martine Labbé 1 Miguel Pozo 2 Justo Puerto 2
1 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : Let be given a graph G = (V, E) 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 Bilevel Minimum Spanning Tree Problem (BMSTP) 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 mathematical formulations for the BMSTP 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 and we also provide reinforcements that together with a proper formulation are able to solve medium to big size instances random instances. We also test our models in instances already existing in the literature.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-01937013
Contributor : Martine Labbé <>
Submitted on : Tuesday, November 27, 2018 - 7:22:27 PM
Last modification on : Friday, April 19, 2019 - 4:55:21 PM

File

BMST_paper_181126_nohead.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01937013, version 1

Collections

Citation

Martine Labbé, Miguel Pozo, Justo Puerto. Computational comparisons of different formulations for the Bilevel Minimum Spanning Tree Problem. 2018. ⟨hal-01937013⟩

Share

Metrics

Record views

47

Files downloads

45