Algorithm for Finding Valid Cycles in an Improvement Graph

[christophgruene]

Searching very large-scale neighborhoods (VLSN) is a meta heuristic for optimization problems. One defines the neighborhood by certain operations for example for TSP (https://en.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic).
After the definition of these operations, one can define the corresponding cyclic-exchange or multi-exchange neighborhood. In the process of finding one or the best improvement in such a neighborhood, building an improvement graph is a usual method. An picturesque example is a cyclic exchange neighborhood search heuristic for k-PARTITION. In there, we move in a cyclic fashion elements from one set in the partition to other sets such that we get an improvement for our solution to the k-PARTITION instance.
Based on the paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.15.6758&rep=rep1&type=pdf, we want to implement an algorithm that finds the shortest valid cycle in the improvement graph in order to use it in VLSN or local searchs. Finding such a cycle is NP-hard such that this algorithm runs exponential time.

Does this fit the scope of this library?