momst is the reference R implementation of the Multi-Criteria Minimum Spanning Tree (mc-MST) solver introduced in:
Parraga-Alava, J., Inostroza-Ponta, M., and Dorn, M. (2017). Using local search strategies to improve the performance of NSGA-II for the Multi-Criteria Minimum Spanning Tree problem. In 2017 IEEE Congress on Evolutionary Computation (CEC), pp. 1818 to 1825. IEEE. doi:10.1109/CEC.2017.7969432
The solver couples NSGA-II with three optional Pareto local search operators and a Prufer sequence chromosome representation. By Cayley’s theorem, every random Prufer sequence decodes to a valid spanning tree, so the genetic operators never need a repair step.
Variants
| Variant | Local search | Reference algorithm |
|---|---|---|
"base" |
None (pure NSGA-II) | Reference baseline. |
"PR" |
Path Relinking | Section III.C of the CEC paper. |
"PLS" |
Pareto Local Search | Section III.A of the CEC paper. |
"TS" |
Tabu Search | Section III.B of the CEC paper. |
Installation
# install.packages("remotes")
remotes::install_github("jorgeklz/momst", build_vignettes = TRUE)Quick start
library(momst)
# Run NSGA-II on a 10 node graph with two random objectives
res <- run_momst(
n = 10,
num_obj = 2,
variant = "PLS", # NSGA-II + Pareto Local Search
iterations = 3,
pop_size = 30,
max_generations = 40,
verbose = FALSE,
seed = 2026
)
# Inspect the global Pareto front
head(res$global_pareto[, c("objective_1", "objective_2")])
# Plot it
plot_pareto_front(res)
# Plot the best-compromise spanning tree (requires the 'igraph' package)
plot_best_tree(res, n = 10)Vignettes
browseVignettes("momst")The package ships two vignettes:
- Getting Started with momst: minimal workflow, two and three objective examples, reproducibility notes.
- Comparing the Four MO-MST Variants: side by side comparison of the four solver variants on the same instance, with combined Pareto front and runtime analysis.
Citation
citation("momst")If you use momst in academic work, please cite the original CEC 2017 paper indicated above and the R package itself.
Issues and contributions
Please report bugs and feature requests through the GitHub issue tracker: https://github.com/jorgeklz/momst/issues.