
Boost : 
From: Michael Drexl (michael_at_[hidden])
Date: 20051209 02:54:50
Thank you for your interest and your comments.
> For such hard problems there is an enormous design space (and an even
> bigger algorithm space) to be considered, so a good dose of genericity
> in the implementation would be appreciated (hopefully it comes with
> concepts?).
Hm, I don't know what exactly you would consider a "good dose of
genericity", but it may well be that I have made some design decisions
that you'll find too restrictive/not generic enough. I'll post the code
I propose  after some renaming and reformatting and the like to
comply with the Boost standards  to the sandbox vault, then you can see
for yourself.
> Since it's NPhard, it would be good to have also a reduction from
> some wellknown NPcomplete problem to SPPRC (for example graph
> colouring), which would be very useful for testing (using some
> established implementation for that NPcomplete problem).
As for the testing, I use the algorithm as a subroutine in a solution
procedure for the Vehicle Routing Problem (VRP), and I have an
alternative exact solution procedure for the VRP. Both procedures
consistently yield the same solutions.
Moreover, I've tested it against the BGL algorithms for the SPP without
resource constraints (which is an SPPRC with one resource constraint
with no upper bound on the consumption of this resource), and achieved
the same results there, too.
Finally, I've solved Shortest Path Problems with Time Windows (two
resources: cost and time) with my algorithm and with an MIP solver
(CPLEX), and this gave correct results as well.
Regards,
Michael
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk