Tabu search for graph partitioning problem

Celem pracy jest implementacja algorytmu Tabu search dla nieskierowanego grafu, który posiada wagi krawędzi oraz wagi wierzchołków. Zadaniem algorytmu jest znalezienie podziału grafu na dwa podgrafy w taki sposób, aby suma wag wierzchołków w obu podgrafach była taka sama, a suma wag krawędzi usuniętych była jak najmniejsza. Najtrudniejszym problemem do rozwiązania w tym zadaniu jest dopasowanie implementacji algorytmu Tabu search w taki sposób, aby rozwiązywał on problem podziału grafu.

The main purpose of the work is to implement the Tabu search algorithm for an undirected graph with edge weights and vertex weights. The algorithm's task is to find the partition of the graph into two subgraphs in such a way that the sum of the vertex weights in both subgraphs is the same, and the sum of the weights of the removed edges is as small as possible. The most difficult problem to solve is to adjust the implementation of the Tabu search algorithm in such a way that it solves the problem of graph partitioning.