Local Search Methods for the One-Sided Crossing Minimisation Problem

This repository contains the code for Local Search Methods for the One-Sided Crossing Minimisation Problem, available here. All code has been implemented within Jupyter Notebooks with SageMath 9.5 kernels and Python 3.10. Each notebook is self-contained.

• OSCM_Introduction.ipynb contains a brief introduction to the One-Sided Crossing Minimisation Problem.
• OSCM_Local_Search.ipynb contains the presented algorithms.
• data/ contains test instances for the provided code.

References:

• The base graph class used throughout the project is a heavily modified version of the class used in the PACE Challenge verifier package.
• The only dependency outside of the Python standard library is the segment-tree package. This may be installed by running pip install segment-tree.

---

This project is licensed under the MIT License - see the LICENSE file for details.