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

Summary

The single-objective minimum spanning tree (MST) problem is a combinatorial optimization problem known to be polynomial-time solvable, e.g., using the algorithm of Prim (Prim 1957). However, in real-world applications one is frequently confronted with multiple objectives which need to be minimized simultaneously. Since the objectives are usually conflicting, there is no single optimal solution to this problem. Instead the goal is the approximate the so-called Pareto-front, i.e., the set of nondominated solutions (see Deb (2001)).

The R (R Core Team 2017) package mcMST provides algorithms to approximate the Pareto-front of mcMST problems. Beside a multi-objective version of Prims algorithm (see, e.g., Knowles and Corne (2001)) the package offers evolutionary multi-objective algorithms (EMOAs), e.g., an Prüfer-encoding (Prüfer 1918) based EMOA as proposed by Zhou and Gen (1999) and an EMOA based on direct encoding and a Pareto-beneficial subtree mutation operator (Bossek and Grimme 2017). Further, a simple and generic enumeration algorithm is included, which is useful to compute the exact front of graph problems (not limited to mcMST) of small instance size by exhaustive enumeration. This is particularly useful to investigate properties of Pareto-optimal solutions.

Additionally, a modular toolbox to generate multi-objective benchmark graph problems is included in the mcMST package. This allows for easy generation of diverse benchmark sets.

References

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

Deb, K. 2001. Multi-Objective Optimization Using Evolutionary Algorithms. New York, NY, USA: John Wiley & Sons, Inc.

Knowles, J. D., and D. W. Corne. 2001. “A Comparison of Encodings and Algorithms for Multiobjective Minimum Spanning Tree Problems.” In Proceedings of the 2001 Congress on Evolutionary Computation (Ieee Cat. No.01th8546), 1:544–51 vol. 1. doi:10.1109/CEC.2001.934439.

Prim, R. C. 1957. “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36 (6). Blackwell Publishing Ltd: 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.

Prüfer, H. 1918. “Neuer Beweis eines Satzes über Permutationen.” Arch. Math. Phys. 27: 742–44.

R Core Team. 2017. R: A Language and Environment for Statistical Computing. Vienna, Austria: R Foundation for Statistical Computing. https://www.R-project.org/.

Zhou, G., and M. Gen. 1999. “Genetic Algorithm Approach on Multi-Criteria Minimum Spanning Tree Problem.” European Journal of Operational Research 114 (1): 141–52. doi:https://doi.org/10.1016/S0377-2217(98)00016-2.