momst

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)

Interactive web app

The package ships a Shiny explorer that wraps run_momst(). It lets you generate or upload an instance, run and compare the four variants, browse and download the Pareto front, and draw any spanning tree on the front.

# install.packages(c("shiny", "bslib"))
momst::run_app()

A browser version runs at https://jorgeklz.github.io/momst/app/ with no installation. It is a JavaScript port of the solver, including R's random number generator, so with the same instance, parameters and seed it returns the same Pareto front as run_momst(). The pkgdown workflow checks this against the R package before every deployment (webapp/test/check-against-r.js).

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.

License

GPL (>= 3). See LICENSE for details.