The k-Medoids Problem through Lagrangian Duality lens

Repository for the course on Combinatorial Optimization at PESC - Systems Engineering and Computer Science Program from UFRJ - Federal University of Rio de Janeiro, taught by Prof. Abilio Pereira de Lucena Filho.

Developed by Ronald Albert.

The project

This work was developed for the Combinatorial Optimization course, taught by Professor Abílio Lucena in 2023/P2 for the Computer Systems Engineering Program (PESC). In this work, Lagrangian relaxation will be applied to the analysis of clustering in the specific context of the k-medoids problem. More specifically, by usage of the subgradient method upper and lower bounds are gradually generated for bounding the objective function, with the hope that such bounds eventually converge to the optimal value of the objective function.

It's entirely implemented in Julia, and all the results are available in the folder results.

File list

• src/OptimalCluster.jl

Main module of the project where all other modules are imported.

• src/HomogeneousCluster.jl

Module for implementing the $k$-medoids clustering problem, an approximate implementation is implemented with the subgradient method, as well as, an exact solution with the help of Gurobi solvers.