Benchmark problem generators and results for the multiobjective degree-constrained minimum spanning tree problem
Joshua D. Knowles, David Corne · 2001
Finding a minimum-weight spanning tree (MST) in a graph is a classic problem in operational research (OR) with important applications in network design. In this paper, we consider the degree-constrained multiobjective MST problem, which is NP-hard. We present several different parameterized problem generators for producing MST instances with different problem features, including any number of objectives, varying degrees of convexity and non-convexity in the Pareto front, and edge weight combinations that mislead greedy approaches. As well as being useful for the OR community, these generators are well-suited to provide problems to form part of a wider (evolutionary) multiobjective test problem suite, where constrained and NP-hard combinatorial problems are sometimes poorly represented. Fifteen instances are generated using the presented methods, and benchmark results on these instances for a multiobjective EA, AESSEA, are presented. These are compared with results from two different non-EA methods. All of our problem instances, generators, and solution sets will be made available for use by other researchers.