search

torressa / cspy

A collection of algorithms for the (Resource) Constrained Shortest Path problem in Python / C++ / C#
https://torressa.github.io/cspy/
MIT License
77 stars 24 forks source link

More languages #64

Open torressa opened 3 years ago

torressa commented 3 years ago

Is your feature request related to a problem? Please describe. I'd like an interface for

Describe the solution you'd like (For Julia)

Julia interface file that directly calls the shared object.

Describe the solution you'd like (For C#/Java)

The cmake of this project is based on cmake-swig.

So it shouldn't be too hard to repeat the process of the python interface with C# and Java.

  1. Update cmake/: I left the includes in the main cmake file: https://github.com/torressa/cspy/blob/f506650f03dd68f765b3b419ba6872beb52350e5/CMakeLists.txt#L122-L124 Which would call the (currently non-existing) dotnet.cmake and java.cmake files in the cmake/ folder.

    1. Add SWIG interface files. The swig and cmake files that would build these would be placed in src/cc/[java|dotnet] in a similar fashion as the original repo.

    2. Language specific tests under test/[java|dotnet]. Should include unittests for BiDirectional, some issue specific tests and the custom REF callback test (similar to the python one in test/python/tests_issue32.py)

    3. Update the docker file and github workflows to run these tests and make sure everything works as expected.

stale[bot] commented 3 years ago

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

stale[bot] commented 2 years ago

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

torressa commented 2 years ago

C# seems to work, will upload nupkg on next release.

DavidGarHeredia commented 2 years ago

Hi!

Great job with the repo (and the paper :wink:). I am very happy each time I see that more and more effort is put into code, reproducible environments, etc in OR. Congrats on that!

I had just one tiny question about this issue. When you say "Julia interface file that directly calls the shared object", what do you mean? That you are interested in calling your C++ code from Julia, or that you are interested in having the same algorithms in Julia?

Because I was planning to code some algorithms for the RCSP in pure Julia, so maybe I could help with this issue :smile:

torressa commented 2 years ago

Muchas gracias @DavidGarHeredia ! Appreciate the compliments! :smile:

So, what I meant there was to interface the C++ code directly with Julia (for future reference, and in case you're interested, I discuss the options below).

I wasn't planning on implementing these algorithms in Julia in the near future.

Not sure what your use case is but if most of your code base is in Julia, I think implementing there is worth it. The C++ to Julia interface will bring various headaches and ultimately may not be the most performant option (specially with REF callbacks). If you go down this route, I do have some pointers to exact algorithms that are worth implementing (depends how much time you have, and again, on the use case). I don't think heuristics can compete at the moment, specially as exact algorithms can act as heuristics by e.g. early termination, graph size reduction.

In my order of preference:

algorithm +ve -ve
A* based - Ahmadi et al. (2021) more links in #67 kicks serious ass has several restrictive assumptions about the problem (heuristic exists, integer critical resource)
Bucket graph - Sadykov et al. (2021) state of the art for VRP, brilliant when network structure doesn't change, and I think when you have a dynamic set of resources i.e. using non-robust cuts. identification of 2 resources for buckets, no implementation (and probably v hard)
Bi-Pulse - Cabrera et al. (2020) Fast, old C++ pulse implementation (mono-directional no backtracking) here See Ahmadi et al. (2021) paper
Bidirectional with dynamic halfway point really good when the critical resources are tight and well defined, implementation in this repo temperamental when critical resource is not tight, at best as fast as others e.g. pulse, implementation in this repo

If you do go down this route, I'd be glad to compare on some benchmarks! There are easy instances in this repo, which are also good to check if the implementation is OK (julia parsing here) I'd be super happy with a contribution in Julia, and I'd help you wherever I can. If it doesn't suit, I'll link/refer Julia users to your implementation.

C++ to Julia

There are two main options to call C++ code (one of which is not great):

  1. Use CxxLang.jl to write a thin wrapper for Julia.
  2. Write a C interface to the C++ for example and use the Julia generator Clang.jl

Right now, option 2 seems more attractive and maintainable, specially for working across different platforms, as for now, CxxLang doesn't compile on Windows https://github.com/JuliaLang/julia/issues/34201.

Option 2 is also what most major optimisation C++ projects use to port to Julia, so it's nice to have to a reference. See e.g., HiGHS C Api -> used to generate HiGHS.jl Same with Cbc C Api -> used to generate Cbc.jl. Solvers are mostly in C so also use this Clang, e.g. SCIP.jl, Gurobi.jl and CPLEX.jl.

This approach brings some headaches specially with callbacks, however, all these projects have them, so it's definitely possible.

DavidGarHeredia commented 2 years ago

Hi!

The idea of implementing the algorithms in Julia is not much related to my use case, but to my willingness of moving away from C++ and all the potential headaches it produces (portability to a different OS, verbose code, external libs non-easy to install, difficulties to reproduce the code by non-c++ programmers, etc).

I planned to code first some simple/classic algorithms (see a short list below), and then move to the most recent ones such as the ones you mention.

  1. An improved solution algorithm for the constrained shortest path problem (https://doi.org/10.1016/j.trb.2006.12.001)
  2. On an exact method for the constrained shortest path problem (Pulse algorithm, https://doi.org/10.1016/j.cor.2012.07.008)
  3. Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem (https://doi.org/10.1002/net.10090)

So if you think that this roadmap may fit with your repo, I can do a PR once I have something solid. If on the other hand, you think that for the moment that would create a "too independent" path in your repo, we leave it as it is :P

torressa commented 2 years ago

That's dedication!

Sounds like a very good plan of action.

I'd more than happily have it here. On your side, it may make more sense to lean on the new (not so Light)Graphs.jl community and add your repo there. And also Coluna.jl and co. Ow, if we have it here, we could go on a (needed) renaming rampage. Anyway, have a think about it, in any case, I'm super keen to be involved.