Fixed

Fixed #108: Non-elementary checks for 2-cycles (i->j->i are not allowed). Thanks @felicze

Scientific Software - Peer-reviewed - C++
Published by torressa over 3 years ago

Changed

Refactored Python and C++ unittests.
Added C# interface.
Moved documentation from readthedocs to github pages.
Non-elementary checks for 2-cycles (i->j->i are not allowed).

Added

Logger using sdplog.

Fixed

Issue: Bidirectional algorithm is not finding valid paths when using non-zero minimum resource values #89
Issue: Bidirectional not finding valid path when using negative resource consumption #90
Issue: Dominance check for elementary paths #94

Scientific Software - Peer-reviewed - C++
Published by torressa almost 4 years ago

Changed

Fix minimum number of nodes on path condition for PSOLGENT.
Force node sorting to start with "Source" and end with "Sink" in PSOLGENT.
Force inclusion of Source and Sink nodes in PSOLGENT paths.
Clean up:
1. BiDirectional to use search objects again.
2. labelling.* remove LabelExtension unified with Params.

Added

Record rand value used to generate PSOLGENT paths from positions.
Make upper and lower bound of PSOLGENT initial positions optional arguments.
2opt in PSOLGENT for better evaluation of solutions.
Critical resource as a parameter to BiDirectional
[EXPERIMENTAL] Add critical resource preprocessing attempt using longest paths

Fixed

Issue #79

Scientific Software - Peer-reviewed - C++
Published by torressa almost 5 years ago

Changed

Graph implementation replaced with LEMON. Brings significant improvement on some instances (e.g. on the benchmarks, pretty similar on solomon).
Docker images

Added

Benchmarks against boost's rcshortest_paths (#65) in benchmarks/README.md.

Fixed

Issues #66, #68, #69, #72

Scientific Software - Peer-reviewed - C++
Published by torressa about 5 years ago

cspy - v1.0.0-alpha

Rewrite of the bidirectional algorithm in C++ interfaced with Python using SWIG.

Comparison

I compared the performance on a solomon instance using vrpy. The exact=True/False are attributes of vrpy that uses the threshold option.

old_vs_new

Changed

The algorithm improvements include: - Faster joining procedure (when direction="both") with lower bounding and sorted labels - Bounds pruning using shortest path algorithm lower bounds and the primal bound obtained during the search (experimental). - Backwards incompatible change to do with custom REFs. Now, instead of specifying each function separately, you can implement them in class that inherits from REFCallback. and then pass them to the algorithm using the REF_callback parameter. This change applies to all algorithms. Note that: 1. the naming of the functions has to match (REF_fwd, REF_bwd and REF_join) 2. so does the number of arguments (not necessarily the naming of the variables though) 3. not all three have to be implemented. If for example, one is just using direction="forward", then only REF_fwd would suffice. In the case of the callback being passed and only part of the functions implemented, the default implementation will used for the missing ones.

e.g. ```python from cspy import BiDirectional, REFCallback

class MyCallback(REFCallback):

def __init__(self, arg1, arg2):
    # You can use custom arguments and save for later use
    REFCallback.__init__(self) # Init parent
    self._arg1: int = arg1
    self._arg2: bool = arg2

def REF_fwd(self, cumul_res, tail, head, edge_res, partial_path,
            cumul_cost):
    res_new = list(cumul_res) # local copy
    # do some operations on `res_new` maybe using `self._arg1/2`
    return res_new

def REF_bwd(self, cumul_res, tail, head, edge_res, partial_path,
            cumul_cost):
    res_new = list(cumul_res) # local copy
    # do some operations on `res_new` maybe using `self._arg1/2`
    return res_new

def REF_join(self, fwd_resources, bwd_resources, tail, head, edge_res):
    fwd_res = list(fwd_resources) # local copy
    # do some operations on `res_new` maybe using `self._arg1/2`
    return fwd_res

Load G, maxres, minres

alg = BiDirectional(G, maxres, minres, REF_callback=MyCallback(1, True)) ```

Added

Benchmarks (and comp results for BiDirectional) from Beasley and Christofides (1989)

Fixed

[BiDirectional] Bug fix for non-elementary paths (#52)
[PSOLGENT] Bug fix for local search (#57)

Removed

BiDirectional python implementation (can be found here)
BiDirectional method="random" see issues (hopefully only temporary).

Scientific Software - Peer-reviewed - C++
Published by torressa over 5 years ago

cspy - v0.1.2

New Parameters and changes to the custom REF inputs

Scientific Software - Peer-reviewed - C++
Published by torressa almost 6 years ago