Package implementing some well known Reoptimization algorithms

Perterson Graph (Made using GeoGebra)

Currently, considerable efforts must be put to find optimal solution for NP-Hard problems. Reoptimisation deals with, If given an optimal solution to a problem instance I_O, can we find a good approximated solution to instance I_N, where I_N is I_O with some 'local' modifications? The goal in this repository is to expose some well known reoptimization algorithms.

• (Recommended) Python versions: >=3.6, <=3.9.*

• Option 1

  To Install the stable latest package from pypi host

  pip install reoptimization-algorithms

• Option 2

  To install directly from this repository execute the following in repository root directory

  python setup.py install

import reoptimization_algorithms as ra

old_graph = (ra.UndirectedGraph().add_vertex("4").add_edge("4", "5").add_edge("40", "50")
             .add_vertex("6").add_edge("4", "8").add_vertex("99").delete_vertex("6"))
attached_graph = ra.UndirectedGraph().add_edge("90", "95")
attach_edges = [ra.Edge("4", "90")]
old_solution = {"8"}

solution = ra.UnweightedPVCP.reoptimize_ptas(old_graph, attached_graph, attach_edges,
                                             old_solution, k = 3)
print(solution) # {"4"}

For detailed documentation and usage refer here

Implementation basically consists of

1. Having a graph data structure utility
2. Implementing the graph algorithms

Algorithms implemented

• PTAS for Reoptimization of unweighted k-path vertex cover under constant size graph insertion

Want to add or improvise the repository? Check out the Contributing documentation :)