antonios-kagias/computational_optimization

Optimization algorithms and heuristics

Computational Optimization

The projects in this repository were created while working on the course Computational Optimization for my postgraduate studies. They include the following:

1. Compressed Sparse Row (CSR) format: implementation of the Compressed Sparse Row format in Python, a type of sparse matrix representation.

2. Compressed Sparse Column (CSC) format: implementation of the Compressed Sparse Column format in Python, a type of sparse matrix representation.

3. Equilibration Scaling Technique: implementation of the Equilibration scaling technique which is a method of scaling where the maximum absolute value in each row and column of a matrix is multiplied by a factor until it equals one. This method can help the matrix's conditioning and lessen the impact of large or small entries.

4. TSP and related problems parser: a parser for Traveling Salesman Problem (TSP) type of problems. This also includes, apart from TSP files, Hamiltonian Cycle Problem (HCP), Asymmetric Traveling Salesman Problem (ATSP), Sequential Ordering Problem (SOP) and Capacitated Vehicle Routing Problem (CVRP) files. The parser was created in collaboration with a group of people credited within the Python file.

5. TSP problems solver with LKH Python package: solver for Traveling Salesman Problem (TSP) files with the Lin-Kernighan-Helsgaun heuristic using the LKH Python package. The output data (solution in the form of a tour) are exported to a file with the extension .tour (same format as in the TSPLIB library) and plotted using the Python NetworkX package.

6. VRP problems solver with VRPy Python framework: solver for Capacitated Vehicle Routing Problem (CVRP) files with the VRPy Python framework.