{ "_id": "6a3a6b03ef5099f0c5f1330a", "Package": "momst", "Type": "Package", "Title": "Multi-Objective Minimum Spanning Tree via NSGA-II with Local\nSearch", "Version": "0.1.1", "Authors@R": "c(\nperson(given = \"Jorge A.\",\nfamily = \"Parraga-Alava\",\nemail = \"jorge.parraga@utm.edu.ec\",\nrole = c(\"aut\", \"cre\"),\ncomment = c(ORCID = \"0000-0001-8558-9122\")))", "Description": "Solves the Multi-Criteria Minimum Spanning Tree (mc-MST)\nproblem on complete weighted graphs by combining the\nNon-dominated Sorting Genetic Algorithm II (NSGA-II) with\noptional Pareto local search operators. Chromosomes are\nrepresented as Prufer sequences so that every random individual\ndecodes to a valid spanning tree (Cayley's theorem), avoiding\nrepair operators. Four solver variants are provided: pure\nNSGA-II (\"base\"), Path Relinking (\"PR\"), Pareto Local Search\n(\"PLS\"), and Tabu Search (\"TS\"). The package supports 2 and 3\nobjective formulations and provides convenience functions to\nplot Pareto fronts and best-compromise spanning trees. This\npackage is the reference implementation of the method described\nin Parraga-Alava, Inostroza-Ponta and Dorn (2017)\n.", "License": "GPL (>= 3)", "URL": "https://github.com/jorgeklz/momst,\nhttps://jorgeklz.github.io/momst/", "BugReports": "https://github.com/jorgeklz/momst/issues", "Encoding": "UTF-8", "RoxygenNote": "7.3.2", "VignetteBuilder": "knitr", "Config/testthat/edition": "3", "Repository": "https://jorgeklz.r-universe.dev", "Date/Publication": "2026-06-02 22:06:44 UTC", "RemoteUrl": "https://github.com/jorgeklz/momst", "RemoteRef": "HEAD", "RemoteSha": "c88b27ba19c7efe7f16d2135e7f33790770479e9", "NeedsCompilation": "no", "Packaged": { "Date": "2026-06-23 11:13:36 UTC", "User": "root" }, "Author": "Jorge A. Parraga-Alava [aut, cre] (ORCID:\n)", "Maintainer": "Jorge A. Parraga-Alava ", "MD5sum": "163fd055b4b7ae371ddfd8b54736197d", "_user": "jorgeklz", "_type": "src", "_file": "momst_0.1.1.tar.gz", "_fileid": "4301b36c61b114b04570351a7828a9814a0755941016782c426f17812e273bfc", "_filesize": 1236887, "_sha256": "4301b36c61b114b04570351a7828a9814a0755941016782c426f17812e273bfc", "_created": "2026-06-23T11:13:36.000Z", "_published": "2026-06-23T11:16:19.042Z", "_distro": "noble", "_jobs": [ { "job": 82940734469, "time": 121, "config": "linux-devel-x86_64", "r": "4.7.0", "check": "NOTE", "artifact": "7819182338" }, { "job": 82940734453, "time": 113, "config": "linux-release-x86_64", "r": "4.6.0", "check": "NOTE", "artifact": "7819179414" }, { "job": 82940734416, "time": 91, "config": "macos-oldrel-arm64", "r": "4.5.3", "check": "NOTE", "artifact": "7819171550" }, { "job": 82940734439, "time": 112, "config": "macos-release-arm64", "r": "4.6.0", "check": "NOTE", "artifact": "7819179658" }, { "job": 82940014844, "time": 236, "config": "source", "r": "4.6.0", "check": "OK", "artifact": "7819136515" }, { "job": 82940734438, "time": 97, "config": "wasm-release", "r": "4.6.0", "check": "OK", "artifact": "7819173694" }, { "job": 82940734448, "time": 77, "config": "windows-devel", "r": "4.7.0", "check": "NOTE", "artifact": "7819166479" }, { "job": 82940734483, "time": 73, "config": "windows-oldrel", "r": "4.5.3", "check": "NOTE", "artifact": "7819165111" }, { "job": 82940734470, "time": 63, "config": "windows-release", "r": "4.6.0", "check": "NOTE", "artifact": "7819161306" } ], "_buildurl": "https://github.com/r-universe/jorgeklz/actions/runs/28021883168", "_status": "success", "_host": "GitHub-Actions", "_upstream": "https://github.com/jorgeklz/momst", "_commit": { "id": "c88b27ba19c7efe7f16d2135e7f33790770479e9", "author": "Jorge <35182364+jorgeklz@users.noreply.github.com>", "committer": "GitHub ", "message": "Update README.md", "time": 1780438004 }, "_maintainer": { "name": "Jorge A. Parraga-Alava", "email": "jorge.parraga@utm.edu.ec", "login": "jorgeparraga-arch", "orcid": "0000-0001-8558-9122", "description": "University professor", "uuid": 258619827 }, "_registered": true, "_dependencies": [ { "package": "R", "version": ">= 4.0", "role": "Depends" }, { "package": "stats", "role": "Imports" }, { "package": "utils", "role": "Imports" }, { "package": "graphics", "role": "Imports" }, { "package": "igraph", "role": "Suggests" }, { "package": "knitr", "role": "Suggests" }, { "package": "rmarkdown", "role": "Suggests" }, { "package": "testthat", "version": ">= 3.0.0", "role": "Suggests" } ], "_owner": "jorgeklz", "_selfowned": true, "_usedby": 0, "_updates": [ { "week": "2026-23", "n": 5 } ], "_tags": [ { "name": "v0.1.1", "date": "2026-06-02" } ], "_stars": 0, "_contributors": [ { "user": "jorgeparraga-arch", "count": 4, "uuid": 258619827 }, { "user": "jorgeklz", "count": 1, "uuid": 35182364 } ], "_userbio": { "uuid": 35182364, "type": "user", "name": "Jorge", "followers": 3 }, "_downloads": { "count": 0, "source": "https://cranlogs.r-pkg.org/downloads/total/last-month/momst" }, "_devurl": "https://github.com/jorgeklz/momst", "_pkgdown": "https://jorgeklz.github.io/momst/", "_searchresults": 0, "_rbuild": "4.6.0", "_assets": [ "extra/citation.cff", "extra/citation.html", "extra/citation.json", "extra/citation.txt", "extra/contents.json", "extra/momst.html", "extra/NEWS.html", "extra/NEWS.txt", "extra/readme.html", "extra/readme.md", "LICENSE", "manual.pdf" ], "_homeurl": "https://github.com/jorgeklz/momst", "_realowner": "jorgeklz", "_cranurl": true, "_releases": [ { "version": "0.1.1", "date": "2026-06-22" } ], "_exports": [ "apply_local_search", "build_weight_lookup", "compute_objectives", "decode_prufer", "generate_instance", "generate_prufer_population", "non_dominated_crowding", "pareto_local_search", "path_relinking", "plot_best_tree", "plot_pareto_front", "random_mutation", "run_momst", "tabu_search", "tournament_selection", "uniform_crossover" ], "_help": [ { "page": "momst-package", "title": "momst: Multi-Objective Minimum Spanning Tree via NSGA-II with Local Search", "topics": [ "momst-package", "momst" ] }, { "page": "apply_local_search", "title": "Apply the Configured Local-Search Variant", "topics": [ "apply_local_search" ] }, { "page": "build_weight_lookup", "title": "Pre-build Edge-Weight Lookup Matrices", "topics": [ "build_weight_lookup" ] }, { "page": "compute_objectives", "title": "Compute Multi-Objective Costs for a Population", "topics": [ "compute_objectives" ] }, { "page": "decode_prufer", "title": "Decode a Prufer Sequence to its Spanning Tree (Linear Time)", "topics": [ "decode_prufer" ] }, { "page": "generate_instance", "title": "Generate a Complete-Graph Instance for MO-MST", "topics": [ "generate_instance" ] }, { "page": "generate_prufer_population", "title": "Generate an Initial Prufer-Encoded Population", "topics": [ "generate_prufer_population" ] }, { "page": "non_dominated_crowding", "title": "Assign Pareto Rank and Crowding Distance", "topics": [ "non_dominated_crowding" ] }, { "page": "pareto_local_search", "title": "Pareto Local Search", "topics": [ "pareto_local_search" ] }, { "page": "path_relinking", "title": "Path Relinking on the Current Pareto Front", "topics": [ "path_relinking" ] }, { "page": "plot_best_tree", "title": "Plot the Best-Compromise Spanning Tree", "topics": [ "plot_best_tree" ] }, { "page": "plot_pareto_front", "title": "Plot a Pareto Front (2-objective case)", "topics": [ "plot_pareto_front" ] }, { "page": "random_mutation", "title": "Random Mutation on Prufer Sequences", "topics": [ "random_mutation" ] }, { "page": "run_momst", "title": "Run the MO-MST NSGA-II Solver", "topics": [ "run_momst" ] }, { "page": "tabu_search", "title": "Tabu Search on the Current Pareto Front", "topics": [ "tabu_search" ] }, { "page": "tournament_selection", "title": "Tournament Selection", "topics": [ "tournament_selection" ] }, { "page": "uniform_crossover", "title": "Uniform Crossover for Prufer Sequences", "topics": [ "uniform_crossover" ] } ], "_readme": "https://github.com/jorgeklz/momst/raw/HEAD/README.md", "_rundeps": [], "_vignettes": [ { "source": "momst-variants.Rmd", "filename": "momst-variants.html", "title": "Comparing the Four MO-MST Variants", "author": "Jorge A. Parraga-Alava", "engine": "knitr::rmarkdown", "headings": [ "Goal of this vignette", "Reference", "Shared experimental setup", "Run all four variants", "Inspecting the Pareto fronts numerically", "Visual comparison of the four fronts", "One panel per variant", "All variants superposed", "A unified \"ground truth\" front", "Runtime cost", "Picking a best-compromise tree per variant", "Three-objective example for every variant", "Summary" ], "created": "2026-06-02 15:49:14", "modified": "2026-06-02 15:49:14", "commits": 1 }, { "source": "getting-started.Rmd", "filename": "getting-started.html", "title": "Getting Started with momst", "author": "Jorge A. Parraga-Alava", "engine": "knitr::rmarkdown", "headings": [ "Overview", "Reference", "Installation", "A first end-to-end example", "Step 1. Generate a random bi-objective instance", "Step 2. Run the NSGA-II solver (base variant)", "Step 3. Inspect the global Pareto front", "Step 4. Plot the Pareto front", "Step 5. Decode and plot the best-compromise tree", "Working with three objectives", "Reproducibility", "Where to go next" ], "created": "2026-06-02 15:49:14", "modified": "2026-06-02 15:49:14", "commits": 1 } ], "_score": 4, "_indexed": true, "_nocasepkg": "momst", "_universes": [ "jorgeklz", "jorgeparraga-arch" ], "_binaries": [ { "r": "4.7.0", "os": "linux", "version": "0.1.1", "date": "2026-06-23T11:15:42.000Z", "distro": "noble", "commit": "c88b27ba19c7efe7f16d2135e7f33790770479e9", "fileid": "21b069a5cbd5e5cd5de5939e66b1722f0c75c2167621ffaf62b8adf59329dc7e", "status": "success", "check": "NOTE", "buildurl": "https://github.com/r-universe/jorgeklz/actions/runs/28021883168" }, { "r": "4.6.0", "os": "linux", "version": "0.1.1", "date": "2026-06-23T11:15:35.000Z", "distro": "noble", "commit": "c88b27ba19c7efe7f16d2135e7f33790770479e9", "fileid": "5e91343b6cecaf048ffcc914125ce84ae151903ba98d458af47bbf2b5408c24c", "status": "success", "check": "NOTE", "buildurl": "https://github.com/r-universe/jorgeklz/actions/runs/28021883168" }, { "r": "4.5.3", "os": "mac", "version": "0.1.1", "date": "2026-06-23T11:15:12.000Z", "commit": "c88b27ba19c7efe7f16d2135e7f33790770479e9", "fileid": "c07cffe0095a95a1c4aaf42a22b2189d372bf1eca4418e7ab585a275c07d7251", "status": "success", "check": "NOTE", "buildurl": "https://github.com/r-universe/jorgeklz/actions/runs/28021883168" }, { "r": "4.6.0", "os": "mac", "version": "0.1.1", "date": "2026-06-23T11:15:32.000Z", "commit": "c88b27ba19c7efe7f16d2135e7f33790770479e9", "fileid": "7e8606091ac3303fa1827e227c651843782c452e4e317043970c8c18722eda5f", "status": "success", "check": "NOTE", "buildurl": "https://github.com/r-universe/jorgeklz/actions/runs/28021883168" }, { "r": "4.6.0", "os": "wasm", "version": "0.1.1", "date": "2026-06-23T11:15:31.000Z", "commit": "c88b27ba19c7efe7f16d2135e7f33790770479e9", "fileid": "08dcbbc61270ae8de803355a832e34147950f3574c5d23d2e7ccb4d7c186339a", "status": "success", "buildurl": "https://github.com/r-universe/jorgeklz/actions/runs/28021883168" }, { "r": "4.7.0", "os": "win", "version": "0.1.1", "date": "2026-06-23T11:14:55.000Z", "commit": "c88b27ba19c7efe7f16d2135e7f33790770479e9", "fileid": "3af87f9801659d30fa34f48db588f7627941a2cea3c00dc3f4e7e98872f059c9", "status": "success", "check": "NOTE", "buildurl": "https://github.com/r-universe/jorgeklz/actions/runs/28021883168" }, { "r": "4.5.3", "os": "win", "version": "0.1.1", "date": "2026-06-23T11:14:49.000Z", "commit": "c88b27ba19c7efe7f16d2135e7f33790770479e9", "fileid": "a2e1ab9cc9791a63b9a00a7693a409ccab4c894ad1e1ff25ed7f8061646aa9e2", "status": "success", "check": "NOTE", "buildurl": "https://github.com/r-universe/jorgeklz/actions/runs/28021883168" }, { "r": "4.6.0", "os": "win", "version": "0.1.1", "date": "2026-06-23T11:14:41.000Z", "commit": "c88b27ba19c7efe7f16d2135e7f33790770479e9", "fileid": "9e9568c097c5135635cb143fdab695d0e9166ec82cabaf2ff453fb747e33e390", "status": "success", "check": "NOTE", "buildurl": "https://github.com/r-universe/jorgeklz/actions/runs/28021883168" } ] }