[pre-ANN] RingStarProblems.jl ⸺ A RSPSolver

A Ring Star Problem variants Solver

Ring Star Problem

I am super happy to share the package RingStarProblems.jl.
This package aims to provide a solver to the Ring Star Problem and its variants.

You can checkout the Labbé et al. (2004) Networks - Article that formulates the first MILP for the Ring Star Problem or the RSP Wikipedia page if you would like to discover more about this NP-Hard problem, which is known to be a generalization of TSP :smile:

RingStarProblems.jl is still under development, feel free to provide any feedback :blush:

Installation

julia> import Pkg ; Pkg.add("RingStarProblems")
9 Likes

Awesome work, congrats! If you need some guidance for creating or improving packages, be sure to check out our blog https://modernjuliaworkflows.github.io/sharing/ :slight_smile:

2 Likes

Many thanks for the support and suggesting the excellent MoJuWo @gdalle :smiling_face_with_three_hearts:

Just released the first patch :smile:

v0.1.2 Patch release notes

Now using Dedicated Types for the solver’s parameters instead of Strings #5

:white_check_mark: A big high five to @nsajko for suggesting it!

Other release improvements

:white_check_mark: Refactoring of several datatypes and variable names to be more compliant with Julia style guide
:white_check_mark: Improving README.md, adding tags and deleted unwanted branches “master”
:white_check_mark: Applying JuliaFormatter.jl
:white_check_mark: Deleting some useless files
:white_check_mark: Compatibily issues fixed
:white_check_mark: Create target ] test for UnitTest and solutionchecker

Plan for upcomming v0.1.3

  • Documenter.jl deploy an extensive documentation for the solver
  • Add an All contributors page
  • Pass all disambiguity tests from Aqua.jl, currently 37 disambiguities (1 Broken)
  • Install Julia TagBot, look for other interesting workflows

Any input is most welcome, in particular if you are able to build, using, and launch the solver :blush:

3 Likes

Patch release v0.1.6

:white_check_mark: As mentioned in issue #11 the solver is now optimizer agnostic!
:white_check_mark: Currently supports GLPK and Gurobi
:white_check_mark: Bug fixes
:white_check_mark: RingStarProblems.jl is not “an empty” package anymore, see here.
:white_check_mark: some GitHub workflows successfully added (CI.yml, and TagBot.yml)

According to JuMP manual, the supported solver for Lazy Constraints Callbacks are:

  • CPLEX, GLPK, Xpress, Gurobi

Next patch objectives: v0.1.7

Next minor release objective v0.2.0

Any feedback is most welcome :smiley:

I was able to precompile and using the package on another computer today, plus lauching the README Usage for the first time with this patch release, let me know if this is also the case for you :heart:

2 Likes

Patch release v0.1.7 and v0.1.8

:white_check_mark: Using Symbol to name instances instead of Integer:

symbolinstance = :TinyInstance_12_2
julia> RSP.rspoptimize(pars, symbolinstance, optimizer_with_attributes(GLPK.Optimizer,
			"msg_lev" => GLPK.GLP_MSG_ALL,
			"tm_lim" => pars.timelimit)

Was previously:

id_instance = 3
julia> RSP.rspoptimize(pars, id_instance, optimizer_with_attributes(GLPK.Optimizer,
			"msg_lev" => GLPK.GLP_MSG_ALL,
			"tm_lim" => pars.timelimit)

And

julia> symbolinstance = :berlin52
julia> RSP.rspoptimize(pars, symbolinstance, optimizer_with_attributes(Gurobi.Optimizer,
		"TimeLimit" => pars.timelimit))

Was previously:

julia> id_instance = 14
julia> RSP.rspoptimize(pars, id_instance, optimizer_with_attributes(Gurobi.Optimizer,
		"TimeLimit" => pars.timelimit))

:white_check_mark: plotting solutions to .pdf is now available as an extension
:white_check_mark: several enhancement and minor bug fixes

julia> using GraphPlot, Compose, Colors
julia> pars.plotting = true

Next patch objectives: v0.1.9

  • Continue document the package (use DocStringExtensions.jl)
  • CodeCoverage increased from 18.72% to 21.71%, to continue

Next minor release objective v0.2.0

Any feedback is most welcome :smiley:

Dear Julia community,

Super happy to share the minor release v0.2.0 of RingStarProblems.jl :smiley:

Minor release v0.2.0

v0.1.8 → v0.1.9 → v0.1.10 → v0.2.0

:white_check_mark: Now possible to use coordinates to solve RSP and 1-R-RSP, closing #12

Solving with nodes coordinates

Either:

julia> x = 1:10
julia> y = rand(1:10, 10)
julia> RSP.rspoptimize(pars, x, y, GLPK.Optimizer)

Or:

julia> xycoors = tuple.(1:10, rand(1:10, 10))
julia> RSP.rspoptimize(pars, xycoors, GLPK.Optimizer)

:white_check_mark: plotting solutions is now available

julia> using GraphPlot, Compose, Colors
julia> pars.plotting = true
### then call `rspoptimize`

:white_check_mark: Number of threads and time limit parameters now handled by user instead of RSPSolver.
:white_check_mark: Several enhancement, minor bug fixes and code readability improved
:white_check_mark: Code Coverage increased to 25.98%

I am super happy that the user can now solve the Ring Star Problem with nodes coordinates, same for 1-R-RSP, and also plot the solutions to .pdf!

Let me know about anything you think of :blush:

2 Likes