# jakobbossek/mcMST

Algorithms to solve the multi-criteria minimum spanning tree problem (mcMST) in R

Language: R

# mcMST: A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem

## Introduction

It is well known, that the single-objective spanning tree problem (MST) is solvable in polynomial time, e.g., by the Prim's algorithm. However, in real-world applications, e.g., in network design, often multiple conflicting objectives have to be considered simultaneously. The multi-criteria version of the MST is NP-hard. The mcMST package for the R programming language contains several methods for solving the multi-criteria spanning tree problem (mcMST).

Key features of the mcMST package are:

• A multi-objective version of Prim's algorithm.
• Evolutionary multi-objective algorithms (based on the Prüfer-encoding or direct edge list representation) with several mutation operators.
• A modular approach for benchmark problem generation (outsourced to R package grapherator.)

## Example

Here we first generate a bi-criteria graph problem with n = 25 nodes with grapherator. The first objective is the euclidean distance of node coordinates in the euclidean plane [0, 10] x [0, 10]. The second objective follows a normal distribution (N(5, 1.5)).

```library(grapherator) # install from github repo (not yet on CRAN)
set.seed(1)
g = graph(lower = 0, upper = 100)
g = addWeights(g, generator = addWeightsRandom, method = rnorm, mean = 5, sd = 1.5)
print(g)```

Next, we apply the multi-objective evolutionary algorithm proposed by Bossek & Grimme with population size `mu = 10` and number of offspring `lambda = 10` for `max.iter = 100` generations.

```library(ggplot2)
res = mcMSTEmoaBG(g, mu = 30L, max.iter = 300L)
ecr::plotFront(res\$pareto.front)```

See the package vignettes for more details.

## Installation Instructions

Install the CRAN release version via:

`install.packages("mcMST")`

If you are interested in trying out and playing around with the current development version use the devtools package and install directly from GitHub:

```install.packages("devtools", dependencies = TRUE)
devtools::install_github("jakobbossek/mcMST")```

## Contributing to mcMST

If you encounter problems using this software, e.g., bugs or insufficient/misleading documentation, or you simply have a question, feel free to open an issue in the issue tracker. In order to reproduce potential problems, please provide a minimal and reproducible code example.

Contributions to this software package are welcome via pull requests and will be merged at the sole discretion of the author.

## Publications

The following publications are strongly related to the package.

Bossek, J., & Grimme, C. (2017). A Pareto-Beneficial Sub-Tree Mutation for the Multi-Criteria Minimum Spanning Tree Problem. In Proceedings of the IEEE Symposium Series on Computational Intelligence, Honolulu, Hawai.

Bossek, J. (2017). mcMST: A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem. The Journal of Open Source Software, 2017.

## Related work

The following packages provide methods to solve the single-objective MST problem:

Several packages implement methods to solve multi-criteria optimization problems in general:

#### Project Statistics

 Sourcerank 4 Repository Size 755 KB Stars 1 Forks 1 Watchers 1 Open issues 3 Dependencies 16 Contributors 2 Tags 3 Created Jul 4, 2017 Last updated Jan 16, 2018 Last pushed Jan 4, 2018

#### Packages Referencing this Repo

##### mcMST
A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem
Latest release 1.0.1 - Updated - 1 stars

#### Recent Tags See all

 v1.0.1 September 18, 2017 v1.0.0 July 11, 2017 v1.0.0 July 11, 2017