Cspy Versions Save

https://github.com/torressa/cspy/compare/v1.0.2...v1.0.3

Fixed

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

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

Coauthored with @dvbuntu! :rocket:

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

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 r_c_shortest_paths (#65) in benchmarks/README.md.

Fixed

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

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.

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.

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, max_res, min_res
alg = BiDirectional(G, max_res, min_res, 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).

New Parameters and changes to the custom REF inputs

Release for JOSS paper.

Code changes include:

• BiDirectional Algorithm: - Reverted backward REF as it is required for some problems. - Added REF join parameter that is required when joining forward and backward labels using custom REFs.
• Moved notes and examples from docstrings to the docs folder

Added

• BiDirectional:
  • Option to chose method for direction selection.
• vrpy submodule.

Changed

• BiDirectional:

  • Label storage, divided into unprocessed, generated and non-dominated labels
  • Restricted join algorithm to non-dominated label
  • Changed backward resource extensions to avoid complex and computationally costly inversion. Additionally, it removes the requirement of an explicit backward REF.
  • Filtering for backward labels in join algorithm.
  • Cleaned up unused label operator overloads.
  • Removed costly comparison in _propagate_label.
  • Changed generated labels attributes from dict of deques to dict of int with count.

• Rework of path and algorithm attributes to avoid duplication

• Replaced networkx.astar algorithm with a procedure that finds a short simple path using networkx.shortest_simple_paths.

Some bug fixes have led to the following changes in the BiDirectional

• Changed label comparison from weight to resource based.
• Simplified and cleaned up implementation (somewhat).
• Implemented full path joining procedure, Algorithm 3, from Righini and Salani (2006). This involved rectified the half-way check that I thought I'd implemented in v0.0.12.
• Parameterized some tests.